# 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 :
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.273-278, 2005, DMTCS Proceedings
Domaine :

Littérature citée [12 références]

https://hal.inria.fr/hal-01184446
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 14:59:19
Dernière modification le : jeudi 11 mai 2017 - 01:02:52
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 11:13:36

### Fichier

dmAE0154.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01184446, version 1

### Citation

Daniela Kühn, Deryk Osthus. Matchings and Hamilton cycles in hypergraphs. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.273-278, 2005, DMTCS Proceedings. 〈hal-01184446〉

### Métriques

Consultations de la notice

## 330

Téléchargements de fichiers