Nearly perfect matchings in regular simple hypergraphs |
| |
| Authors: | Noga Alon Jeong-Han Kim Joel Spencer |
| |
| Institution: | (1) AT & T Bell Labs, 07974 Murray Hill, NJ, USA;(2) Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel;(3) Department of Mathematics and Computer Science, Courant Institute, NYU, NY, USA |
| |
| Abstract: | 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.
Research supported in part by a USA-Israel BSF grant.
Research supported in part by a USA-Israel BSF Grant. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
