$F$-factors in hypergraphs via absorption

Abstract

Given integers $n\ge k>l\ge 1$ and a $k$-graph $F$ with $|V(F)|$ divisible by $n$, define $t_l^k(n,F)$ to be the smallest integer $d$ such that every $k$-graph $H$ of order $n$ with minimum $l$-degree ${\delta }_l(H)\ge d$ contains an $F$-factor. A classical theorem of Hajnal and Szemerédi implies that $t_1^2(n,K_t)=(1-1/t)n$ for integers $t$. For $k\ge 3$, $t_{k-1}^k(n,K_k^k)$ (the ${\delta }_{k-1}(H)$ threshold for perfect matchings) has been determined by Kühn and Osthus (asymptotically) and Rödl, Ruciński and Szemerédi (exactly) for large $n$. In this paper, we generalise the absorption technique of Rödl, Ruciński and Szemerédi to $F$-factors. We determine the asymptotic values of $t_1^k(n,K_k^k(m))$ for $k=3,4$ and $m\ge 1$. In addition, we show that for $t>k=3$ and $\gamma >0$, $t_2^3(n,K_t^3)\le (1-\frac{2}{t^2-3t+4}+\gamma )n$ provided $n$ is large and $t|n$. We also bound $t_2^3(n,K_t^3)$ from below. In particular, we deduce that $t_2^3(n,K_4^3)=(3/4+o(1))n$ answering a question of Pikhurko. In addition, we prove that $t_{k-1}^k(n,K_t^k)\le (1-{\left(\genfrac{}{}{0ex}{}{t-1}{k-1}\right)}^{-1}+\gamma )n$ for $\gamma >0$, $k\ge 6$ and $t\ge (3+\sqrt{5})k/2$ provided $n$ is large and $t|n$.

Final version, accepted for publication in Graphs and Combinatorics

References in corpus (2)

• Matchings in 3-uniform hypergraphs
• Toward a Hajnal-Szemeredi theorem for hypergraphs

Cited by in corpus (8)

• Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
• Polynomial-time perfect matchings in dense hypergraphs
• Perfect Packings in Quasirandom Hypergraphs II
• Large matchings in uniform hypergraphs and the conjectures of Erdos and Samuels
• A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs
• Packing k-partite k-uniform hypergraphs
• Tiling 3-uniform hypergraphs with K_4^3-2e
• Minimum codegree threshold for $(K_4^3-e)$-factors