pith. sign in

arxiv: 2605.02678 · v1 · submitted 2026-05-04 · 🧮 math.CO

A universal dichotomy for concentration in randomly colored graphs

Nicola Apollonio This is my paper

Pith reviewed 2026-05-08 18:28 UTC · model grok-4.3

classification 🧮 math.CO
keywords randomly colored graphsconcentrationmonochromatic edgesdegree sequenceasymptotic analysisrandom graphsdichotomy
0
0 comments X

The pith

When vertices of a graph are randomly colored, concentration of induced subgraphs and monochromatic edges follows a dichotomy controlled by the normalized degree norm ζ.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The author proves that random colorings of graph vertices with a fixed number of colors, each used on a positive fraction of vertices, lead to only two possible asymptotic behaviors for concentration. If the normalized Euclidean norm ζ of the degree sequence is o(1), then the sizes of the subgraphs induced by each color class concentrate around their expected values. If ζ is Θ(1), concentration of the total number of monochromatic edges M depends on whether the color classes remain imbalanced or become balanced: persistent imbalance prevents concentration of M, while vanishing imbalance allows it. This split holds not only for fixed graphs but also for a broad class of randomly colored random graphs, providing a simple criterion based on graph density for when coloring randomness produces predictable outcomes.

Core claim

Let ζ be the 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

What carries the argument

ζ, defined as the Euclidean norm of the degree sequence normalized by the number of vertices, which partitions the possible graphs into sparse (o(1)) and dense (Θ(1)) regimes that dictate different concentration behaviors under random coloring.

Load-bearing premise

The fractions of vertices in each color class are bounded away from zero and the coloring is chosen independently at random for each vertex.

What would settle it

A counterexample would be a family of graphs where ζ is bounded away from zero, color classes have non-vanishing imbalance, yet the monochromatic edge count M converges in probability to its expected value.

read the original abstract

