Rainbow Pancyclicity in Graph Systems

Let G(1), ...,G(n), be graphs on the same vertex set of size n, each graph with minimum degree delta(G(i)) >= n/2. A recent conjecture of Aharoni asserts that there exists a rainbow Hamiltonian cycle i.e. a cycle with edge set {e(1),..., e(n)} such that e(i) E E(G(i)) for 1 <= i <= n. This can be viewed as a rainbow version of the well-known Dirac theorem. In this paper, we prove this conjecture asymptotically by showing that for every epsilon > 0, there exists an integer N > 0, such that when n > N for any graphs G(1), ...,G(n), on the same vertex set of size n with delta(G(i)) >= (1/2 + epsilon), there exists a rainbow Hamiltonian cycle. Our main tool is the absorption technique. Additionally, we prove that with delta(G(i)) >= (n+1/2) for each i, one can find rainbow cycles of length 3, ..., n - 1.