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

科研成果: 期刊稿件 › 文章 › 同行评审

14 引用（Scopus）

摘要

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.

源语言	英语
页（从-至）	107-115
页数	9
期刊	Journal of Combinatorial Theory. Series A
卷	143
DOI	https://doi.org/10.1016/j.jcta.2016.05.005
出版状态	已出版 - 1 10月 2016
已对外发布	是

访问文件

10.1016/j.jcta.2016.05.005

其它文件与链接

链接到 Scopus 的出版物

引用此

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

摘要

访问文件

其它文件与链接

指纹

引用此