Let $\zeta$ 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 $\zeta=o(1)$, then the sizes of the subgraphs induced by the color classes concentrate around their expected values. If $\zeta=\Theta(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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 3 minor

Summary. The paper proves a dichotomy theorem for concentration in graphs with random vertex colorings. Let ζ denote the Euclidean norm of the degree sequence normalized by n. For an s-coloring in which each color class occupies a fraction of vertices bounded away from zero, the induced subgraphs on the color classes concentrate around their expectations whenever ζ = o(1). When ζ = Θ(1), the total number M of monochromatic edges concentrates if the color probabilities exhibit vanishing imbalance but remains bounded away from its mean with positive probability under persisting imbalance. The same two-regime behavior is shown to hold for a broad class of randomly colored random graphs.

Significance. If correct, the result supplies a single, easily computed parameter ζ that cleanly separates concentration regimes for both induced color-class sizes and monochromatic edge counts, independent of further model details once the degree sequence and color-balance asymptotics are fixed. The extension to random graphs via conditioning on realizations where ζ remains Θ(1) w.h.p. is a notable strength, as is the explicit use of conditional-expectation calculations and standard second-moment or martingale bounds without fitted parameters.

major comments (1)
  1. [Theorem 1.2 / Introduction] The abstract and introduction state that the dichotomy extends to 'a broad class of randomly colored random graphs,' yet the precise conditions on the random-graph model (e.g., edge-probability regime, dependence on n) under which ζ = Θ(1) holds w.h.p. are not spelled out in the theorem statement; this makes it difficult to verify the scope of the claimed extension without consulting the full proof.
minor comments (3)
  1. [Abstract] The precise definition of 'persisting imbalance' versus 'vanishing imbalance' (in terms of the color probabilities p_i) should be stated explicitly in the abstract or the statement of the main theorem rather than only in the body.
  2. [Section 1] Notation for the color probabilities p_1, …, p_s and the imbalance measure should be introduced at the first appearance of the dichotomy statement to improve readability.
  3. [Introduction] A short comparison paragraph relating the new ζ-based criterion to earlier concentration results for monochromatic edges (e.g., in Erdős–Rényi or configuration-model graphs) would help situate the contribution.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment, and constructive suggestion. We address the major comment below and have revised the manuscript accordingly to improve clarity.

read point-by-point responses

  1. Referee: [Theorem 1.2 / Introduction] The abstract and introduction state that the dichotomy extends to 'a broad class of randomly colored random graphs,' yet the precise conditions on the random-graph model (e.g., edge-probability regime, dependence on n) under which ζ = Θ(1) holds w.h.p. are not spelled out in the theorem statement; this makes it difficult to verify the scope of the claimed extension without consulting the full proof.

    Authors: We agree that the theorem statement benefits from greater explicitness. In the revised manuscript we have updated the statement of Theorem 1.2 to list the precise conditions on the random-graph model: the edge-probability regime must ensure that the normalized degree norm ζ remains Θ(1) with high probability (including the explicit dependence on n), and the result is obtained by conditioning on the realizations satisfying this property. These conditions, previously developed in the proof, are now stated directly in the theorem so that the scope of the extension is verifiable without reference to the full argument. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation uses external parameters and standard concentration tools

full rationale

The paper defines ζ externally as the normalized Euclidean norm of the given degree sequence and partitions regimes by its asymptotic size together with an explicit color-balance condition. Concentration statements for induced subgraphs and monochromatic edges M are obtained via direct application of martingale inequalities and second-moment calculations on the independent vertex colorings; no parameter is fitted to data and then renamed as a prediction, no self-citation supplies a load-bearing uniqueness theorem, and the bounded-away-from-zero color fractions are stated as an input assumption rather than derived. The argument therefore remains self-contained against external probabilistic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the standard model of independent random vertex coloring with balanced fractions and on classical concentration tools from probability; no free parameters are introduced or fitted, and no new entities are postulated.

axioms (2)
  • domain assumption Vertices are colored independently and uniformly at random with s colors, each color class having asymptotic fraction bounded away from zero.
    This balanced random coloring is the setting in which the two regimes are claimed to emerge.
  • standard math Standard concentration inequalities (Chernoff, Azuma, etc.) apply to the relevant random variables once the degree sequence is fixed.
    These are the tools implicitly used to prove concentration in the o(1) regime and in the balanced Θ(1) regime.

pith-pipeline@v0.9.0 · 5412 in / 1543 out tokens · 76709 ms · 2026-05-08T18:28:51.865677+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • Foundation/BranchSelection.lean branch_selection unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    Let zeta 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 ... only two asymptotic regimes emerge.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    N. Alon, D. Hefetz, M. Krivelevich, M. Tyomkyn,Edge-statistics on large graphs, Combin. Probab. Comput., 29:2:(2020) 163–189. 18

    work page 2020

  2. [2]

    Alon and J.H

    N. Alon and J.H. Spencer,The Probabilistic Method, 4th ed., Hoboken, NJ, John Wiley & Sons, 2016

    work page 2016

  3. [3]

    Apollonio, P.G

    N. Apollonio, P.G. Franciosa, D. Santoni,Network homophily via tail inequalities, Physical Review E, 108:5 (2023) 054130

    work page 2023

  4. [4]

    Apollonio,Second-order moments of the size of randomly induced subgraphs of given order, Discrete Applied Mathematics 355 (2024) 46-56

    N. Apollonio,Second-order moments of the size of randomly induced subgraphs of given order, Discrete Applied Mathematics 355 (2024) 46-56

    work page 2024

  5. [5]

    Apollonio,Functions that are uniquely maximized by sparse quasi-star graphs, and uniquely minimized by quasi-complete graphs, Discrete Applied Mathematics 366 (2025) 226-237

    N. Apollonio,Functions that are uniquely maximized by sparse quasi-star graphs, and uniquely minimized by quasi-complete graphs, Discrete Applied Mathematics 366 (2025) 226-237

    work page 2025

  6. [6]

    BillingsleyProbability and measure2nd ed

    P. BillingsleyProbability and measure2nd ed. New York: Wiley; 1986. (Wiley series in probability and mathematical statistics)

    work page 1986

  7. [7]

    Blekherman, S

    G. Blekherman, S. Patel,Threshold graphs maximise homomorphism densities, Combina- torics, Probability and Computing. 33:3 (2024) 300–318

    work page 2024

  8. [8]

    Borovi´ canin, K.C

    B. Borovi´ canin, K.C. Das, B. Furtula, I. Gutman,Bounds for Zagreb indices, MATCH Com- mun. Math. Comput. Chem., 78 (2017), 17–100

    work page 2017

  9. [9]

    Chung, L

    F. Chung, L. Lu,The average distances in random graphs with given expected degrees, Proc. Natl. Acad. Sci. U.S.A., 99:25 (2002) 15879–15882

    work page 2002

  10. [10]

    J. Fox, L. Sauermann,A completion of the proof of the edge-statistics conjecture, Adv. Comb., Paper No. 4, 52, 2020

    work page 2020

  11. [11]

    Hirst,The inducibility of graphs on four vertices,J.Graph Theory 75:3 (2014) 231–243

    J. Hirst,The inducibility of graphs on four vertices,J.Graph Theory 75:3 (2014) 231–243

    work page 2014

  12. [12]

    Ismailescu, D

    D. Ismailescu, D. Stefanica,Minimizer graphs for a class of extremal problems, J. Graph Theory, 39 (2002) 230–240

    work page 2002

  13. [13]

    Kallenberg,Foundations of Modern Probability, Springer-Verlag, New York, 1997

    O. Kallenberg,Foundations of Modern Probability, Springer-Verlag, New York, 1997

    work page 1997

  14. [14]

    M. Kwan, B. Sudakov, T. Tran,Anticoncentration for subgraph statisticsJ. Lond. Math. Soc. (2), 99:3 (2019) 757–777

    work page 2019

  15. [15]

    X. Liu, D. Mubayi, C. Reiher,The feasible region of induced graphs, J. Combin. Theory Ser.B, 158 (2023) 105—135

    work page 2023

  16. [16]

    Lov´ asz,Large Networks and Graph Limits

    L. Lov´ asz,Large Networks and Graph Limits. Colloquium Publications 60., Providence, RI, American Mathematical Society, 2012

    work page 2012

  17. [17]

    Martinsson, F

    A. Martinsson, F. Mousset, A. Noever, M. Truji` c. The edge-statistics conjecture forℓ!k 6{5. Israel J.Math., 234:2 (2019) 677–690

    work page 2019

  18. [18]

    McPherson, L

    M. McPherson, L. Smith-Lovin, J.M. Cook.Birds of a Feather: Homophily in Social Networks, Annual Review of Sociology 27 (2001) 415-444

    work page 2001

  19. [19]

    Newman,Mixing patterns in networks, Physical Review E 67:2 (2003) 026126

    M.E.J. Newman,Mixing patterns in networks, Physical Review E 67:2 (2003) 026126

    work page 2003

  20. [20]

    Pippengerand, M.C

    N. Pippengerand, M.C. Golumbic,The inducibility of graphs,J. Combinatorial Theory Ser. B 19:3 (1975) 189–203. 19 Appendix For the foregoing notions we refer to [6, 13], especially Chapter 3 in [13]. Recall that a sequence pYnqně1 of random variables is uniformly integrable (see [6]) if for allϵą0 there exists someℓą0 such that: sup n Ep|Yn|1t|Yn|ąℓuq ăϵ w...

    work page 1975