Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-25T08:16:23.896Z Has data issue: false hasContentIssue false

Exact Minimum Codegree Threshold for K4-Factors

Published online by Cambridge University Press:  04 August 2017

JIE HAN
Affiliation:
Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo, SP 05508-090, Brazil (e-mail: [email protected])
ALLAN LO
Affiliation:
School of Mathematics, University of Birmingham, Birmingham B15 2TT, UK (e-mail: [email protected], [email protected])
ANDREW TREGLOWN
Affiliation:
School of Mathematics, University of Birmingham, Birmingham B15 2TT, UK (e-mail: [email protected], [email protected])
YI ZHAO
Affiliation:
Department of Mathematics and Statistics, Georgia State University, Atlanta, GA 30303, USA (e-mail: [email protected])

Abstract

Given hypergraphs F and H, an F-factor in H is a set of vertex-disjoint copies of F which cover all the vertices in H. Let K4 denote the 3-uniform hypergraph with four vertices and three edges. We show that for sufficiently large n ∈ 4ℕ, every 3-uniform hypergraph H on n vertices with minimum codegree at least n/2−1 contains a K4-factor. Our bound on the minimum codegree here is best possible. It resolves a conjecture of Lo and Markström [15] for large hypergraphs, who earlier proved an asymptotically exact version of this result. Our proof makes use of the absorbing method as well as a result of Keevash and Mycroft [11] concerning almost perfect matchings in hypergraphs.

Type
Paper
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Baber, R. and Talbot, J. (2011) Hypergraphs do jump. Combin. Probab. Comput. 20 161171.Google Scholar
[2] Czygrinow, A. Minimum degree condition for C 4-tiling in 3-uniform hypergraphs. Unpublished manuscript.Google Scholar
[3] Czygrinow, A., DeBiasio, L. and Nagle, B. (2014) Tiling 3-uniform hypergraphs with K 4 3-2e . J. Graph Theory 75 124136.Google Scholar
[4] Daykin, D. E. and Häggkvist, R. (1981) Degrees giving independent edges in a hypergraph. Bull. Austral. Math. Soc. 23 103109.Google Scholar
[5] Erdős, P. (1964) On extremal problems of graphs and generalized graphs. Israel J. Math. 2 183190.Google Scholar
[6] Erdős, P. and Simonovits, M. (1983) Supersaturated graphs and hypergraphs. Combinatorica 3 181192.Google Scholar
[7] Gao, W. and Han, J. (2017) Minimum codegree threshold for C 6 3-factors in 3-uniform hypergraphs. Combin. Probab. Comput. 26 (4) 536559.Google Scholar
[8] Hajnal, A. and Szemerédi, E. (1970) Proof of a conjecture of Erdős. In Combinatorial Theory and its Applications vol. II 4 601623.Google Scholar
[9] Han, J., Zang, C. and Zhao, Y. (2017) Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs. J. Combin. Theory Ser. A 149 115147.Google Scholar
[10] Han, J. and Zhao, Y. (2015) Minimum vertex degree threshold for C 4 3-tiling. J. Graph Theory 79 300317.Google Scholar
[11] Keevash, P. and Mycroft, R. (2014) A Geometric Theory for Hypergraph Matching, Vol. 233, no. 1098 of Memoirs of the American Mathematical Society, AMS.Google Scholar
[12] Kühn, D. and Osthus, D. (2006) Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree. J. Combin. Theory Ser. B 96 767821.Google Scholar
[13] Kühn, D. and Osthus, D. (2009) The minimum degree threshold for perfect graph packings. Combinatorica 29 65107.Google Scholar
[14] Kühn, D. and Osthus, D. (2009) Embedding large subgraphs into dense graphs. In Surveys in Combinatorics (Huczynska, S., Mitchell, J. D. and Roney-Dougal, C. M., eds), Vol. 365 of London Mathematical Society Lecture Notes, Cambridge University Press, pp. 137167.Google Scholar
[15] Lo, A. and Markström, K. (2013) Minimum codegree threshold for (K 4 3-e)-factors. J. Combin. Theory Ser. A 120 708721.Google Scholar
[16] Lo, A. and Markström, K. (2015) F-factors in hypergraphs via absorption. Graphs Combin. 31 679712.Google Scholar
[17] Mycroft, R. (2016) Packing k-partite k-uniform hypergraphs. J. Combin. Theory Ser. A 138 60132.Google Scholar
[18] Rödl, V. and Ruciński, A. (2010) Dirac-type questions for hypergraphs: A survey (or more problems for Endre to solve). In An Irregular Mind: Szemerédi is 70, Vol. 21 of Bolyai Society Mathematical Studies, pp. 130.Google Scholar
[19] Rödl, V., Ruciński, A. and Szemerédi, E. (2006) A Dirac-type theorem for 3-uniform hypergraphs. Combin. Probab. Comput. 15 229251.Google Scholar
[20] Rödl, V., Ruciński, A. and Szemerédi, E. (2009) Perfect matchings in large uniform hypergraphs with large minimum collective degree. J. Combin. Theory Ser. A 116 613636.Google Scholar
[21] Zhao, Y. (2016) Recent advances on Dirac-type problems for hypergraphs. In Recent Trends in Combinatorics, Vol. 159 of The IMA Volumes in Mathematics and its Applications, Springer, pp. 145165.Google Scholar