
arXiv: 1009.1298
We determine the minimum vertex degree that ensures a perfect matching in a 3-uniform hypergraph. More precisely, suppose that H is a sufficiently large 3-uniform hypergraph whose order n is divisible by 3. If the minimum vertex degree of H is greater than \binom{n-1}{2}-\binom{2n/3}{2}, then H contains a perfect matching. This bound is tight and answers a question of Han, Person and Schacht. More generally, we show that H contains a matching of size d\le n/3 if its minimum vertex degree is greater than \binom{n-1}{2}-\binom{n-d}{2}, which is also best possible. This extends a result of Bollobas, Daykin and Erdos.
18 pages, 1 figure. To appear in JCTB
Computational Theory and Mathematics, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Combinatorics (math.CO), 05C35, 05C65, 05C70, Theoretical Computer Science
Computational Theory and Mathematics, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Combinatorics (math.CO), 05C35, 05C65, 05C70, Theoretical Computer Science
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 55 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
