×

Perfect matchings in uniform hypergraphs with large minimum degree. (English) Zbl 1104.05051

Summary: A perfect matching in a \(k\)-uniform hypergraph on \(n\) vertices, \(n\) divisible by \(k\), is a set of \(n/k\) disjoint edges. We give a sufficient condition for the existence of a perfect matching in terms of a variant of the minimum degree. We prove that for every \(k\geq 3\) and sufficiently large \(n\), a perfect matching exists in every \(n\)-vertex \(k\)-uniform hypergraph in which each set of \(k - 1\) vertices is contained in \(n/2+\Omega (log n)\) edges. Owing to a construction in [D. Kühn and D. Osthus, J. Graph Theory 51, 269–280 (2006; Zbl 1087.05041)], this is nearly optimal. For almost perfect and fractional perfect matchings we show that analogous thresholds are close to \(n/k\) rather than \(n/2\).

MSC:

05C65 Hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 1087.05041
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Rödl, V.; Ruciński, A., Perfect matchings in \(\epsilon \)-regular graphs, Electron. J. Combin., 5, 1, #R13 (1998) · Zbl 0886.05088
[2] Alon, N.; Spencer, J., The Probabilistic Method (2000), John Wiley and Sons: John Wiley and Sons New York
[3] Chvátal, V., Linear Programming (1983), W.H. Freeman: W.H. Freeman New York · Zbl 0318.05002
[4] Erdős, P.; Ko, C.; Rado, R., Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser., 12, 313-320 (1961) · Zbl 0100.01902
[5] Janson, S.; Łuczak, T.; Ruciński, A., Random Graphs (2000), John Wiley and Sons: John Wiley and Sons New York
[6] Katona, G. Y.; Kierstead, H. A., Hamiltonian chains in hypergraphs, J. Graph Theory, 30, 205-212 (1999) · Zbl 0924.05050
[7] Kühn, D.; Osthus, D., Matchings in hypergraphs of large minimum degree, J. Graph Theory, 51, 1, 269-280 (2006) · Zbl 1087.05041
[8] Lovász, L.; Plummer, M. D., Matching theory, (North-Holland Mathematics Studies 121. North-Holland Mathematics Studies 121, Annals of Discrete Mathematics, vol. 29 (1986), North-Holland Publishing Co., Amsterdam: North-Holland Publishing Co., Amsterdam Akadémiai Kiadó, Budapest) · Zbl 0618.05001
[9] Rödl, V.; Ruciński, A., Perfect matching in \(\epsilon \)-regular graphs and the blow-up lemma, Combinatorica, 19, 3, 437-452 (1999) · Zbl 0932.05080
[10] Rödl, V.; Ruciński, A.; Szeméredi, E., A Dirac-type theorem for 3-uniform hypergraphs, Combinatorics, Probability, and Computing, 15, 1-2, 229-251 (2006) · Zbl 1082.05057
[11] V. Rödl, A. Ruciński, E. Szeméredi, Dirac theorem for 3-uniform hypergraphs, work in progress; V. Rödl, A. Ruciński, E. Szeméredi, Dirac theorem for 3-uniform hypergraphs, work in progress
[12] V. Rödl, A. Ruciński, E. Szeméredi, Perfect matchings in uniform hypergraphs with large minimum degree. II, work in progress; V. Rödl, A. Ruciński, E. Szeméredi, Perfect matchings in uniform hypergraphs with large minimum degree. II, work in progress
[13] V. Rödl, A. Ruciński, E. Szeméredi, An approximative Dirac-type theorem for \(k\); V. Rödl, A. Ruciński, E. Szeméredi, An approximative Dirac-type theorem for \(k\)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.