Packing k-partite k-uniform hypergraphs

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)\ge \delta$ 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 $k\ge 3$. 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ödl and Ruciński 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$.

v2: Updated with minor corrections. Accepted for publication in Journal of Combinatorial Theory, Series A

References in corpus (4)

• Hypergraph regularity and the multidimensional Szemerédi theorem
• Polynomial-time perfect matchings in dense hypergraphs
• Perfect Packings in Quasirandom Hypergraphs II
• Minimum vertex degree threshold for $C_4^3$-tiling