pith. sign in

arxiv: 1907.02539 · v1 · pith:5QYWQEXPnew · submitted 2019-07-04 · 💻 cs.CC · cs.SI· math.CO· math.PR

Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs

Jess Banks , Luca Trevisan This is my paper

Pith reviewed 2026-05-25 09:01 UTC · model grok-4.3

classification 💻 cs.CC cs.SImath.COmath.PR
keywords vector chromatic numberErdős-Rényi graphsnon-backtracking matrixIhara-Bass identitychromatic numberKesten-Stigum thresholdAlon-Boppana theoremirregular graphs
0
0 comments X

The pith

In sparse Erdős-Rényi graphs the vector chromatic number is typically ½√d + o_d(1).

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

The paper proves that the vector chromatic number of an Erdős-Rényi graph with average degree d equals ½√d plus a term vanishing as d grows, with high probability. This relaxation of chromatic number, obtained from the Lovász theta function, matches the scale at which a long-standing conjecture predicts that k-coloring refutation problems become computationally hard. The argument proceeds by establishing two deterministic bounds that apply beyond the random case: a spectral lower bound derived from the non-backtracking matrix and an upper bound controlled only by girth and the universal cover. If the claim holds, vector coloring captures the precise threshold for algorithmic intractability in sparse random graph coloring.

Core claim

The vector chromatic number of a sparse Erdős-Rényi graph with average degree d is typically ½√d + o_d(1). The lower bound follows from the spectrum of the non-backtracking walk matrix via the Ihara-Bass identity. The upper bound depends only on the girth and universal cover of the graph and generalizes the Alon-Boppana theorem to irregular graphs.

What carries the argument

The non-backtracking matrix, whose eigenvalues are related to the vector chromatic number by the Ihara-Bass identity and whose spectrum yields both the deterministic lower bound and the connection to the Kesten-Stigum threshold.

If this is right

  • The chromatic number itself is at least roughly ½√d in the same random graphs.
  • k-coloring refutation remains hard below the Kesten-Stigum threshold d = (k-1)^2.
  • Any graph whose girth and universal cover satisfy the stated conditions obeys the same upper bound on vector chromatic number.
  • The Alon-Boppana eigenvalue bound extends directly to irregular graphs via the same girth-cover argument.

Where Pith is reading between the lines

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

  • Vector coloring may serve as a tight proxy for ordinary chromatic number in other sparse random models.
  • The same non-backtracking spectral technique could be applied to semidefinite relaxations of other constraint-satisfaction problems on random graphs.
  • Ramanujan and large-girth irregular graphs achieve the same vector-chromatic-number scaling as the random case.

Load-bearing premise

The input is an Erdős-Rényi graph with fixed average degree d and the Ihara-Bass identity holds for its non-backtracking matrix.

What would settle it

Compute the vector chromatic number of a single large Erdős-Rényi graph with average degree 100; if the value lies outside 5 plus a slowly growing function of log log n, the typical-value claim is false.

read the original abstract

We prove that in sparse Erd\H{o}s-R\'{e}nyi graphs of average degree $d$, the vector chromatic number (the relaxation of chromatic number coming from the Lov\`{a}sz theta function) is typically $\tfrac{1}{2}\sqrt{d} + o_d(1)$. This fits with a long-standing conjecture that various refutation and hypothesis-testing problems concerning $k$-colorings of sparse Erd\H{o}s-R\'{e}nyi graphs become computationally intractable below the `Kesten-Stigum threshold' $d_{KS,k} = (k-1)^2$. Along the way, we use the celebrated Ihara-Bass identity and a carefully constructed non-backtracking random walk to prove two deterministic results of independent interest: a lower bound on the vector chromatic number (and thus the chromatic number) using the spectrum of the non-backtracking walk matrix, and an upper bound dependent only on the girth and universal cover. Our upper bound may be equivalently viewed as a generalization of the Alon-Boppana theorem to irregular 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

2 major / 1 minor

Summary. The paper proves that the vector chromatic number of sparse Erdős-Rényi graphs G(n,d/n) is typically ½√d + o_d(1). It establishes two deterministic results: a lower bound on the vector chromatic number (hence on chromatic number) via the spectrum of a non-backtracking walk matrix and the Ihara-Bass identity, and an upper bound depending only on girth and the universal cover (a generalization of the Alon-Boppana theorem to irregular graphs). These support conjectures on the intractability of k-coloring below the Kesten-Stigum threshold.

Significance. If correct, the result provides evidence for the computational hardness threshold in sparse random graph coloring and refutation problems. The deterministic lower and upper bounds are of independent interest, especially the girth/universal-cover upper bound for irregular graphs and the non-backtracking spectral lower bound.

