Forbidding Hamilton cycles in uniform hypergraphs

Jie Han; Yi Zhao

doi:10.1016/j.jcta.2016.05.005

Forbidding Hamilton cycles in uniform hypergraphs

Jie Han, Yi Zhao

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	107-115
Number of pages	9
Journal	Journal of Combinatorial Theory. Series A
Volume	143
DOIs	https://doi.org/10.1016/j.jcta.2016.05.005
Publication status	Published - 1 Oct 2016
Externally published	Yes

Keywords

Hamilton cycles
Hypergraphs
Perfect matchings

Access to Document

10.1016/j.jcta.2016.05.005

Cite this

Han, J., & Zhao, Y. (2016). Forbidding Hamilton cycles in uniform hypergraphs. Journal of Combinatorial Theory. Series A, 143, 107-115. https://doi.org/10.1016/j.jcta.2016.05.005

@article{2d4f55d691244386abe2b969d7dcd77a,

title = "Forbidding Hamilton cycles in uniform hypergraphs",

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{\"o}dl and Ruci{\'n}ski. Our (simple) construction generalizes a construction of Katona and Kierstead and the space barrier for Hamilton cycles.",

keywords = "Hamilton cycles, Hypergraphs, Perfect matchings",

author = "Jie Han and Yi Zhao",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier Inc.",

year = "2016",

month = oct,

day = "1",

doi = "10.1016/j.jcta.2016.05.005",

language = "English",

volume = "143",

pages = "107--115",

journal = "Journal of Combinatorial Theory. Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Forbidding Hamilton cycles in uniform hypergraphs

AU - Han, Jie

AU - Zhao, Yi

PY - 2016/10/1

Y1 - 2016/10/1

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

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

KW - Hamilton cycles

KW - Hypergraphs

KW - Perfect matchings

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

U2 - 10.1016/j.jcta.2016.05.005

DO - 10.1016/j.jcta.2016.05.005

M3 - Article

AN - SCOPUS:84975687789

SN - 0097-3165

VL - 143

SP - 107

EP - 115

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

ER -

Forbidding Hamilton cycles in uniform hypergraphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this