pith. sign in

arxiv: 2604.14006 · v1 · submitted 2026-04-15 · 🧮 math.CO

Coloring powers of random graphs

Alan Frieze , Ross Kang , Aditya Raut , Michelle Sweering , Hilde Verbeek This is my paper

Pith reviewed 2026-05-10 12:44 UTC · model grok-4.3

classification 🧮 math.CO
keywords random graphsgraph powersmaximum degreechromatic numberasymptotic boundsbinomial modelsparse regimedense regime
0
0 comments X

The pith

The rth power of a sparse random graph has maximum degree asymptotically log n over the (r+1)th iterated logarithm, with chromatic number bounded by the maximum degrees of its floor(r/2)th and (r-1)th powers.

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

The paper determines the typical maximum degree and chromatic number of the rth power of the binomial random graph G(n,p). In the sparse regime with fixed average degree d, it proves the maximum degree concentrates at log n divided by the (r+1)th iterated logarithm. It also shows the chromatic number lies between one plus the maximum degree of the floor(r/2)th power and one plus the maximum degree of the (r-1)th power, with equality in the upper bound when r equals 2. A reader would care because these quantities describe how longer-range connections reshape connectivity and colorability in random networks. In denser regimes where d grows faster than log n but stays below n to the power 1/r minus a constant, the chromatic number is shown to be on the order of d to the r over its logarithm.

Core claim

Given a graph G and integer r at least 1, the rth power G^r adds edges between all pairs at distance at most r. For G equal to the binomial random graph G(n,p) with p equal to d over n and d a fixed constant, the paper proves that with high probability the maximum degree satisfies Delta(G(n,p)^r) asymptotically equivalent to log n over log base (r+1) of n. It further proves that Delta(G(n,p) to the floor(r/2)) plus one is at most the chromatic number of G(n,p)^r, which is at most Delta(G(n,p) to the (r-1)) plus one, and that the upper bound is tight for r equal to 2. When d grows faster than log n yet stays at most n to the power 1/r minus Omega of 1, the chromatic number is Theta of d to r,

What carries the argument

The rth power graph construction on G(n,p), whose maximum degree is set by the number of vertices reachable in at most r steps and whose chromatic number is controlled by greedy coloring bounds from the maximum degrees of lower powers.

If this is right

  • With high probability the maximum degree of G(n,p)^r follows the iterated-logarithm formula for any fixed r in the sparse regime.
  • The chromatic number of the rth power is at most one more than the maximum degree of the (r-1)th power.
  • When r equals 2 the chromatic number of the square equals exactly the maximum degree of the original graph plus one.
  • In the denser regime the chromatic number grows as Theta(d^r over log d).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same neighborhood-counting approach might yield analogous degree formulas for other distance-based graph operations such as distance graphs.
  • Numerical checks on moderate-sized instances could reveal the speed of convergence to the asymptotic formulas.
  • The bounds may suggest efficient coloring heuristics for powered random graphs by first coloring the underlying sparse graph.

Load-bearing premise

The binomial random graph G(n,p) in the given density ranges produces typical neighborhood sizes that yield the stated concentration for degrees in the powered graph.

What would settle it

Simulate a single large instance of G(n,p) with n around 10^6 and fixed d, compute the actual maximum degree in its rth power, and check whether it stays within a small constant factor of log n over the (r+1)th iterated log; a consistent large deviation would falsify the main degree claim.

read the original abstract

Given a graph $G$ and an integer $r\ge 1$, the $r$th power $G^r$ of $G$ is the graph obtained from $G$ by adding edges for all pairs of distinct vertices at distance at most $r$ from each other. We focus on two basic structural properties of the $r$th power of the binomial random graph $G_{n,p}$, namely, the maximum degree $\Delta(G_{n,p}^r)$ and the chromatic number $\chi(G_{n,p}^r)$, and give with high probability (w.h.p.) bounds. In the sparse case that $p=d/n$ for some fixed constant $d>0$, we prove the following. We prove that w.h.p.~$\Delta(G_{n,p}^r) \sim \frac{\log n}{\log_{(r+1)}n}$ (where $\log_{(1)}n=\log n$ and $\log_{(r+1)}n=\log\log_{(r)}n$) and that w.h.p.~$\Delta(G_{n,p}^{\lfloor{r/2}\rfloor})+1 \le \chi(G_{n,p}^r) \le \Delta(G_{n,p}^{r-1})+1$. For $r=2$, we show the upper bound holds with equality. For denser cases, for $d$ satisfying $d=\omega(\log n)$ and $d\le n^{1/r-\Omega(1)}$ as $n\to\infty$, we have $\chi(G_{n,p}^r) = \Theta(d^r/\log d)$ w.h.p.

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

