2024/07/19 by Debsoumya Chakraborti, Chakraborti, Debsoumya, Jaehoon Kim +5
Decision Sciences · Computer Science · #Game Theory and Applications #Artificial Intelligence in Games
paper · pdf · doi:10.48550/arxiv.2407.14300
Thomason [Trans. Amer. Math. Soc. 296.1 (1986)] proved that every sufficiently large tournament contains Hamilton paths and cycles with all possible orientations, except possibly the consistently oriented Hamilton cycle. This paper establishes transversal generalizations of these classical results. For a collection T=\T1,…,Tm\ of not-necessarily distinct tournaments on the common vertex set V, an m-edge directed subgraph D with the vertices in V is called a transversal if there exists an bijection φ\colon E(D)→ [m] such that e∈ E(Tφ(e)) for all e∈ E(D). We prove that for sufficiently large n, there exist transversal Hamilton cycles of all possible orientations possibly except the consistently oriented one. We also obtain a similar result for the transversal Hamilton paths of all possible orientations. These results generalize the classical theorem of Thomason, and our approach provides another proof of this theorem.