Skip to content
DraconiticResearch
Search Sources API
186,123 studies31 sourcesUpdated 1 min ago
PreprintCC BY 4.0arXiv

A universal dichotomy for concentration in randomly colored graphs

  • Nicola Apollonio
Open at sourcePDFDOICite

Abstract

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.

Related

  1. Density of states of randomly sprinkled graphs
    Antti Knowles, Steffen Polzer
    arXivPreprintCC BY 4.0Full textMathematical physicsProbabilityarXiv
  2. Powers of Hamiltonian Cycles in Randomly Augmented Pósa-Seymour Graphs
    Sylwia Antoniuk, Andrzej Dudek, Andrzej Ruciński
    The Electronic Journal of CombinatoricsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsCrossref
  3. Scale Graphs II: Cheeger Dichotomy, (t,s)-Transport, and Tail Drainage
    Andrea Caffagni
    FigsharePreprintCC BY6 citedMathematical physicsOpenAlex
  4. The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy
    Aseem Raj Baranwal
    arXivPreprintCC BY 4.0Full textProbabilityStatisticsarXiv
  5. Almost Linear Universal Point Sets for Planar Graphs
    Taylor Gordon
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{apollonio2026universal,
  title = {{A universal dichotomy for concentration in randomly colored graphs}},
  author = {Nicola Apollonio},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2605.02678},
  eprint = {2605.02678},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.02678},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A universal dichotomy for concentration in randomly colored graphs
AU  - Nicola Apollonio
PY  - 2026
DA  - 2026/09/02
PB  - arXiv
DO  - 10.48550/arxiv.2605.02678
UR  - https://arxiv.org/abs/2605.02678
AB  - 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.
ER  -