0 major / 3 minor

Summary. The manuscript studies the maximum degree and chromatic number of the r-th power G^r of the binomial random graph G_{n,p}. In the sparse regime p = d/n with fixed d > 0, it proves w.h.p. that Δ(G_{n,p}^r) ∼ log n / log_{(r+1)} n (with the iterated logarithm defined recursively), together with the sandwich Δ(G_{n,p}^{⌊r/2⌋}) + 1 ≤ χ(G_{n,p}^r) ≤ Δ(G_{n,p}^{r-1}) + 1; equality holds in the upper bound when r = 2. In the denser regime d = ω(log n) and d ≤ n^{1/r − Ω(1)}, it establishes χ(G_{n,p}^r) = Θ(d^r / log d) w.h.p.

Significance. If the claims hold, the work supplies precise, parameter-free asymptotics for the maximum degree of random-graph powers in the sparse regime and tight chromatic-number bounds that exploit the local tree-like geometry and ball-clique structure. The denser-regime result aligns with known inhomogeneous-random-graph chromatic-number asymptotics. These are natural and useful extensions of classical G(n,p) results; the explicit matching of lower and upper bounds for r = 2 is a particular strength.

minor comments (3)
  1. The definition of the iterated logarithm log_{(r+1)} n is given only in the abstract; it should be restated at the beginning of the sparse-case section for self-contained reading.
  2. In the statement of the denser regime, the hidden constant inside the Ω(1) in the upper bound on d should be made explicit (or at least bounded) so that the precise range of validity is clear.
  3. The proof sketch for the lower bound χ(G^r) ≥ Δ(G^{⌊r/2⌋}) + 1 relies on the existence of a clique formed by a maximum ball of radius ⌊r/2⌋; a short paragraph confirming that the diameter argument survives the random-graph local structure would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our results on the maximum degree and chromatic number of powers of random graphs, and for recommending minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained in G(n,p) model

full rationale

The paper establishes w.h.p. bounds on Δ(G_{n,p}^r) and χ(G_{n,p}^r) via direct probabilistic analysis of the binomial random graph. The lower bound χ(G^r) ≥ Δ(G^{⌊r/2⌋})+1 follows from the structural fact that radius-⌊r/2⌋ balls induce cliques in the power graph (diameter ≤ r). The upper bound exploits the locally tree-like structure of G(n,p) for a strengthened greedy coloring. The Θ(d^r/log d) asymptotic in the denser regime matches standard results for inhomogeneous random graphs with effective degree Θ(d^r). No equations reduce claims to fitted parameters, self-definitions, or load-bearing self-citations; all steps are independent consequences of the stated G(n,p) regimes.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the standard binomial random-graph model and classical concentration tools; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption Binomial random graph G(n,p) model with the given p regimes
    Invoked throughout the abstract as the underlying probability space.

