Monochromatic cycle covers in random graphs

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 phenomenon in the case where K n is replaced by the random graph G ( n , p ) . Given a fixed integer r and p = p ( n ) ≥ n − 1 / r + ε, we show that with high probability the random graph G ∼ G ( n , p ) has the property that for every r ‐coloring of the edges of G , there is a collection of f ′ ( 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 ≪ ( log n / n ) 1 / r, then with high probability there are colorings of G ∼ G ( n , p ) such that the number of monochromatic cycles needed to cover all vertices of G grows with n .