Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.02678 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914528119226368 |
|---|---|
| author | Apollonio, Nicola |
| author_facet | Apollonio, Nicola |
| contents | 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 probability; otherwise, for vanishing imbalance, $M$ still concentrates. The same dichotomy holds for a broad class of randomly colored random graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_02678 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A universal dichotomy for concentration in randomly colored graphs Apollonio, Nicola Combinatorics 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 probability; otherwise, for vanishing imbalance, $M$ still concentrates. The same dichotomy holds for a broad class of randomly colored random graphs. |
| title | A universal dichotomy for concentration in randomly colored graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.02678 |