Packing tight hamilton cycles in uniform hypergraphs

Deepak Bal, Alan Frieze

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

We say that a k-uniform hypergraph C is a Hamilton cycle of type l, for some 1 ≤ l ≤ k, if there exists a cyclic ordering of the vertices of C such that every edge consists of k consecutive vertices, and for every pair of consecutive edges E i-1\E i in C (in the natural ordering of the edges) we have |E i-1 \ E i| = l. We define a class of (ε, p)-regular hypergraphs, that includes random hypergraphs, for which we can prove the existence of a decomposition of almost all edges into type l Hamilton cycles, where l < k/2.

Original languageEnglish
Pages (from-to)435-451
Number of pages17
JournalSIAM Journal on Discrete Mathematics
Volume26
Issue number2
DOIs
StatePublished - 6 Sep 2012

Keywords

  • Hamilton cycles
  • Packings
  • Pseudorandom hypergraphs

Fingerprint Dive into the research topics of 'Packing tight hamilton cycles in uniform hypergraphs'. Together they form a unique fingerprint.

Cite this