Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4654951 | European Journal of Combinatorics | 2006 | 17 Pages |
Abstract
A perfect matching in a kk-uniform hypergraph on nn vertices, nn divisible by kk, is a set of n/kn/k disjoint edges. In this paper 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≥3k≥3 and sufficiently large nn, a perfect matching exists in every nn-vertex kk-uniform hypergraph in which each set of k−1k−1 vertices is contained in n/2+Ω(logn)n/2+Ω(logn) edges. Owing to a construction in [D. Kühn, D. Osthus, Matchings in hypergraphs of large minimum degree, J. Graph Theory 51 (1) (2006) 269–280], this is nearly optimal. For almost perfect and fractional perfect matchings we show that analogous thresholds are close to n/kn/k rather than n/2n/2.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Vojtech Rödl, Andrzej Ruciński, Endre Szemerédi,