Hamilton ℓ-cycles in uniform hypergraphs

We say that a k-uniform hypergraph C is an ℓ- cycle if there exists a cyclic ordering of the vertices of C such that every edge of C consists of k consecutive vertices and such that every pair of consecutive edges (in the natural ordering of the edges) intersects in precisely ℓ vertices. We prove th...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series A 2010-10, Vol.117 (7), p.910-927
Main Authors: Kühn, Daniela, Mycroft, Richard, Osthus, Deryk
Format: Article
Language:English
Subjects:
Hamilton cycles
Hypergraphs
Regularity lemma
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We say that a k-uniform hypergraph C is an ℓ- cycle if there exists a cyclic ordering of the vertices of C such that every edge of C consists of k consecutive vertices and such that every pair of consecutive edges (in the natural ordering of the edges) intersects in precisely ℓ vertices. We prove that if 1 ⩽ ℓ < k and k − ℓ does not divide k then any k-uniform hypergraph on n vertices with minimum degree at least n ⌈ k k − ℓ ⌉ ( k − ℓ ) + o ( n ) contains a Hamilton ℓ-cycle. This confirms a conjecture of Hàn and Schacht. Together with results of Rödl, Ruciński and Szemerédi, our result asymptotically determines the minimum degree which forces an ℓ-cycle for any ℓ with 1 ⩽ ℓ < k .
ISSN:0097-3165
1096-0899
DOI:10.1016/j.jcta.2010.02.010