F-Factors in Hypergraphs Via Absorption
2015 (English)In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 31, no 3, 679-712 p.Article in journal (Refereed) Published
Given integers n ≥ k > l ≥ 1 and a k-graph F with |V(F)| divisible by n, define t k l (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˝os, pp. 601–623, 1969) implies that t2 1 (n, Kt) = (1 − 1/t)n for integers t. For k ≥ 3, t k k−1(n, Kk 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 k 1 (n, Kk k (m)) for k = 3, 4 and m ≥ 1. In addition, we show that for t > k = 3 and γ > 0, t3 2 (n, K3 t ) ≤ (1− 2 t2−3t+4 +γ )n provided n is large and t|n. We also bound t 3 2 (n, K3 t )from below. In particular, we deduce that t 3 2 (n, K3 4 ) = (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 k−1(n, Kk t ) ≤ (1 − t−1 k−1 −1 + γ )n for γ > 0, k ≥ 6 and t ≥ (3 + √ 5)k/2 provided n is large and t|n.
Place, publisher, year, edition, pages
2015. Vol. 31, no 3, 679-712 p.
Hypergraph, k-Graph, F-factor, Minimum degree, Primary 05C65, 05C70, 05C07
IdentifiersURN: urn:nbn:se:umu:diva-92703DOI: 10.1007/s00373-014-1410-8ISI: 000353232900015ScopusID: 2-s2.0-84896417194OAI: oai:DiVA.org:umu-92703DiVA: diva2:742342