Monochromatic cycle covers in random graphs. Issue 4 (21st October 2018)

• Record Type: Journal Article
• Authors: Korándi, Dániel; Mousset, Frank; Nenadov, Rajko; Škorić, Nemanja; Sudakov, Benny
• Is Part Of: Random structures & algorithms. Volume 53:Issue 4(2018)
• Page Start: 667
• Page End: 691
• Publication Date: 2018-10-21
• Subjects: cycle cover -- monochromatic cycles -- random graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20819
• Languages: English
• ISSNs: 1042-9832

Abstract

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 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 .