pith. sign in

arxiv: 2604.17907 · v1 · submitted 2026-04-20 · 🧮 math.CO

On Spielman's Laplacian Eigenratio Conjecture and Related Problems

Jie Ma , Quanyu Tang , Yuchang Wang , Zhiheng Zheng This is my paper

Pith reviewed 2026-05-10 04:39 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C5005C75
keywords Laplacian eigenvalueseigenratioSpielman conjectureRamanujan graphsregular graphsspectral graph theorytreesHamiltonian graphs
0
0 comments X

The pith

Spielman's Laplacian eigenratio conjecture fails for infinitely many average degrees above 2 but holds for regular graphs and low average degrees.

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

The paper tests Spielman's conjecture that for graphs with average degree d the ratio of the second smallest Laplacian eigenvalue to the largest is at most (d minus twice the square root of d minus one) over (d plus twice the square root of d minus one) plus a vanishing term. It finds the conjecture false for infinitely many d greater than 2 by building examples from bipartite Ramanujan graphs. The conjecture is verified for every graph with average degree at most 2. For regular graphs the paper proves the bound and stronger comparisons among higher eigenvalues. These results also imply new spectral properties for Ramanujan graphs and resolve two other conjectures on trees and Hamiltonicity.

Core claim

The conjecture fails for infinitely many average degrees d>2 via constructions based on bipartite Ramanujan graphs. It holds for all average degrees d≤2 and for all regular graphs, where stronger bounds comparing higher Laplacian eigenvalues are obtained. Consequently, every sufficiently large d-regular Ramanujan graph has linearly many adjacency eigenvalues below −2√(d−1)+ε. The paper also settles the You-Liu conjecture on the maximum Laplacian eigenratio of trees and Gu's conjecture on the Hamiltonicity of graphs with large Laplacian eigenratio.

What carries the argument

Constructions of graphs from bipartite Ramanujan graphs to produce counterexamples to the eigenratio bound, combined with spectral analysis for regular graphs.

If this is right

  • The eigenratio bound holds for all graphs with average degree d ≤ 2.
  • It holds for all regular graphs with comparisons on higher eigenvalues.
  • Large d-regular Ramanujan graphs have linearly many adjacency eigenvalues below -2√(d-1) + ε for any ε > 0.
  • The maximum Laplacian eigenratio among trees is determined.
  • Graphs with sufficiently large Laplacian eigenratio are Hamiltonian.

Where Pith is reading between the lines

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

  • The distinction between regular and non-regular graphs suggests that regularity plays a key role in achieving optimal spectral ratios.
  • These findings may inform the design of graphs with desired expansion properties in network theory.
  • Further exploration could check if similar mixed behaviors occur in other eigenvalue conjectures.

Load-bearing premise

The counterexamples for average degrees greater than 2 depend on the existence of infinite families of bipartite Ramanujan graphs at those degrees.

What would settle it

A specific construction or disproof of bipartite Ramanujan graphs for a d > 2 where the eigenratio bound is violated would confirm or refute the failure of the conjecture for that degree.

read the original abstract

Let $G$ be an $n$-vertex graph with Laplacian eigenvalues $0=\lambda_1(G)\le \lambda_2(G)\le\cdots\le \lambda_n(G)$. Motivated by the Alon-Boppana bound and the Ramanujan phenomenon for regular graphs, Spielman conjectured that, for every graph $G$ with fixed average degree $d\ge 1$, its Laplacian eigenratio satisfies $$ \frac{\lambda_2(G)}{\lambda_n(G)} \le \frac{d-2\sqrt{d-1}}{d+2\sqrt{d-1}}+o_n(1), $$ where $o_n(1)\to 0$ as $n\to\infty$. The main purpose of this paper is to investigate this conjecture. We show that the situation is mixed. On the negative side, the conjecture fails for infinitely many average degrees $d>2$, via constructions based on bipartite Ramanujan graphs. On the positive side, it holds in two important settings: we verify it for all average degrees $d\le 2$, and we prove it for all regular graphs. In fact, for regular graphs we obtain stronger bounds comparing higher Laplacian eigenvalues. As a consequence, we show that for every fixed $d\ge 3$ and every $\varepsilon>0$, every sufficiently large $d$-regular Ramanujan graph has linearly many adjacency eigenvalues below $-2\sqrt{d-1}+\varepsilon$, thereby strengthening earlier results of Li and Cioab\u{a} by giving an unconditional result of this form. We also settle two related conjectures: one of You and Liu concerning the maximum Laplacian eigenratio of trees, and one of Gu concerning the Hamiltonicity of graphs with large Laplacian eigenratio.

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 / 3 minor

