Premium
Monochromatic cycle covers in random graphs
Author(s) -
Korándi Dániel,
Mousset Frank,
Nenadov Rajko,
Škorić Nemanja,
Sudakov Benny
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20819
Subject(s) - monochromatic color , combinatorics , mathematics , disjoint sets , vertex (graph theory) , random graph , discrete mathematics , complete graph , graph , upper and lower bounds , cover (algebra) , physics , optics , mechanical engineering , mathematical analysis , engineering
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 .