Packing k-partite k-uniform hypergraphs

DOI10.1016/J.JCTA.2015.09.007zbMATH Open1326.05122arXiv1402.5643OpenAlexW2005146019MaRDI QIDQ891826FDOQ891826

Authors: Richard Mycroft 

Publication date: 17 November 2015

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: Let $G$ and $H$ be $k$-graphs ($k$-uniform hypergraphs); then a perfect $H$-packing in $G$ is a collection of vertex-disjoint copies of $H$ in $G$ which together cover every vertex of $G$. For any fixed $H$ let $delta(H,n)$ be the minimum $delta$ such that any $k$-graph $G$ on $n$ vertices with minimum codegree $delta(G)geqdelta$ contains a perfect $H$-packing. The problem of determining $delta(H,n)$ has been widely studied for graphs (i.e. $2$-graphs), but little is known for $kgeq3$. Here we determine the asymptotic value of $delta(H,n)$ for all complete $k$-partite $k$-graphs $H$, as well as a wide class of other $k$-partite $k$-graphs. In particular, these results provide an asymptotic solution to a question of R"odl and Ruci'nski on the value of $delta(H,n)$ when $H$ is a loose cycle. We also determine asymptotically the codegree threshold needed to guarantee an $H$-packing covering all but a constant number of vertices of $G$ for any complete $k$-partite $k$-graph $H$.

Full work available at URL: https://arxiv.org/abs/1402.5643

Recommendations

• Packing \(k\)-partite \(k\)-uniform hypergraphs
• Almost perfect matchings in \(k\)-partite \(k\)-graphs
• Minimum codegree condition for perfect matchings in k‐partite k‐graphs
• On a hypergraph matching problem
• Perfect packings in quasirandom hypergraphs. I.

zbMATH Keywords

tilinghypergraphspacking

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Tiling Turán theorems
• \(H\)-factors in dense graphs
• The minimum degree threshold for perfect graph packings
• \(F\)-factors in hypergraphs via absorption
• On extremal problems of graphs and generalized graphs
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Regularity Lemma for k-uniform hypergraphs
• Title not available (Why is that?)
• Proof of the Alon-Yuster conjecture
• Perfect matchings and \(K_4^3\)-tilings in hypergraphs of large codegree
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• Minimum codegree threshold for \((K^3_4-e)\)-factors
• Matchings in 3-uniform hypergraphs
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs. II
• Perfect matchings in 3-uniform hypergraphs with large vertex degree
• Tiling 3-uniform hypergraphs with \(K_4^3-2e\)
• On perfect matchings in uniform hypergraphs with large minimum vertex degree
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
• Perfect Packings in Quasirandom Hypergraphs II
• Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
• Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree
• Perfect matchings in 4-uniform hypergraphs
• A hypergraph blow-up lemma
• Regular Partitions of Hypergraphs: Regularity Lemmas
• Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
• Regular Partitions of Hypergraphs: Counting Lemmas
• Loose Hamilton cycles in hypergraphs
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• A note on codegree problems for hypergraphs
• Perfect matchings in \(r\)-partite \(r\)-graphs
• Degrees giving independent edges in a hypergraph
• Perfect matchings in 3-partite 3-uniform hypergraphs
• Tight co-degree condition for perfect matchings in 4-graphs
• Polynomial-time perfect matchings in dense hypergraphs
• Minimum vertex degree threshold for \(\mathcal{C}_4^3\)-tiling

Cited In (25)

• Integer and fractional packings in dense 3‐uniform hypergraphs
• Covering and tiling hypergraphs with tight cycles
• Covering and tiling hypergraphs with tight cycles
• Network Capacity Bound for Personalized PageRank in Multimodal Networks
• Packing \(k\)-partite \(k\)-uniform hypergraphs
• A geometric theory for hypergraph matching
• Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
• Codegree thresholds for covering 3-uniform hypergraphs
• Tight minimum degree condition for the existence of loose cycle tilings in 3-graphs
• A note on packing of uniform hypergraphs
• The complexity of perfect matchings and packings in dense hypergraphs
• Tiling multipartite hypergraphs in quasi-random hypergraphs
• On perfect matchings and tilings in uniform hypergraphs
• Codegree threshold for tiling \(k\)-graphs with two edges sharing exactly \(\ell\) vertices
• Sufficient conditions for perfect mixed tilings
• An asymptotic multipartite Kühn-Osthus theorem
• Minimum codegree threshold for \(C_6^3\)-factors in 3-uniform hypergraphs
• Codegree conditions for tiling complete \(k\)-partite \(k\)-graphs and loose cycles
• Shadows of 3-uniform hypergraphs under a minimum degree condition
• Packing of nonuniform hypergrahs- product and sum of sizes conditions
• Codegree threshold for tiling balanced complete \(3\)-partite \(3\)-graphs and generalized \(4\)-cycles
• Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
• Maximally connected \(p\)-partite uniform hypergraphs
• Constructive packings by linear hypergraphs
• Exact minimum codegree threshold for \(K^-_4\)-factors

This page was built for publication: Packing \(k\)-partite \(k\)-uniform hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q891826)