Matchings in 3-uniform hypergraphs

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 (n−12)−(2n/32), then H contains a perfect m...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series B 2013-03, Vol.103 (2), p.291-305
Main Authors: Kühn, Daniela, Osthus, Deryk, Treglown, Andrew
Format: Article
Language:English
Subjects:
Hypergraphs
Perfect matchings
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 (n−12)−(2n/32), then H contains a perfect matching. This bound is tight and answers a question of Hàn, Person and Schacht. More generally, we show that H contains a matching of size d⩽n/3 if its minimum vertex degree is greater than (n−12)−(n−d2), which is also best possible. This extends a result of Bollobás, Daykin and Erdős.
ISSN:0095-8956
1096-0902
DOI:10.1016/j.jctb.2012.11.005