pith-pipeline@v0.9.0 · 5601 in / 1262 out tokens · 46971 ms · 2026-05-10T12:44:47.943971+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs

    cs.DS 2026-05 unverdicted novelty 7.0

    Online algorithms achieve multiplicative approximation r^{1/(r-1)} for maximum independent sets in dense r-uniform ER hypergraphs and (max γ_i)^{-1/(r-1)} for balanced sets in r-partite versions, with matching lower bounds.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages · cited by 1 Pith paper

  1. [1]

    Achlioptas and A

    D. Achlioptas and A. Naor. The two possible values of the chromatic number of a random graph.Ann. of Math. (2), 162(3):1335–1351, 2005

    work page 2005

  2. [2]

    Addario-Berry, N

    L. Addario-Berry, N. Broutin, and C. Goldschmidt. The continuum limit of critical random graphs.Probab. Theory Related Fields, 152(3-4):367–406, 2012

    work page 2012

  3. [3]

    Agnarsson and M

    G. Agnarsson and M. M. Halld´ orsson. Coloring powers of planar graphs.SIAM J. Discrete Math., 16(4):651–662, 2003

    work page 2003

  4. [4]

    N. Alon, M. Krivelevich, and B. Sudakov. Coloring graphs with sparse neighborhoods. Journal of Combinatorial Theory, Series B, 77(1):73–82, 1999

    work page 1999

  5. [5]

    Alon and B

    N. Alon and B. Mohar. The chromatic number of graph powers.Combinatorics, Probability and Computing, 11(1):1–10, 2002

    work page 2002

  6. [6]

    Amini, L

    O. Amini, L. Esperet, and J. van den Heuvel. A unified approach to distance-two colouring of graphs on surfaces.Combinatorica, 33(3):253–296, 2013

    work page 2013

  7. [7]

    Atkinson and A

    G. Atkinson and A. Frieze. On the-independence number of sparse random graphs. Combinatorics, Probability and Computing, 13(3):295–309, 2004. 14

    work page 2004

  8. [8]

    P. Ayre, A. Coja-Oghlan, and C. Greenhill. Lower bounds on the chromatic number of random graphs.Combinatorica, 42(5):617–658, 2022

    work page 2022

  9. [9]

    Bollob´ as

    B. Bollob´ as. The distribution of the maximum degree of a random graph.Discrete Math., 32(2):201–203, 1980

    work page 1980

  10. [10]

    Bollob´ as

    B. Bollob´ as. The diameter of random graphs.Trans. Amer. Math. Soc., 267(1):41–52, 1981

    work page 1981

  11. [11]

    Bollob´ as

    B. Bollob´ as. The chromatic number of random graphs.Combinatorica, 8(1):49–55, 1988

    work page 1988

  12. [12]

    Coja-Oghlan and D

    A. Coja-Oghlan and D. Vilenchik. The chromatic number of random graphs for most average degrees.Int. Math. Res. Not. IMRN, (19):5801–5859, 2016

    work page 2016

  13. [13]

    Davies, R

    E. Davies, R. J. Kang, F. Pirot, and J.-S. Sereni. Graph structure via local occupancy. arXiv e-prints, page arXiv:2003.14361, Mar. 2020

    work page arXiv 2003

  14. [14]

    Erd˝ os and A

    P. Erd˝ os and A. R´ enyi. On the evolution of random graphs.Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl., 5:17–61, 1960

    work page 1960

  15. [15]

    Frieze and M

    A. Frieze and M. Karo´ nski.Introduction to random graphs. Cambridge University Press, Cambridge, 2016

    work page 2016

  16. [16]

    Frieze and A

    A. Frieze and A. Raut. A note on the chromatic number of the square of a sparse random graph, 2023

    work page 2023

  17. [17]

    Garapaty, D

    K. Garapaty, D. Lokshtanov, H. K. Maji, and A. Pothen. The chromatic number of squares of random graphs.Journal of Combinatorics, 14(4):507–537, 2023

    work page 2023

  18. [18]

    List Colouring Squares of Planar Graphs

    F. Havet, J. van den Heuvel, C. McDiarmid, and B. Reed. List Colouring Squares of Planar Graphs.arXiv e-prints, page arXiv:0807.3233, July 2008

    work page Pith review arXiv 2008

  19. [19]

    S. Janson. Poisson approximation for large deviations.Random Structures Algorithms, 1(2):221–229, 1990

    work page 1990

  20. [20]

    R. J. Kang and C. McDiarmid. Colouring random graphs. InTopics in chromatic graph theory, volume 156 ofEncyclopedia Math. Appl., pages 199–229. Cambridge Univ. Press, Cambridge, 2015

    work page 2015

  21. [21]

    R. J. Kang and F. Pirot. Coloring powers and girth.SIAM J. Discrete Math., 30(4):1938–1949, 2016

    work page 1938

  22. [22]

    R. J. Kang and F. Pirot. Distance colouring without one cycle length.Combin. Probab. Comput., 27(5):794–807, 2018

    work page 2018

  23. [23]

    R. J. Kang and W. van Loon. Tree-like distance colouring for planar graphs of sufficient girth.Electron. J. Combin., 26(1):Paper No. 1.23, 15, 2019. 15

    work page 2019

  24. [24]

    Klee and D

    V. Klee and D. Larman. Diameters of random graphs.Can. J. Math., 33:618–640, 1981

    work page 1981

  25. [25]

    N. Linial. Locality in distributed graph algorithms.SIAM J. Comput., 21(1):193–201, 1992

    work page 1992

  26. [26]

    T. Luczak. The chromatic number of random graphs.Combinatorica, 11(1):45–54, 1991

    work page 1991

  27. [27]

    Matula and L

    D. Matula and L. Kuˇ cera. An expose-and-merge algorithm and the chromatic number of a random graph. InRandom graphs ’87 (Pozna´ n, 1987), pages 175–187. Wiley, Chichester, 1990

    work page 1987

  28. [28]

    D. W. Matula. Expose-and-merge exploration and the chromatic number of a random graph.Combinatorica, 7(3):275–284, 1987

    work page 1987

  29. [29]

    Pokrovskiy

    A. Pokrovskiy. Edge growth in graph powers.Australas. J. Combin., 58:347–357, 2014

    work page 2014

  30. [30]

    Riordan and N

    O. Riordan and N. Wormald. The diameter of sparse random graphs.Combin. Probab. Comput., 19(5-6):835–926, 2010. 16

    work page 2010