Universality for transversal Hamilton cycles

Abstract

Let $\mathbf{G}=\{G_1,\dots ,G_m\}$ be a graph collection on a common vertex set $V$ of size $n$ such that $\hat{I}´(G_i)\ge (1+o(1))n/2$ for every $i\in [m]$. We show that $\mathbf{G}$ contains every Hamilton cycle pattern. That is, for every map $\ddot{I}‡:[n]\to [m]$ there is a Hamilton cycle whose $i$-th edge lies in $G_{\ddot{I}‡(i)}$.

19 pages, 2 figures. Final version