Transversal Hamilton cycle in hypergraph systems

2021/11/13 by Yangyang Cheng, Cheng, Yangyang, Jie Han +7 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics #Combinatorics (math.CO) #Discrete mathematics #FOS: Mathematics #Graph #Hypergraph #Limits and Structures in Graph Theory #Mathematical analysis #Mathematics #Physics #Transversal (combinatorics) #Vertex (graph theory)

paper · pdf · doi:10.48550/arxiv.2111.07079

openalex publication_date 2021/11/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 and a k-graph H on V is said to be H-transversal provided that there exists an injection φ: E(H)→ [m] such that e∈ E(H_φ(e)) for all e∈ E(H). We show that given k≥3, γ>0, sufficiently large n and an n-vertex k-graph system H=\H_i\_i∈[n], if δ_k-1(H_i)≥(1/2+γ)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, 2008] on single k-graphs.

Citations

• Some Theorems on Abstract Graphs
• On Hamiltonian bipartite graphs
• Tight co-degree condition for the existence of loose Hamilton cycles in 3-graphs
• A better bound on the size of rainbow matchings
• On a rainbow version of Dirac's theorem
• Global hypercontractivity and its applications
• Rainbow spanning structures in graph and hypergraph systems

Cited by

• Transversal packings in families of percolated hypergraphs

Related

• Hamilton transversals in tournaments
• From one to many rainbow Hamiltonian cycles
• Transversal Hamilton paths and cycles
• Stability of transversal Hamilton cycles and paths
• Transversal Hamilton Paths and Cycles