Summary. The paper investigates Spielman's conjecture that for any n-vertex graph G with fixed average degree d ≥ 1, the Laplacian eigenratio λ₂(G)/λₙ(G) is at most (d − 2√(d−1))/(d + 2√(d−1)) + oₙ(1). It disproves the conjecture for infinitely many d > 2 via explicit constructions based on bipartite Ramanujan graphs, proves the bound holds for all d ≤ 2 and for every regular graph (with stronger comparisons among higher Laplacian eigenvalues), and deduces that every sufficiently large d-regular Ramanujan graph has linearly many adjacency eigenvalues below −2√(d−1) + ε. The paper also resolves two related conjectures: the maximum eigenratio among trees (You–Liu) and Hamiltonicity for graphs with large eigenratio (Gu).

Significance. If the proofs are correct, the work supplies a mixed but definitive resolution of the conjecture together with two ancillary results. The counterexamples are concrete and rely on known infinite families of bipartite Ramanujan graphs; the positive results for regular graphs and d ≤ 2 rest on standard spectral-graph techniques and yield strictly stronger eigenvalue comparisons. The unconditional linear-eigenvalue consequence for Ramanujan graphs improves earlier conditional statements of Li and Cioabă. Settling the You–Liu and Gu conjectures adds immediate value to the literature.

major comments (2)
  1. [§3 (counterexamples)] The counterexample construction for d > 2 (presumably §3) invokes the existence of infinite families of bipartite Ramanujan graphs for those specific degrees. While the literature supplies such families for many d, the manuscript should state explicitly the arithmetic conditions on d under which the families are known to exist, so that the precise set of counterexample degrees is transparent.
  2. [§4 (regular graphs) and consequence paragraph] In the regular-graph case (presumably §4), the stronger comparison of higher Laplacian eigenvalues is used to obtain the linear number of adjacency eigenvalues below −2√(d−1) + ε. The passage from the Laplacian eigenratio bound to the adjacency-eigenvalue count should include an explicit error-term calculation showing that the oₙ(1) term remains controllable uniformly for all sufficiently large n.
minor comments (3)
  1. [Introduction] The notation oₙ(1) is introduced in the abstract and introduction but never restated with its precise meaning (limit as n → ∞ with d fixed). A single sentence clarifying the quantifiers would remove any ambiguity.
  2. [§3] Several citations to the Ramanujan-graph literature appear only in the bibliography; inline references at the first use of each family would improve readability.
  3. [Conclusion] The statement of the You–Liu conjecture (trees) and its resolution could be placed in a short dedicated subsection rather than appearing only in the final paragraph.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and have incorporated revisions where appropriate to improve clarity and rigor.

read point-by-point responses

  1. Referee: [§3 (counterexamples)] The counterexample construction for d > 2 (presumably §3) invokes the existence of infinite families of bipartite Ramanujan graphs for those specific degrees. While the literature supplies such families for many d, the manuscript should state explicitly the arithmetic conditions on d under which the families are known to exist, so that the precise set of counterexample degrees is transparent.

    Authors: We agree that explicitly identifying the arithmetic conditions on d improves transparency. In the revised manuscript, we have added a sentence in Section 3 stating that the constructions rely on the known infinite families of bipartite Ramanujan graphs existing for all degrees d = q + 1 where q is a prime power (via the Lubotzky–Phillips–Sarnak construction and its extensions). This yields infinitely many counterexample degrees d > 2 while leaving the disproof intact for those d. revision: yes

  2. Referee: [§4 (regular graphs) and consequence paragraph] In the regular-graph case (presumably §4), the stronger comparison of higher Laplacian eigenvalues is used to obtain the linear number of adjacency eigenvalues below −2√(d−1) + ε. The passage from the Laplacian eigenratio bound to the adjacency-eigenvalue count should include an explicit error-term calculation showing that the oₙ(1) term remains controllable uniformly for all sufficiently large n.

    Authors: We thank the referee for this suggestion. The consequence paragraph uses the stronger eigenvalue comparisons for regular graphs to control the o_n(1) term, but we have now added an explicit error-term calculation in the revised version. This shows that, for fixed d and ε > 0, the uniform bound on the eigenratio (independent of n) ensures at least c n adjacency eigenvalues lie below −2√(d−1) + ε for some c > 0 and all sufficiently large n, making the linear count fully rigorous. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper's negative results for the conjecture rely on constructions from external families of bipartite Ramanujan graphs in prior literature, while positive results for all d ≤ 2 and all regular graphs (including stronger eigenvalue bounds) are derived from standard Laplacian spectral properties and comparisons without any reduction to fitted parameters, self-definitions, or load-bearing self-citations. The o_n(1) handling and consequences for Ramanujan graphs use known external results without circular reduction. No step equates a claimed prediction or uniqueness to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper operates entirely within standard spectral graph theory; no free parameters are fitted, no new entities postulated, and axioms are background facts about Laplacian spectra.

