Matchings and Hamilton cycles in hypergraphs
Daniela Kühn, Deryk Osthus
Abstract
It is well known that every bipartite graph with vertex classes of size n whose minimum degree is at least n/2 contains a perfect matching. We prove an analogue of this result for uniform hypergraphs. We also provide an analogue of Dirac's theorem on Hamilton cycles for 3-uniform hypergraphs: We say that a 3-uniform hypergraph has a Hamilton cycle if there is a cyclic ordering of its vertices such that every pair of consecutive vertices lies in a hyperedge which consists of three consecutive vertices. We prove that for every ε> 0 there is an n0 such that every 3-uniform hypergraph of order n ≥n0 whose minimum degree is at least n/4+εn contains a Hamilton cycle. Our bounds on the minimum degree are essentially best possible.
Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page