F-Factors in Hypergraphs Via Absorption

• Published in: Graphs and combinatorics 2015-05, Vol.31 (3), p.679-712
• Main Authors: Lo, Allan, Markström, Klas
• Format: Article
• Language: English
• Subjects: 05C07; 05C70; Combinatorics; Engineering Design; F-factor; Hypergraph; k-Graph; Mathematics; Mathematics and Statistics; Minimum degree; Original Paper; Primary 05C65
• ISSN: 0911-0119; 1435-5914; 1435-5914
• DOI: 10.1007/s00373-014-1410-8

Given integers n ≥ k > l ≥ 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 δ l ( H ) ≥ d contains an F -factor. A classical theorem of Hajnal and Szemerédi in (Proof of a Conjecture of P. Erdős, pp. 601–623, 1969 ) implies that t 1 2 ( n , K t ) = ( 1 - 1 / t ) n for integers t . For k ≥ 3 , t k - 1 k ( n , K k k ) (the δ k - 1 ( H ) threshold for perfect matchings) has been determined by Kühn and Osthus in (J Graph Theory 51(4):269–280, 2006 ) (asymptotically) and Rödl et al. in (J Combin Theory Ser A 116(3):613–636, 2009 ) (exactly) for large n . In this paper, we generalise the absorption technique of Rödl et al. in (J Combin Theory Ser A 116(3):613–636, 2009 ) to F -factors. We determine the asymptotic values of t 1 k ( n , K k k ( m ) ) for k = 3 , 4 and m ≥ 1 . In addition, we show that for t > k = 3 and γ > 0 , t 2 3 ( n , K t 3 ) ≤ ( 1 - 2 t 2 - 3 t + 4 + γ ) 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 (Graphs Combin 24(4):391–404, 2008 ). In addition, we prove that t k - 1 k ( n , K t k ) ≤ ( 1 - t - 1 k - 1 - 1 + γ ) n for γ > 0 , k ≥ 6 and t ≥ ( 3 + 5 ) k / 2 provided n is large and t | n .