axioms (2)
  • standard math Laplacian eigenvalues satisfy 0=λ1(G) ≤ λ2(G) ≤ ⋯ ≤ λn(G) for any graph G
    Invoked throughout the abstract in the definition of the eigenratio and all stated bounds.
  • domain assumption Existence of infinite families of bipartite Ramanujan graphs for certain degrees
    Used to construct counterexamples for d>2; this is a known but non-trivial assumption from prior literature.

pith-pipeline@v0.9.0 · 5619 in / 1483 out tokens · 40223 ms · 2026-05-10T04:39:20.317222+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

31 extracted references · 31 canonical work pages

  1. [1]

    Eigenvalues and expanders,

    N. Alon, “Eigenvalues and expanders,”Combinatorica, vol. 6, no. 2, pp. 83–96, 1986

    work page 1986

  2. [2]

    R. B. Bapat,Graphs and Matrices, Springer, London, 2010

    work page 2010

  3. [3]

    The spectrum of the corona of two graphs,

    S. Barik, S. Pati, and B. K. Sarma, “The spectrum of the corona of two graphs,”SIAM J. Discrete Math., vol. 21, no. 1, pp. 47–56, 2007

    work page 2007

  4. [4]

    Eigenvalues and graph bisection: An average-case analysis,

    R. B. Boppana, “Eigenvalues and graph bisection: An average-case analysis,” inProceedings of the 28th Annual Symposium on Foundations of Computer Science (FOCS ’87), Los Alamitos, CA: IEEE Computer Society, 1987, pp. 280–285

    work page 1987

  5. [5]

    On the extreme eigenvalues of regular graphs,

    S. M. Cioab˘ a, “On the extreme eigenvalues of regular graphs,”J. Combin. Theory Ser. B, vol. 96, no. 3, pp. 367–373, 2006

    work page 2006

  6. [6]

    G. P. Davidoff, P. Sarnak, and A. Valette,Elementary Number Theory, Group Theory, and Ramanujan Graphs, vol. 55. Cambridge: Cambridge Univ. Press, 2003

    work page 2003

  7. [7]

    Hamiltonicity of expanders: optimal bounds and applications.arXiv preprint arXiv:2402.06603, 2024

    N. Dragani´ c, R. Montgomery, D. M. Correia, A. Pokrovskiy, and B. Sudakov, “Hamiltonicity of expanders: optimal bounds and applications,”arXiv preprint arXiv:2402.06603v2, 2024

    work page arXiv 2024

  8. [8]

    Some geometric aspects of graphs and their eigenfunctions,

    J. Friedman, “Some geometric aspects of graphs and their eigenfunctions,”Duke Math. J., vol. 69, pp. 487– 525, 1993

    work page 1993

  9. [9]

    A proof of Alon’s second eigenvalue conjecture,

    J. Friedman, “A proof of Alon’s second eigenvalue conjecture,” inProceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC ’03), New York: Association for Computing Machinery, 2003, pp. 720–724. 22

    work page 2003

  10. [10]

    On the corona of two graphs,

    R. Frucht and F. Harary, “On the corona of two graphs,”Aequationes Math., vol. 4, pp. 322–325, 1970

    work page 1970

  11. [11]

    Graph toughness from Laplacian eigenvalues,

    X. Gu and W. H. Haemers, “Graph toughness from Laplacian eigenvalues,”Algebr. Combin., vol. 5, no. 1, pp. 53–61, 2022

    work page 2022

  12. [12]

    Interlacing eigenvalues and graphs,

    W. H. Haemers, “Interlacing eigenvalues and graphs,”Linear Algebra Appl., vol. 226/228, pp. 593–616, 1995

    work page 1995

  13. [13]

    Expander graphs and their applications,

    S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their applications,”Bull. Amer. Math. Soc., vol. 43, no. 4, pp. 439–561, 2006

    work page 2006

  14. [14]

    Huang, T

    J. Huang, T. McKenzie, and H.-T. Yau, “Ramanujan Property and Edge Universality of Random Regular Graphs,”arXiv preprint arXiv:2412.20263, 2024

    work page arXiv 2024

  15. [15]

    On the second eigenvalue and linear expansion of regular graphs,

    N. Kahale, “On the second eigenvalue and linear expansion of regular graphs,” in33rd Annu. Symp. Found. Comput. Sci. (FOCS 1992), pp. 296–305, IEEE, 1992

    work page 1992

  16. [16]

    On negative eigenvalues of regular graphs,

    W.-C. W. Li, “On negative eigenvalues of regular graphs,”C. R. Acad. Sci. Paris S´ er. I Math., vol. 333, no. 10, pp. 907–912, 2001

    work page 2001

  17. [17]

    New bounds on the Laplacian spectral ratio of connected graphs,

    Z. Lin, M. Cai, and J. Wang, “New bounds on the Laplacian spectral ratio of connected graphs,”Czechoslo- vak Math. J., vol. 74, pp. 1207–1220, 2024

    work page 2024

  18. [18]

    An improved result on Laplacian spectral ratio of connected graphs,

    Z. Lin and L. Miao, “An improved result on Laplacian spectral ratio of connected graphs,”J. Inform. Optim. Sci., vol. 42, pp. 711–718, 2021

    work page 2021

  19. [19]

    Unsolved problems in spectral graph theory,

    L. Liu and B. Ning, “Unsolved problems in spectral graph theory,”Oper. Res. Trans., vol. 27, no. 4, pp. 33–60, 2023

    work page 2023

  20. [20]

    The Laplacian spectrum of corona of two graphs,

    Q. Liu, “The Laplacian spectrum of corona of two graphs,”Kragujevac J. Math., vol. 38, no. 1, pp. 163–170, 2014

    work page 2014

  21. [21]

    Ramanujan graphs,

    A. Lubotzky, R. Phillips, and P. Sarnak, “Ramanujan graphs,”Combinatorica, vol. 8, no. 3, pp. 261–277, 1988

    work page 1988

  22. [22]

    Existence and explicit constructions ofq+ 1 regular Ramanujan graphs for every prime powerq,

    M. Morgenstern, “Existence and explicit constructions ofq+ 1 regular Ramanujan graphs for every prime powerq,”Journal of Combinatorial Theory, Series B, vol. 62, no. 1, pp. 44–62, 1994

    work page 1994

  23. [23]

    Interlacing families. I. Bipartite Ramanujan graphs of all degrees,

    A. W. Marcus, D. A. Spielman, and N. Srivastava, “Interlacing families. I. Bipartite Ramanujan graphs of all degrees,”Ann. of Math., vol. 182, pp. 307–325, 2015

    work page 2015

  24. [24]

    Interlacing families IV: Bipartite Ramanujan graphs of all sizes,

    A. W. Marcus, D. A. Spielman, and N. Srivastava, “Interlacing families IV: Bipartite Ramanujan graphs of all sizes,”SIAM J. Comput., vol. 47, no. 6, pp. 2488–2509, 2018

    work page 2018

  25. [25]

    Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators,

    G. A. Margulis, “Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators,”Probl. Peredachi Inf., vol. 24, no. 1, pp. 51–60, 1988

    work page 1988

  26. [26]

    A strengthening and a multipartite generalization of the Alon–Boppana–Serre theorem,

    B. Mohar, “A strengthening and a multipartite generalization of the Alon–Boppana–Serre theorem,”Proc. Amer. Math. Soc., vol. 138, no. 11, pp. 3899–3909, 2010

    work page 2010

  27. [27]

    On the second eigenvalue of a graph,

    A. Nilli, “On the second eigenvalue of a graph,”Discrete Math., vol. 91, no. 2, pp. 207–210, 1991

    work page 1991

  28. [28]

    Tight estimates for eigenvalues of regular graphs,

    A. Nilli, “Tight estimates for eigenvalues of regular graphs,”Electron. J. Combin., vol. 11, no. 1, Note N9, 2004

    work page 2004

  29. [29]

    R´ epartition asymptotique des valeurs propres de l’op´ erateur de HeckeTp,

    J.-P. Serre, “R´ epartition asymptotique des valeurs propres de l’op´ erateur de HeckeTp,”J. Amer. Math. Soc., vol. 10, no. 1, pp. 75–102, 1997

    work page 1997

  30. [30]

    D. A. Spielman,Spectral and Algebraic Graph Theory, draft/book in progress. Available at:http:// cs-www.cs.yale.edu/homes/spielman/sagt/sagt.pdf, accessed 2026-04-19

    work page 2026

  31. [31]

    On the Laplacian spectral ratio of connected graphs,

    Z. You and B. Liu, “On the Laplacian spectral ratio of connected graphs,”Appl. Math. Lett., vol. 25, pp. 1245–1250, 2012. Jie Ma:jiema@ustc.edu.cn Quanyu Tang:tang_quanyu@163.com Yuchang Wang:wyc1999@mail.ustc.edu.cn Zhiheng Zheng:lhotse@mail.ustc.edu.cn 23

    work page 2012