Nearly perfect matchings in regular simple hypergraphs |
| |
Authors: | Noga Alon Jeong-Han Kim Joel Spencer |
| |
Affiliation: | (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 等数据库收录! |
|