2025/01/02 by Yangyang Cheng, Heng Li, Cheng, Yangyang +5
#05C20 #05C38 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2501.00998
Given a collection D =\D1,D2,…,Dm\ of digraphs on the common vertex set V, an m-edge digraph H with vertices in V is transversal in D if there exists a bijection φ:E(H)→ [m] such that e ∈ E(Dφ(e)) for all e∈ E(H). Ghouila-Houri proved that any n-vertex digraph with minimum semi-degree at least (n)/(2) contains a directed Hamilton cycle. In this paper, we provide a transversal generalization of Ghouila-Houri's theorem, thereby solving a problem proposed by Chakraborti, Kim, Lee and Seo \cite2023Tournament. Our proof utilizes the absorption method for transversals, the regularity method for digraph collections, as well as the transversal blow-up lemma \citecheng2023transversals and the related machinery. As an application, when n is sufficiently large, our result implies the transversal version of Dirac's theorem, which was proved by Joos and Kim \cite2021jooskim.