Daniela Kühn ; Deryk Osthus
-
Matchings and Hamilton cycles in hypergraphs
dmtcs:3457 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
-
https://doi.org/10.46298/dmtcs.3457
Matchings and Hamilton cycles in hypergraphsConference paper
Authors: Daniela Kühn 1; Deryk Osthus 1
NULL##NULL
Daniela Kühn;Deryk Osthus
1 School of Mathematics [Birmingham]
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.