Rainbow Matchings and Hamilton Cycles in Random Graphs

Deepak Bal, Alan Frieze

Published 2013-11-25, updated 2014-01-28Version 3

Let $HP_{n,m,k}$ be drawn uniformly from all $k$-uniform, $k$-partite hypergraphs where each part of the partition is a disjoint copy of $[n]$. We let $HP^{(\k)}_{n,m,k}$ be an edge colored version, where we color each edge randomly from one of $\k$ colors. We show that if $\k=n$ and $m=Kn\log n$ where $K$ is sufficiently large then w.h.p. there is a rainbow colored perfect matching. I.e. a perfect matching in which every edge has a different color. We also show that if $n$ is even and $m=Kn\log n$ where $K$ is sufficiently large then w.h.p. there is a rainbow colored Hamilton cycle in $G^{(n)}_{n,m}$. Here $G^{(n)}_{n,m}$ denotes a random edge coloring of $G_{n,m}$ with $n$ colors. When $n$ is odd, our proof requires $m=\om(n\log n)$ for there to be a rainbow Hamilton cycle.