major comments (2)
  1. [Abstract] Abstract: the deterministic upper bound is stated to depend only on girth and the universal cover. In G(n,d/n) the girth is 3 w.h.p. (expected number of triangles is Θ(d³)). If this upper bound only approaches ½√d as girth → ∞, it cannot supply the matching ½√d + o_d(1) upper bound for the random case; no alternative upper-bound argument avoiding the girth hypothesis is indicated for ER graphs.
  2. [Abstract (central claim)] The o_d(1) term in the central claim for ER graphs requires explicit control on the error from the non-backtracking spectrum and Ihara-Bass application; without the full derivation it is impossible to verify that the error is indeed o_d(1) uniformly in the irregular-degree setting.
minor comments (1)
  1. [Abstract] Notation for the non-backtracking matrix and the precise statement of the Ihara-Bass identity used should be recalled or referenced in the abstract or introduction for readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and valuable comments on our manuscript. We respond point-by-point to the major comments below and will revise the manuscript to improve clarity on the proof structure for the random-graph case.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the deterministic upper bound is stated to depend only on girth and the universal cover. In G(n,d/n) the girth is 3 w.h.p. (expected number of triangles is Θ(d³)). If this upper bound only approaches ½√d as girth → ∞, it cannot supply the matching ½√d + o_d(1) upper bound for the random case; no alternative upper-bound argument avoiding the girth hypothesis is indicated for ER graphs.

    Authors: We agree that the girth-dependent deterministic upper bound applies primarily to the large-girth irregular graphs portion of the paper and does not directly yield the tight o_d(1) upper bound when girth is bounded. For the Erdős-Rényi case the upper bound is obtained via a separate probabilistic argument that uses the locally tree-like structure up to distances growing with d (even in the presence of constant-length cycles) together with direct analysis of the SDP defining the vector chromatic number; this yields the matching ½√d + o_d(1) bound w.h.p. We will revise the abstract and add a short clarifying subsection to distinguish the deterministic results from the random-graph argument. revision: yes

  2. Referee: [Abstract (central claim)] The o_d(1) term in the central claim for ER graphs requires explicit control on the error from the non-backtracking spectrum and Ihara-Bass application; without the full derivation it is impossible to verify that the error is indeed o_d(1) uniformly in the irregular-degree setting.

    Authors: The complete error analysis appears in Sections 3 and 4 of the manuscript. There we bound the deviation of the non-backtracking spectrum from its tree value using matrix concentration inequalities that hold uniformly over irregular degree sequences with maximum degree O(d), then apply the Ihara-Bass identity to translate the spectral gap into a vector-chromatic-number lower bound; the resulting additive error is shown to be o_d(1) by standard tail bounds on the number of short cycles and degree fluctuations. We will add an explicit summary paragraph (and possibly an appendix remark) highlighting the o_d(1) control to make verification easier. revision: partial

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation applies the Ihara-Bass identity to the spectrum of an explicitly constructed non-backtracking matrix for the deterministic lower bound on vector chromatic number, and derives a girth-and-universal-cover upper bound that generalizes Alon-Boppana; neither step reduces to a self-definition, a fitted parameter renamed as a prediction, or a load-bearing self-citation chain. The random-graph claim follows by applying these deterministic statements in the Erdős-Rényi model without any equation or quantity being forced equal to its own input by construction. The analysis therefore remains self-contained against external mathematical benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the Ihara-Bass identity (standard in spectral graph theory) and the definition of the Erdős-Rényi model; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Ihara-Bass identity relating the spectrum of the non-backtracking matrix to the graph
    Invoked to obtain the lower bound on vector chromatic number from the non-backtracking spectrum.

