{"id":"arxiv/2605.02678","url":"https://arxiv.org/abs/2605.02678","tags":["math.CO"],"score":0,"title":"A universal dichotomy for concentration in randomly colored graphs","domain":"math.CO","source":"arxiv","authors":["Nicola Apollonio"],"reviews":0,"subject":"math.CO","summary":"Let $ζ$ 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 $ζ=o(1)$, then the sizes of the subgraphs induced by the color classes concentrate around their expected values. If $ζ=Θ(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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-04","reactions":{}}