Packing tight hamilton cycles in uniform hypergraphs

Deepak Bal, Alan Frieze

Research output: Contribution to journalArticleResearchpeer-review

7 Citations (Scopus)

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

Fingerprint

Hamilton Cycle
Uniform Hypergraph
Hypergraph
Packing
Consecutive
Decompose
Class

Keywords

  • Hamilton cycles
  • Packings
  • Pseudorandom hypergraphs

Cite this

@article{f19fffe2154b4c5ebbb950e1458263b5,
title = "Packing tight hamilton cycles in uniform hypergraphs",
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.",
keywords = "Hamilton cycles, Packings, Pseudorandom hypergraphs",
author = "Deepak Bal and Alan Frieze",
year = "2012",
month = "9",
day = "6",
doi = "10.1137/11082378X",
language = "English",
volume = "26",
pages = "435--451",
journal = "SIAM Journal on Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "2",

}

Packing tight hamilton cycles in uniform hypergraphs. / Bal, Deepak; Frieze, Alan.

In: SIAM Journal on Discrete Mathematics, Vol. 26, No. 2, 06.09.2012, p. 435-451.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Packing tight hamilton cycles in uniform hypergraphs

AU - Bal, Deepak

AU - Frieze, Alan

PY - 2012/9/6

Y1 - 2012/9/6

N2 - 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.

AB - 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.

KW - Hamilton cycles

KW - Packings

KW - Pseudorandom hypergraphs

UR - http://www.scopus.com/inward/record.url?scp=84865623415&partnerID=8YFLogxK

U2 - 10.1137/11082378X

DO - 10.1137/11082378X

M3 - Article

VL - 26

SP - 435

EP - 451

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 2

ER -