Article ID Journal Published Year Pages File Type
4654951 European Journal of Combinatorics 2006 17 Pages PDF
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
, , ,