Monochromatic cycle covers in random graphs

A classic result of Erd\H{o}s, Gy'arf'as 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)$\mathrm{.}Givenafixedinteger$r$and$p =p(n) \ge n^{-1/r + \varepsilon}$, 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^{\mathrm{\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\mathrm{/}n{)}^{1\mathrm{/}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$.