2023/01/31 by Yucong Tang, Bin Wang, Tang, Yucong +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2302.00080
openalex publication_date 2023/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we develop a new rainbow Hamilton framework, which is of independent interest, settling the problem proposed by Gupta, Hamann, Müyesser, Parczyk, and Sgueglia when k=3, and draw the general conclusion for any k≥3 as follows. A k-graph system H=\Hi\i∈[n] is a family of not necessarily distinct k-graphs on the same n-vertex set V, moreover, a k-graph H on V is rainbow if E(H)⊆ \bigcupi∈[n]E(Hi) and |E(H)∩ E(Hi)|≤1 for i∈[n]. We show that given γ> 0, sufficiently large n and an n-vertex k-graph system H=\Hi\i∈[n] , if δk-2(Hi)≥(5/9+γ)\binomn2 for i∈[n] where k≥3, then there exists a rainbow tight Hamilton cycle. This result implies the conclusion in a single graph, which was proved by Lang and Sanhueza-Matamala [J. Lond. Math. Soc., 2022], Polcyn, Reiher, Rödl and Schülke [J. Combin. Theory Ser. B, 2021] independently.