Hostname: page-component-745bb68f8f-b6zl4 Total loading time: 0 Render date: 2025-02-11T22:55:41.836Z Has data issue: false hasContentIssue false
  • English
  • Français

Exact Minimum Codegree Threshold for K−4-Factors

Published online by Cambridge University Press:  04 August 2017

JIE HAN ,
ALLAN LO ,
ANDREW TREGLOWN  and
YI ZHAO
JIE HAN
Affiliation:
Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo, SP 05508-090, Brazil (e-mail: jhan@ime.usp.br)
ALLAN LO
Affiliation:
School of Mathematics, University of Birmingham, Birmingham B15 2TT, UK (e-mail: s.a.lo@bham.ac.uk, a.c.treglown@bham.ac.uk)
ANDREW TREGLOWN
Affiliation:
School of Mathematics, University of Birmingham, Birmingham B15 2TT, UK (e-mail: s.a.lo@bham.ac.uk, a.c.treglown@bham.ac.uk)
YI ZHAO
Affiliation:
Department of Mathematics and Statistics, Georgia State University, Atlanta, GA 30303, USA (e-mail: yzhao6@gsu.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 K−4 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 K−4-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.

Keywords

Primary 05C70Secondary 05C3505C65
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 6 , November 2017 , pp. 856 - 885
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Baber, R. and Talbot, J. (2011) Hypergraphs do jump. Combin. Probab. Comput. 20 161–171.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 124–136.Google Scholar
[4] Daykin, D. E. and Häggkvist, R. (1981) Degrees giving independent edges in a hypergraph. Bull. Austral. Math. Soc. 23 103–109.Google Scholar
[5] Erdős, P. (1964) On extremal problems of graphs and generalized graphs. Israel J. Math. 2 183–190.Google Scholar
[6] Erdős, P. and Simonovits, M. (1983) Supersaturated graphs and hypergraphs. Combinatorica 3 181–192.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) 536–559.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 601–623.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 115–147.Google Scholar
[10] Han, J. and Zhao, Y. (2015) Minimum vertex degree threshold for C 4 3-tiling. J. Graph Theory 79 300–317.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 767–821.Google Scholar
[13] Kühn, D. and Osthus, D. (2009) The minimum degree threshold for perfect graph packings. Combinatorica 29 65–107.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. 137–167.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 708–721.Google Scholar
[16] Lo, A. and Markström, K. (2015) F-factors in hypergraphs via absorption. Graphs Combin. 31 679–712.Google Scholar
[17] Mycroft, R. (2016) Packing k-partite k-uniform hypergraphs. J. Combin. Theory Ser. A 138 60–132.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. 1–30.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 229–251.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 613–636.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. 145–165.Google Scholar