Transversal Hamilton cycles in digraph collections

Source abstract

Abstract Given a collection script upper D equals StartSet upper D 1 comma upper D 2 comma ellipsis comma upper D Subscript m Baseline EndSet D = { D 1 , D 2 , … , D m } $\mathcal{D} =\{D_1,D_2,\ldots ,D_m\}$ of digraphs on the common vertex set upper V V $V$ , an m m $m$ -edge digraph upper H H $H$ with vertices in upper V V $V$ is transversal in script upper D D $\mathcal{D}$ if there exists a bijection phi colon upper E left parenthesis upper H right parenthesis right arrow left bracket m right bracket φ : E ( H ) → [ m ] $\varphi \,:\,E(H)\rightarrow [m]$ such that e element of upper E left parenthesis upper D Subscript phi left parenthesis e right parenthesis Baseline right parenthesis e ∈ E ( D φ ( e ) ) $e \in E(D_{\varphi (e)})$ for all e element of upper E left parenthesis upper H right parenthesis e ∈ E ( H ) $e\in E(H)$ . Ghouila-Houri proved that any n n $n$ -vertex digraph with minimum semi-degree at least StartFraction n Over 2 EndFraction n 2 $\frac {n}{2}$ contains a directed Hamilton cycle. In this paper, we provide a transversal generalisation of Ghouila-Houri’s theorem, thereby solving a problem proposed by Chakraborti, Kim, Lee, and Seo. Our proof utilises the absorption method for transversals, the regularity method for digraph collections, as well as the transversal blow-up lemma and the related machinery. As an application, when n n $n$ is sufficiently large, our result implies the transversal version of Dirac’s theorem, which was proved by Joos and Kim.