Matchings and Hamilton cycles in hypergraphsReportar como inadecuado

Matchings and Hamilton cycles in hypergraphs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 School of Mathematics Birmingham

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 : matchings Hamilton cycles packings uniform hypergraphs

Autor: Daniela Kühn - Deryk Osthus -



Documentos relacionados