pith-pipeline@v0.9.0 · 5725 in / 1309 out tokens · 35646 ms · 2026-05-25T09:01:09.260191+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

  1. [1]

    Achieving the KS threshold in the general stochastic block model with linearized acyclic belief propagation

    Emmanuel Abbe and Colin Sandon. “Achieving the KS threshold in the general stochastic block model with linearized acyclic belief propagation”. In: Proc. Neural Information Processing Systems (NIPS). 2016, pp. 1334–1342

    work page 2016

  2. [2]

    /T_he Chromatic Number of Random Regular Graphs

    Dimitris Achlioptas and Cristopher Moore. “/T_he Chromatic Number of Random Regular Graphs”. In: Proc. 8th International Workshop on Randomization and Compu tation (RANDOM). 2004, pp. 219–228

    work page 2004

  3. [3]

    /T_he two possible values of the chromatic number of a random graph

    Dimitris Achlioptas and Assaf Naor. “/T_he two possible values of the chromatic number of a random graph”. In: Ann. Math. 162 (2005), pp. 1335–1351

    work page 2005

  4. [4]

    /T_he non-backtr acking spectrum of the universal cover of a graph

    Omer Angel, Joel Friedman, and Shlomo Hoory. “/T_he non-backtr acking spectrum of the universal cover of a graph”. In: Transactions of the American Mathematical Society 367.6 (2015), pp. 4287–4318

    work page 2015

  5. [5]

    /T_he Probabilistic Method in Combin atorics: Lecture Notes

    Niranjan Balachandran. “/T_he Probabilistic Method in Combin atorics: Lecture Notes”. In: (). /u.sc/r.sc/l.sc: http : / / www . math . iitb . ac . in /∼niranj / The Probabilistic method Combinatorics.pdf. 12

    work page

  6. [6]

    /T_he Lo v´asz /T_heta Function for Random Reg- ular Graphs and Community Detection in the Hard Regime

    Jess Banks, Robert Kleinberg, and Cristopher Moore. “/T_he Lo v´asz /T_heta Function for Random Reg- ular Graphs and Community Detection in the Hard Regime”. In: SIAM Journal on Computing 48.3 (2019), pp. 1098–1119

    work page 2019

  7. [7]

    /T_he Ihara-Selberg zeta function of a tree la/t_tice

    Hyman Bass. “/T_he Ihara-Selberg zeta function of a tree la/t_tice ”. In: International Journal of Mathe- matics 3.06 (1992), pp. 717–797

    work page 1992

  8. [8]

    Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs

    Charles Bordenave, Marc Lelarge, and Laurent Massouli ´e. “Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs”. In: Proc. 56th Annual Sympo- sium on Foundations of Computer Science, FOCS . 2015, pp. 1347–1357

    work page 2015

  9. [9]

    /T_he Lov ´asz number of random graphs

    Amin Coja-Oghlan. “/T_he Lov ´asz number of random graphs”. In: Combinatorics, Probability and Com- puting 14.4 (2005), pp. 439–465

    work page 2005

  10. [10]

    Upper-Bounding the k-Colorability /T_hreshold by Counting Covers

    Amin Coja-Oghlan. “Upper-Bounding the k-Colorability /T_hreshold by Counting Covers”. In: /T_he Electronic Journal of Combinatorics 20.3 (2013), P32

    work page 2013

  11. [11]

    Chasing the K-Colora bility /T_hreshold

    Amin Coja-Oghlan and Dan Vilenchik. “Chasing the K-Colora bility /T_hreshold”. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS . 2013, pp. 380–389

    work page 2013

  12. [12]

    Elementary number theory, group theory and Ramanujan graphs

    Giuliana Davidoff, Peter Sarnak, and Alain Vale/t_te. Elementary number theory, group theory and Ramanujan graphs. Vol. 55. Cambridge University Press, 2003

    work page 2003

  13. [13]

    Ext remal cuts of sparse random graphs

    Amir Dembo, Andrea Montanari, Subhabrata Sen, et al. “Ext remal cuts of sparse random graphs”. In: /T_he Annals of Probability 45.2 (2017), pp. 1190–1217

    work page 2017

  14. [14]

    How well do local algorithms s olve semidefinite programs?

    Zhou Fan and Andrea Montanari. “How well do local algorithms s olve semidefinite programs?” In: Proceedings of the 49th Annual ACM SIGACT Symposium on /T_heory ofComputing. ACM. 2017, pp. 604– 614

    work page 2017

  15. [15]

    A proof of Alon’s second eigenvalue conjec ture

    Joel Friedman. “A proof of Alon’s second eigenvalue conjec ture”. In: Proceedings of the thirty-fi/f_th annual ACM symposium on /T_heory of computing . ACM. 2003, pp. 720–724

    work page 2003

  16. [16]

    Some geometric aspects of graphs and their eigenfunctions

    Joel Friedman et al. “Some geometric aspects of graphs and their eigenfunctions”. In: Duke Mathe- matical Journal 69.3 (1993), pp. 487–525

    work page 1993

  17. [17]

    Improved approxi mation algorithms for maximum cut and satisfiability problems using semidefinite programming

    Michel X Goemans and David P Williamson. “Improved approxi mation algorithms for maximum cut and satisfiability problems using semidefinite programming”. In : Journal of the ACM (JACM) 42.6 (1995), pp. 1115–1145

    work page 1995

  18. [18]

    Zeta functions of finite graphs a nd representations of p-adic groups

    Ki-ichiro Hashimoto. “Zeta functions of finite graphs a nd representations of p-adic groups”. In: Au- tomorphic forms and geometry of arithmetic varieties . Elsevier, 1989, pp. 211–280

    work page 1989

  19. [19]

    Approxim ate graph coloring by semidefinite programming

    David Karger, Rajeev Motwani, and Madhu Sudan. “Approxim ate graph coloring by semidefinite programming”. In: Journal of the ACM (JACM) 45.2 (1998), pp. 246–265

    work page 1998

  20. [20]

    Zeta Functions of F inite Graphs

    Motoko Kotani and Toshikazu Sunada. “Zeta Functions of F inite Graphs”. In: J. Math. Sci. Univ. Tokyo 7 (2000), pp. 7–25

    work page 2000

  21. [21]

    Spectral redemption in clustering s parse networks

    Florent Krzakala et al. “Spectral redemption in clustering s parse networks”. In: Proc. Natl. Acad. Sci. USA 110.52 (2013), pp. 20935–20940. /d.sc/o.sc/i.sc: 10.1073/pnas.1312486110

    work page doi:10.1073/pnas.1312486110 2013

  22. [22]

    On the Shannon capacity of a graph

    L ´aszl´o Lov´asz. “On the Shannon capacity of a graph”. In: IEEE Transactions on Information theory 25.1 (1979), pp. 1–7

    work page 1979

  23. [23]

    Cayley graphs: eigenvalues, expanders and random walks

    Alexander Lubotzky. “Cayley graphs: eigenvalues, expanders and random walks”. In: London Math- ematical Society Lecture Note Series (1995), pp. 155–190

    work page 1995

  24. [24]

    A note on the sharp concentration of th e chromatic number of random graphs

    Tomasz Luczak. “A note on the sharp concentration of th e chromatic number of random graphs”. In: Combinatorica 11.3 (1991), pp. 295–297. 13

    work page 1991

  25. [25]

    Community detection thresholds and the weak Ramanujan prop erty

    Laurent Massouli ´e. “Community detection thresholds and the weak Ramanujan prop erty”. In: Proc. 46th Annual ACM Symposium on /T_heory of Computing (STOC) . 2014, pp. 694–703

    work page 2014

  26. [26]

    Semidefinite Progr ams on Sparse Random Graphs and /T_heir Application to Community Detection

    Andrea Montanari and Subhabrata Sen. “Semidefinite Progr ams on Sparse Random Graphs and /T_heir Application to Community Detection”. In: Proceedings of the Forty-eighth Annual ACM Symposium on /T_heory of Computing. STOC ’16. Cambridge, MA, USA: ACM, 2016, pp. 814–827. /i.sc/s.sc/b.sc/n.sc: 978-1-4503- 4132-5. /d.sc/o.sc/i.sc: 10.1145/2897518.2897548. /u....

    work page doi:10.1145/2897518.2897548 2016

  27. [27]

    Belief propagati on, robust reconstruction and optimal recovery of block models

    Elchanan Mossel, Joe Neeman, and Allan Sly. “Belief propagati on, robust reconstruction and optimal recovery of block models”. In: Proc. 27th Conference on Learning /T_heory, COLT . 2014, pp. 356–370

    work page 2014

  28. [28]

    On the second eigenvalue of a graph

    Alon Nilli. “On the second eigenvalue of a graph”. In: Discrete Mathematics 91.2 (1991), pp. 207–210

    work page 1991

  29. [29]

    Tight estimates for eigenvalues of regular grap hs

    Alon Nilli. “Tight estimates for eigenvalues of regular grap hs”. In: the electronic journal of combina- torics 11.1 (2004), p. 9

    work page 2004

  30. [30]

    Spectral clustering of graphs with the bethe hessian

    Alaa Saade, Florent Krzakala, and Lenka Zdeborov ´a. “Spectral clustering of graphs with the bethe hessian”. In: Advances in Neural Information Processing Systems . 2014, pp. 406–414

    work page 2014

  31. [31]

    A comparison of the Delsarte and Lov ´asz bounds

    Alexander Schrijver. “A comparison of the Delsarte and Lov ´asz bounds”. In: IEEE Transactions on Information /T_heory 25.4 (1979), pp. 425–429

    work page 1979

  32. [32]

    Sharp concentration of the chromatic number on random graphsG n, p

    Eli Shamir and Joel Spencer. “Sharp concentration of the chromatic number on random graphsG n, p”. In: Combinatorica 7.1 (1987), pp. 121–129

    work page 1987

  33. [33]

    An alon-boppana ty pe bound for weighted graphs and lower- bounds for spectral sparsification

    Nikhil Srivastava and Luca Trevisan. “An alon-boppana ty pe bound for weighted graphs and lower- bounds for spectral sparsification”. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Sympo- sium on Discrete Algorithms . SIAM. 2018, pp. 1306–1315

    work page 2018

  34. [34]

    Zeta functions of graphs: a stroll through the garden

    Audrey Terras. Zeta functions of graphs: a stroll through the garden . Vol. 128. Cambridge University Press, 2010

    work page 2010

  35. [35]

    Phase Transitions in the Coloring of Ra ndom Graphs

    Lenka Zdeborov ´a and Florent Krzakala. “Phase Transitions in the Coloring of Ra ndom Graphs”. In: Physical Review E: Statistical, Nonlinear, and So/f_t Ma/t_ter Ph ysics 76 (2007), p. 031131. 14

    work page 2007