Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-07T18:01:13.180Z Has data issue: false hasContentIssue false
  • English
  • Français

Minimum Codegree Threshold for C 6 3-Factors in 3-Uniform Hypergraphs

Published online by Cambridge University Press:  22 March 2017

WEI GAO  and
JIE HAN
WEI GAO
Affiliation:
Department of Mathematics and Statistics, Auburn University, 221 Parker Hall, Auburn, AL 36849, USA (e-mail: wzg0021@auburn.edu)
JIE HAN
Affiliation:
Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508-090, São Paulo, Brazil (e-mail: jhan@ime.usp.br)
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.

Let C 6 3 be the 3-uniform hypergraph on {1, . . ., 6} with edges 123,345,561, which can be seen as the analogue of the triangle in 3-uniform hypergraphs. For sufficiently large n divisible by 6, we show that every n-vertex 3-uniform hypergraph H with minimum codegree at least n/3 contains a C 6 3-factor, that is, a spanning subhypergraph consisting of vertex-disjoint copies of C 6 3. The minimum codegree condition is best possible. This improves the asymptotic result obtained by Mycroft and answers a question of Rödl and Ruciński exactly.

Keywords

Primary 05C70Secondary 05C65

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 4 , July 2017 , pp. 536 - 559
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Alon, N., Frankl, P., Huang, H., Rödl, V., Ruciński, A. and Sudakov, B. (2012) Large matchings in uniform hypergraphs and the conjecture of Erdős and Samuels. J. Combin. Theory Ser. A 119 1200–1215.Google Scholar
[2] Alon, N. and Yuster, R. (1996) H-factors in dense graphs. J. Combin. Theory Ser. B 66 269–282.Google Scholar
[3] Corradi, K. and Hajnal, A. (1963) On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hungar. 14 423–439.CrossRefGoogle Scholar
[4] Czygrinow, A. (2016) Tight co-degree condition for packing of loose cycles in 3-graphs. J. Graph Theory 83 317–333.Google Scholar
[5] Czygrinow, A. Minimum degree condition for C 4-tiling in 3-uniform hypergraphs. Preprint.Google Scholar
[6] 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
[7] Czygrinow, A. and Kamat, V. (2012) Tight co-degree condition for perfect matchings in 4-graphs. Electron. J. Combin. 19 #P20.CrossRefGoogle Scholar
[8] Czygrinow, A. and Molla, T. (2014) Tight codegree condition for the existence of loose Hamilton cycles in 3-graphs. SIAM J. Discrete Math. 28 67–76.Google Scholar
[9] Erdős, P. (1964) On extremal problems of graphs and generalized graphs. Israel J. Math. 2 183–190.Google Scholar
[10] Gao, W., Han, J. and Zhao, Y. Codegree conditions for tiling complete k-partite k-graphs and loose cycles. arXiv:1612.07247 Google Scholar
[11] Hajnal, A. and Szemerédi, E. (1970) Proof of a conjecture of P. Erdős. In Combinatorial Theory and its Applications II: Balatonfüred 1969, North-Holland, pp. 601–623.Google Scholar
[12] Hàn, H. and Schacht, M. (2010) Dirac-type results for loose Hamilton cycles in uniform hypergraphs. J. Combin. Theory Ser. B 100 332–346.Google Scholar
[13] Han, J. (2015) Near perfect matchings in k-uniform hypergraphs. Combin. Probab. Comput. 24 723–732.Google Scholar
[14] Han, J., Lo, A., Treglown, A. and Zhao, Y. Exact minimum codegree threshold for K 4 −-factors. Preprint.Google Scholar
[15] Han, J. and Treglown, A. The complexity of perfect matchings and packings in dense graphs and hypergraphs. Preprint.Google Scholar
[16] Han, J., Zang, C. and Zhao, Y. Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs. J. Combin. Theory Ser. A 149 115–147.Google Scholar
[17] Han, J. and Zhao, Y. (2015) Minimum degree thresholds for loose Hamilton cycle in 3-graphs. J. Combin. Theory Ser. B 114 70–96.CrossRefGoogle Scholar
[18] Han, J. and Zhao, Y. (2015) Minimum vertex degree threshold for C 4 3-tiling. J. Graph Theory 79 300–317.Google Scholar
[19] Hell, P. and Kirkpatrick, D. G. (1983) On the complexity of general graph factor problems. SIAM J. Comput. 12 601–609.Google Scholar
[20] Keevash, P. (2011) A hypergraph blow-up lemma. Random Struct. Alg. 39 275–376.Google Scholar
[21] Keevash, P. and Mycroft, R. (2014) A Geometric Theory for Hypergraph Matching, Vol. 233 of Memoirs of the American Mathematical Society, AMS.Google Scholar
[22] Khan, I. (2013) Perfect matchings in 3-uniform hypergraphs with large vertex degree. SIAM J. Discrete Math. 27 1021–1039.Google Scholar
[23] Khan, I. (2016) Perfect matchings in 4-uniform hypergraphs. J. Combin. Theory Ser. B 116 333–366.Google Scholar
[24] Komlós, J., Sárközy, G. and Szemerédi, E. (2001) Proof of the Alon–Yuster conjecture. Discrete Math. 235 255–269.Google Scholar
[25] 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
[26] Kühn, D. and Osthus, D. (2006) Multicolored Hamilton cycles and perfect matchings in pseudorandom graphs. SIAM J. Discrete Math. 20 273–286.Google Scholar
[27] Kühn, D. and Osthus, D. (2009) Embedding large subgraphs into dense graphs. In Surveys in Combinatorics 2009, Vol. 365 of London Math. Society Lecture Note Series, Cambridge University Press, pp. 137–167.Google Scholar
[28] Kühn, D. and Osthus, D. (2009) The minimum degree threshold for perfect graph packings. Combinatorica 29 65–107.Google Scholar
[29] Kühn, D., Osthus, D. and Treglown, A. (2013) Matchings in 3-uniform hypergraphs. J. Combin. Theory Ser. B 103 291–305.Google Scholar
[30] 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
[31] Lo, A. and Markström, K. (2015) F-factors in hypergraphs via absorption. Graphs Combin. 31 679–712.Google Scholar
[32] Mycroft, R. (2016) Packing k-partite k-uniform hypergraphs. J. Combin. Theory Ser. A 138 60–132.Google Scholar
[33] 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, Springer, pp. 561–590.CrossRefGoogle Scholar
[34] 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
[35] 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.CrossRefGoogle Scholar
[36] Szemerédi, E. (1978) Regular partitions of graphs. In Problèmes Combinatoires et Théorie des Graphes: Orsay 1976), Vol. 260 of Colloq. Internat. CNRS, CNRS, Paris, pp. 399–401.Google Scholar
[37] Treglown, A. and Zhao, Y. (2013) Exact minimum degree thresholds for perfect matchings in uniform hypergraphs II. J. Combin. Theory Ser. A 120 1463–1482.Google Scholar
[38] Treglown, A. and Zhao, Y. (2016) A note on perfect matchings in uniform hypergraphs. Electron. J. Combin. 23 #P1.16.Google Scholar
[39] Tutte, W. T. (1947) The factorization of linear graphs. J. London Math. Soc. 22 107–111.Google Scholar
[40] Zhao, Y. (2015) 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.Google Scholar