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 language | English (US) |
|---|---|
| Pages (from-to) | 171-187 |
| Number of pages | 17 |
| Journal | Israel Journal of Mathematics |
| Volume | 100 |
| DOIs | |
| State | Published - 1997 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- General Mathematics