Skip to Main content Skip to Navigation
Conference papers

Matchings and Hamilton cycles in hypergraphs

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 $\varepsilon > 0$ there is an $n_0$ such that every $3$-uniform hypergraph of order $n \geq n_0$ whose minimum degree is at least $n/4+ \varepsilon n$ contains a Hamilton cycle. Our bounds on the minimum degree are essentially best possible.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 2:59:19 PM
Last modification on : Thursday, May 11, 2017 - 1:02:52 AM
Long-term archiving on: : Sunday, November 15, 2015 - 11:13:36 AM


Publisher files allowed on an open archive


  • HAL Id : hal-01184446, version 1



Daniela Kühn, Deryk Osthus. Matchings and Hamilton cycles in hypergraphs. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.273-278. ⟨hal-01184446⟩



Record views


Files downloads