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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [12 references]

https://hal.inria.fr/hal-01184446
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
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

File

dmAE0154.pdf
Publisher files allowed on an open archive

Citation

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, ⟨10.46298/dmtcs.3457⟩. ⟨hal-01184446⟩

Record views