Hostname: page-component-745bb68f8f-b6zl4 Total loading time: 0 Render date: 2025-02-06T20:06:42.788Z Has data issue: false hasContentIssue false
  • English
  • Français

Near Perfect Matchings in k-Uniform Hypergraphs

Published online by Cambridge University Press:  02 October 2014

JIE HAN
JIE HAN*
Affiliation:
Georgia State University, Atlanta, GA 30303, USA (e-mail: jhan22@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.

Let H be a k-uniform hypergraph on n vertices where n is a sufficiently large integer not divisible by k. We prove that if the minimum (k − 1)-degree of H is at least ⌊n/k⌋, then H contains a matching with ⌊n/k⌋ edges. This confirms a conjecture of Rödl, Ruciński and Szemerédi [13], who proved that minimum (k − 1)-degree n/k + O(log n) suffices. More generally, we show that H contains a matching of size d if its minimum codegree is d < n/k, which is also best possible.

Keywords

Primary 05C70Secondary 05C50
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Issue 5 , September 2015 , pp. 723 - 732
Copyright
Copyright © Cambridge University Press 2014 

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.CrossRefGoogle Scholar
[2] Czygrinow, A. and Kamat, V. (2012) Tight co-degree condition for perfect matchings in 4-graphs. Electron. J. Combin. 19 #20.CrossRefGoogle Scholar
[3] Hàn, H., Person, Y. and Schacht, M. (2009) On perfect matchings in uniform hypergraphs with large minimum vertex degree. SIAM J. Discrete Math 23 732–748.CrossRefGoogle Scholar
[4] Khan, I. Perfect matchings in 4-uniform hypergraphs. arXiv:1101.5675 Google Scholar
[5] Khan, I. (2013) Perfect matchings in 3-uniform hypergraphs with large vertex degree. SIAM J. Discrete Math. 27 1021–1039.CrossRefGoogle Scholar
[6] Kühn, D. and Osthus, D. (2006) Matchings in hypergraphs of large minimum degree. J. Graph Theory 51 269–280.CrossRefGoogle Scholar
[7] Kühn, D., Osthus, D. and Treglown, A. (2013) Matchings in 3-uniform hypergraphs. J. Combin. Theory Ser. B 103 291–305.CrossRefGoogle Scholar
[8] Markström, K. and Ruciński, A. (2011) Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees. Europ. J. Combin. 32 677–687.CrossRefGoogle Scholar
[9] Pikhurko, O. (2008) Perfect matchings and K 3 4-tilings in hypergraphs of large codegree. Graphs Combin. 24 391–404.CrossRefGoogle Scholar
[10] 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 (Bárány, I. and Solymosi, J., eds), Vol. 21 of Bolyai Society Mathematical Studies, pp. 561–590.CrossRefGoogle Scholar
[11] 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.CrossRefGoogle Scholar
[12] Rödl, V., Ruciński, A. and Szemerédi, E. (2006) Perfect matchings in uniform hypergraphs with large minimum degree. Europ. J. Combin. 27 1333–1349.CrossRefGoogle Scholar
[13] 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
[14] 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.CrossRefGoogle Scholar