DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Matchings and Hamilton cycles in hypergraphs

Daniela Kühn, Deryk Osthus


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

Valid XHTML 1.0 Transitional