Matchings and Hamilton cycles in hypergraphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2005

Matchings and Hamilton cycles in hypergraphs

Résumé

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.
Fichier principal
Vignette du fichier
dmAE0154.pdf (158.82 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01184446 , version 1 (14-08-2015)

Identifiants

Citer

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⟩

Collections

TDS-MACS
178 Consultations
598 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More