Nearly perfect matchings in regular simple hypergraphs

• DOI: 10.1007/bf02773639
• Publication Date: 2007-12-11T19:34:01Z
• Authors: Noga Alon; Jeong-Han Kim; Joel Spencer
• Keywords: Hypergraph

For every fixedk≥3 there exists a constantc k with the following property. LetH be ak-uniform,D-regular hypergraph onN vertices, in which no two edges contain more than one common vertex. Ifk>3 thenH contains a matching covering all vertices but at mostc k ND −1/(k−1). Ifk=3, thenH contains a matching covering all vertices but at mostc 3 ND −1/2ln3/2 D. This improves previous estimates and implies, for example, that any Steiner Triple System onN vertices contains a matching covering all vertices but at mostO(N 1/2ln3/2 N), improving results by various authors.