TRANSVERSAL HAMILTON CYCLE IN HYPERGRAPH SYSTEMS

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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ödl, Ruciński, and Szemerédi [Combinatorica, 28 (2008), pp. 229–260] on single k-graphs.

Original languageEnglish
Pages (from-to)55-74
Number of pages20
JournalSIAM Journal on Discrete Mathematics
Volume39
Issue number1
DOIs
Publication statusPublished - 2025

Keywords

  • Hamilton cycle
  • k-graph system
  • transversal

Fingerprint

Dive into the research topics of 'TRANSVERSAL HAMILTON CYCLE IN HYPERGRAPH SYSTEMS'. Together they form a unique fingerprint.

Cite this

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