Forbidding Hamilton cycles in uniform hypergraphs

Jie Han, Yi Zhao

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)

Abstract

For 1 ≤ d≤ ℓ < k, we give a new lower bound for the minimum d-degree threshold that guarantees a Hamilton ℓ-cycle in k-uniform hypergraphs. When k≥. 4 and d< ℓ = k - 1, this bound is larger than the conjectured minimum d-degree threshold for perfect matchings and thus disproves a well-known conjecture of Rödl and Ruciński. Our (simple) construction generalizes a construction of Katona and Kierstead and the space barrier for Hamilton cycles.

Original languageEnglish
Pages (from-to)107-115
Number of pages9
JournalJournal of Combinatorial Theory. Series A
Volume143
DOIs
Publication statusPublished - 1 Oct 2016
Externally publishedYes

Keywords

  • Hamilton cycles
  • Hypergraphs
  • Perfect matchings

Fingerprint

Dive into the research topics of 'Forbidding Hamilton cycles in uniform hypergraphs'. Together they form a unique fingerprint.

Cite this