$F$-factors in hypergraphs via absorption

By Allan Siu Lun Lo, K. Markstrom. 2011

58 citations recorded by the source corpus.

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\'{e}di implies that $t^2_1(n,K_t) = (1-1/t)n$ for integers $t$. For $k \ge 3$, $t^k_{k-1}(n,K_k^k)$ (the $\delta_{k-1}(H)$ threshold for perfect matchings) has been determined by K\"{u}hn and Osthus (asymptotically) and R\"{o}dl, Ruci\'{n}ski and Szemer\'{e}di (exactly) for large $n$. In this paper, we generalise the absorption technique of R\"{o}dl, Ruci\'{n}ski and Szemer\'{e}di to $F$-factors. We determine the asymptotic values of $t^k_1(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^3_{2}(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^3_{2}(n,K_t^3)$ from below. In particular, we deduce that $t^3_2(n,K_4^3) = (3/4+o(1))n$ answering a question of Pikhurko. In addition, we prove that $t^k_{k-1}(n,K_t^k) \le (1- \binom{t-1}{k-1}^{-1} + \gamma)n$ for $\gamma>0$, $k \ge 6$ and $t \ge (3+ \sqrt5)k/2$ provided $n$ is large and $t | n$.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/5886498896410c4e05b864f62e95a79c748b33f9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

  1. Yi Zhao
  2. Jie Han

In Discrete Mathematics and Combinatorics

  1. Yi Zhao
  2. Jie Han

In Geometry and Topology

  1. Yi Zhao
  2. Jie Han

Citations in the corpus