TRANSVERSAL HAMILTON CYCLE IN HYPERGRAPH SYSTEMS

Yangyang Cheng; Jie Han; Bin Wang; Guanghui Wang; Donglei Yang

doi:10.1137/23M1602425

TRANSVERSAL HAMILTON CYCLE IN HYPERGRAPH SYSTEMS

Yangyang Cheng, Jie Han, Bin Wang^*, Guanghui Wang, Donglei Yang

^*此作品的通讯作者

信息与电子学院

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

摘要

A k-graph system H = {Hi}_i∈[m_] is a family of not necessarily distinct k-graphs on the same n-vertex set V , and a k-graph H on V is said to be H-transversal provided that there exists an injection varp : E(H) \rightarrow [m] such that e ∊ E(H_\varphi₍e₎) for all e ∊ E(H). We show that given k ≥ 3, gamm > 0, sufficiently large n, and an n-vertex k-graph system H = {Hi}_i∈[n], if delt_k-₁(Hi) ≥ (1/2 + gamm)n for each i ∊ [n], then there exists an H-transversal tight Hamilton cycle. This extends the result of Rödl, Ruciński, and Szemerédi [Combinatorica, 28 (2008), pp. 229–260] on single k-graphs.

源语言	英语
页（从-至）	55-74
页数	20
期刊	SIAM Journal on Discrete Mathematics
卷	39
期	1
DOI	https://doi.org/10.1137/23M1602425
出版状态	已出版 - 2025

访问文件

10.1137/23M1602425

其它文件与链接

链接到 Scopus 的出版物

引用此

Cheng, Y., Han, J., Wang, B., Wang, G., & Yang, D. (2025). TRANSVERSAL HAMILTON CYCLE IN HYPERGRAPH SYSTEMS. SIAM Journal on Discrete Mathematics, 39(1), 55-74. https://doi.org/10.1137/23M1602425

@article{662c8ee8858f41679b2a2b4e2552db8b,

title = "TRANSVERSAL HAMILTON CYCLE IN HYPERGRAPH SYSTEMS",

abstract = "A k-graph system H = {Hi}i∈[m] is a family of not necessarily distinct k-graphs on the same n-vertex set V , and a k-graph H on V is said to be H-transversal provided that there exists an injection varp : E(H) \rightarrow [m] such that e ∊ E(H\varphi(e)) for all e ∊ E(H). We show that given k ≥ 3, gamm > 0, sufficiently large n, and an n-vertex k-graph system H = {Hi}i∈[n], if deltk-1(Hi) ≥ (1/2 + gamm)n for each i ∊ [n], then there exists an H-transversal tight Hamilton cycle. This extends the result of R{\"o}dl, Ruci{\'n}ski, and Szemer{\'e}di [Combinatorica, 28 (2008), pp. 229–260] on single k-graphs.",

keywords = "Hamilton cycle, k-graph system, transversal",

author = "Yangyang Cheng and Jie Han and Bin Wang and Guanghui Wang and Donglei Yang",

note = "Publisher Copyright: {\textcopyright} 2025 Society for Industrial and Applied Mathematics.",

year = "2025",

doi = "10.1137/23M1602425",

language = "English",

volume = "39",

pages = "55--74",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - TRANSVERSAL HAMILTON CYCLE IN HYPERGRAPH SYSTEMS

AU - Cheng, Yangyang

AU - Han, Jie

AU - Wang, Bin

AU - Wang, Guanghui

AU - Yang, Donglei

PY - 2025

Y1 - 2025

N2 - A k-graph system H = {Hi}i∈[m] is a family of not necessarily distinct k-graphs on the same n-vertex set V , and a k-graph H on V is said to be H-transversal provided that there exists an injection varp : E(H) \rightarrow [m] such that e ∊ E(H\varphi(e)) for all e ∊ E(H). We show that given k ≥ 3, gamm > 0, sufficiently large n, and an n-vertex k-graph system H = {Hi}i∈[n], if deltk-1(Hi) ≥ (1/2 + gamm)n for each i ∊ [n], then there exists an H-transversal tight Hamilton cycle. This extends the result of Rödl, Ruciński, and Szemerédi [Combinatorica, 28 (2008), pp. 229–260] on single k-graphs.

AB - A k-graph system H = {Hi}i∈[m] is a family of not necessarily distinct k-graphs on the same n-vertex set V , and a k-graph H on V is said to be H-transversal provided that there exists an injection varp : E(H) \rightarrow [m] such that e ∊ E(H\varphi(e)) for all e ∊ E(H). We show that given k ≥ 3, gamm > 0, sufficiently large n, and an n-vertex k-graph system H = {Hi}i∈[n], if deltk-1(Hi) ≥ (1/2 + gamm)n for each i ∊ [n], then there exists an H-transversal tight Hamilton cycle. This extends the result of Rödl, Ruciński, and Szemerédi [Combinatorica, 28 (2008), pp. 229–260] on single k-graphs.

KW - Hamilton cycle

KW - k-graph system

KW - transversal

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

U2 - 10.1137/23M1602425

DO - 10.1137/23M1602425

M3 - Article

AN - SCOPUS:85215014415

SN - 0895-4801

VL - 39

SP - 55

EP - 74

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -

TRANSVERSAL HAMILTON CYCLE IN HYPERGRAPH SYSTEMS

摘要

访问文件

其它文件与链接

指纹

引用此