Transversal Hamilton cycle in the hypergraph system

Yucong Tang; Bin Wang; Guanghui Wang; Guiying Yan

doi:10.1007/s11425-024-2469-2

Transversal Hamilton cycle in the hypergraph system

Yucong Tang
, Bin Wang^*
, Guanghui Wang
, Guiying Yan

^*Corresponding author for this work

Nanjing University of Aeronautics and Astronautics
Beijing Institute of Technology
Shandong University
CAS - Academy of Mathematics and System Sciences

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

Abstract

In this paper, we develop a sequential Hamilton framework, which is of independent interest, settling the problem proposed by Gupta et al. (2023) when k = 3, and draw the general conclusion for any k ⩾ 3 as follows. A k-graph system H = {H_i}_i∈[m] is a family of not necessarily distinct k-graphs on the same n-vertex set V; moreover, a k-graph H on V with m edges is transversal in H if there is a bijection φ: E(H) → [m] such that e ∈ E(H_φ(e)) for each e ∈ E(H). We show that given γ > 0, k ⩾ 3, sufficiently large n and an n-vertex k-graph system H = {H_i}_i∈[n], if δk−2(Hi)⩾(5/9+γ)(n2) for i ∈ [n], then there exists a tight Hamilton cycle which is transversal in H. This result implies the conclusion in a single graph, which was proved by Lang and Sanhueza-Matamala (2022) and Polcyn et al. (2021) independently.

Original language	English
Journal	Science China Mathematics
DOIs	https://doi.org/10.1007/s11425-024-2469-2
Publication status	Accepted/In press - 2026
Externally published	Yes

Keywords

05C35
05C65
k-graph system
sequential Hamilton framework
transversal Hamilton cycle

Access to Document

10.1007/s11425-024-2469-2

Cite this

@article{016044aa1bad432bb9ee20fd0376aedc,

title = "Transversal Hamilton cycle in the hypergraph system",

abstract = "In this paper, we develop a sequential Hamilton framework, which is of independent interest, settling the problem proposed by Gupta et al. (2023) when k = 3, and draw the general conclusion for any k ⩾ 3 as follows. A k-graph system H = \{Hi\}i∈[m] is a family of not necessarily distinct k-graphs on the same n-vertex set V; moreover, a k-graph H on V with m edges is transversal in H if there is a bijection φ: E(H) → [m] such that e ∈ E(Hφ(e)) for each e ∈ E(H). We show that given γ > 0, k ⩾ 3, sufficiently large n and an n-vertex k-graph system H = \{Hi\}i∈[n], if δk−2(Hi)⩾(5/9+γ)(n2) for i ∈ [n], then there exists a tight Hamilton cycle which is transversal in H. This result implies the conclusion in a single graph, which was proved by Lang and Sanhueza-Matamala (2022) and Polcyn et al. (2021) independently.",

keywords = "05C35, 05C65, k-graph system, sequential Hamilton framework, transversal Hamilton cycle",

author = "Yucong Tang and Bin Wang and Guanghui Wang and Guiying Yan",

note = "Publisher Copyright: {\textcopyright} Science China Press 2026.",

year = "2026",

doi = "10.1007/s11425-024-2469-2",

language = "English",

journal = "Science China Mathematics",

issn = "1674-7283",

publisher = "Science China Press",

}

TY - JOUR

T1 - Transversal Hamilton cycle in the hypergraph system

AU - Tang, Yucong

AU - Wang, Bin

AU - Wang, Guanghui

AU - Yan, Guiying

N1 - Publisher Copyright: © Science China Press 2026.

PY - 2026

Y1 - 2026

N2 - In this paper, we develop a sequential Hamilton framework, which is of independent interest, settling the problem proposed by Gupta et al. (2023) when k = 3, and draw the general conclusion for any k ⩾ 3 as follows. A k-graph system H = {Hi}i∈[m] is a family of not necessarily distinct k-graphs on the same n-vertex set V; moreover, a k-graph H on V with m edges is transversal in H if there is a bijection φ: E(H) → [m] such that e ∈ E(Hφ(e)) for each e ∈ E(H). We show that given γ > 0, k ⩾ 3, sufficiently large n and an n-vertex k-graph system H = {Hi}i∈[n], if δk−2(Hi)⩾(5/9+γ)(n2) for i ∈ [n], then there exists a tight Hamilton cycle which is transversal in H. This result implies the conclusion in a single graph, which was proved by Lang and Sanhueza-Matamala (2022) and Polcyn et al. (2021) independently.

AB - In this paper, we develop a sequential Hamilton framework, which is of independent interest, settling the problem proposed by Gupta et al. (2023) when k = 3, and draw the general conclusion for any k ⩾ 3 as follows. A k-graph system H = {Hi}i∈[m] is a family of not necessarily distinct k-graphs on the same n-vertex set V; moreover, a k-graph H on V with m edges is transversal in H if there is a bijection φ: E(H) → [m] such that e ∈ E(Hφ(e)) for each e ∈ E(H). We show that given γ > 0, k ⩾ 3, sufficiently large n and an n-vertex k-graph system H = {Hi}i∈[n], if δk−2(Hi)⩾(5/9+γ)(n2) for i ∈ [n], then there exists a tight Hamilton cycle which is transversal in H. This result implies the conclusion in a single graph, which was proved by Lang and Sanhueza-Matamala (2022) and Polcyn et al. (2021) independently.

KW - 05C35

KW - 05C65

KW - k-graph system

KW - sequential Hamilton framework

KW - transversal Hamilton cycle

UR - https://www.scopus.com/pages/publications/105028207078

U2 - 10.1007/s11425-024-2469-2

DO - 10.1007/s11425-024-2469-2

M3 - Article

AN - SCOPUS:105028207078

SN - 1674-7283

JO - Science China Mathematics

JF - Science China Mathematics

ER -

Transversal Hamilton cycle in the hypergraph system

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this