Loading [MathJax]/jax/output/HTML-CSS/jax.js

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

  • 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 nn0 whose minimum degree is at least n/4+εn contains a Hamilton cycle. Our bounds on the minimum degree are essentially best possible.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: matchings,Hamilton cycles,packings,uniform hypergraphs,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]

Consultation statistics

This page has been seen 287 times.
This article's PDF has been downloaded 374 times.