A universal dichotomy for concentration in randomly colored graphs

Abstract

Let $\hat{I}\P$ be Euclidean norm of the degree sequence of a graph normalized by the graph size. We prove that when the vertices of a graph are randomly colored with $s$ colors such that the fraction of vertices in each color class is bounded away from zero, only two asymptotic regimes emerge. If $\hat{I}\P =o(1)$, then the sizes of the subgraphs induced by the color classes concentrate around their expected values. If $\hat{I}\P =\hat{I}˜(1)$, then concentration depends on the color balance: for colorings with persisting imbalance, the total number $M$ of monochromatic edges stays bounded away from its mean with positive probability; otherwise, for vanishing imbalance, $M$ still concentrates. The same dichotomy holds for a broad class of randomly colored random graphs.

21 pages, no figure