Nearly perfect matchings in regular simple hypergraphs

Noga Alon, Jeong Han Kim, Joel Spencer

Research output: Contribution to journalArticlepeer-review

53 Scopus citations

Abstract

For every fixed k ≥ 3 there exists a constant ck with the following property. Let H be a k-uniform, D-regular hypergraph on N vertices, in which no two edges contain more than one common vertex. If k > 3 then H contains a matching covering all vertices but at most ckND-1/(k-1). If k = 3, then H contains a matching covering all vertices but at most c3ND-1/2ln3/2D. This improves previous estimates and implies, for example, that any Steiner Triple System on N vertices contains a matching covering all vertices but at most 0(N1/2ln3/2N), improving results by various authors.

Original languageEnglish (US)
Pages (from-to)171-187
Number of pages17
JournalIsrael Journal of Mathematics
Volume100
DOIs
StatePublished - Jan 1 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Nearly perfect matchings in regular simple hypergraphs'. Together they form a unique fingerprint.

Cite this