Monochromatic cycle covers in random graphs

• Published in: Random structures & algorithms 2018-12, Vol.53 (4), p.667-691
• Main Authors: Korándi, Dániel, Mousset, Frank, Nenadov, Rajko, Škorić, Nemanja, Sudakov, Benny
• Format: Article
• Language: English
• Subjects: Coloring; cycle cover; monochromatic cycles; random graphs
• ISSN: 1042-9832; 1098-2418
• DOI: 10.1002/rsa.20819

A classic result of Erdős, Gyárfás and Pyber states that for every coloring of the edges of Kn with r colors, there is a cover of its vertex set by at most f(r)=O(r2logr) vertex‐disjoint monochromatic cycles. In particular, the minimum number of such covering cycles does not depend on the size of Kn but only on the number of colors. We initiate the study of this phenomenon in the case where Kn 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(r8logr) monochromatic cycles covering all the vertices of G. Our bound on p is close to optimal in the following sense: if p≪(logn/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.