Transversal Hamilton Cycles in Digraph Collections
The transversal generalization of the Ghouila-Houri theorem: for sufficiently large n, any collection D = {D1,...,Dn} of digraphs on a common n-vertex set whose minimum semi-degree satisfies delta0(D) >= n/2 contains a transversal directed Hamilton cycle -- a directed Hamilton cycle whose n arcs are drawn bijectively, one from each Di. The result solves a problem of Chakraborti, Kim, Lee and Seo, and implies both Ghouila-Houri's theorem (all Di equal) and the transversal Dirac theorem of Joos and Kim. The proof combines the absorption method for transversals, the regularity method for digraph collections, and the transversal blow-up lemma.
Transversal Hamilton cycles in digraph collections Yangyang Cheng∗ Heng Li † Wanting Sun ‡ Guanghui
Primary research in extremal combinatorics (Cheng, Li, Sun, Wang). Given a collection D = {D1,...,Dm} of digraphs on a common vertex set, a digraph H is transversal in D if its edges can be matched b…