Monochromatic cycle covers in random graphs

Abstract

A classic result of Erdős, Gyárfás and Pyber states that for every coloring of the edges of $K_n$ with $r$ colors, there is a cover of its vertex set by at most $f(r)=O(r^2\log r)$ vertex-disjoint monochromatic cycles. In particular, the minimum number of such covering cycles does not depend on the size of $K_n$ but only on the number of colors. We initiate the study of this phenomena in the case where $K_n$ is replaced by the random graph $\mathcal{G}(n,p)$. Given a fixed integer $r$ and $p=p(n)\ge n^{-1/r+\epsilon }$, we show that with high probability the random graph $G\sim \mathcal{G}(n,p)$ has the property that for every $r$-coloring of the edges of $G$, there is a collection of $f^{\prime }(r)=O(r^8\log r)$ monochromatic cycles covering all the vertices of $G$. Our bound on $p$ is close to optimal in the following sense: if $p\ll (\log n/n{)}^{1/r}$, then with high probability there are colorings of $G\sim \mathcal{G}(n,p)$ such that the number of monochromatic cycles needed to cover all vertices of $G$ grows with $n$.

24 pages, 1 figure (minor changes, added figure)