High-girth near-Ramanujan graphs with localized eigenvectors

Nikhil Srivastava; Noga Alon; Shirshendu Ganguly

High-girth near-Ramanujan graphs with localized eigenvectors

T0 review · 0 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read High-girth expanders exist whose many eigenvectors live entirely on tiny sets.

desk verdict A sound and interesting construction: high-girth expanders with localized eigenvectors; the proof's delicate layer-regularity check survives scrutiny. read the letter →

arxiv 1908.03694 v1 pith:VQJDKFOR submitted 2019-08-10 math.CO cs.DMmath-phmath.MPmath.SP

Noga Alon , Shirshendu Ganguly , Nikhil Srivastava This is my paper · ORCID

classification math.COcs.DMmath-phmath.MPmath.SP MSC 05C5005C35

keywords high-girthgraphsRamanujaneigenvectorlocalizationspectralgapquantumergodicityonscarringd-arytreesvertexexpansion

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves that for every prime $d$ and every $\alpha\in(0,1/6)$, there are infinitely many $(d+1)$-regular graphs whose nontrivial eigenvalues are all at most $(3/\sqrt{2})\sqrt{d}$, whose shortest cycles grow like $2\alpha\log_d m$, and which have at least $\lfloor\alpha\log_d m\rfloor$ eigenvalues whose eigenvectors are supported entirely on a set of size $O(m^\alpha)$. Earlier work produced such localized eigenvectors in high-girth graphs without expansion; this construction adds a near-Ramanujan spectral gap, so expansion and high girth do not force delocalization. The result is a discrete analogue of the 'scarring' phenomenon in quantum ergodic systems, and the graphs are constructed explicitly. The eigenvalues carried by the localized eigenvectors are dense in the whole bulk interval $(-2\sqrt{d},2\sqrt{d})$.

What carries the argument

The construction starts from an explicit family of $(d+1)$-regular Ramanujan graphs and selects a vertex $u$; the ball of radius $r=\lfloor\alpha\log_d m\rfloor$ around $u$ is a $d$-ary tree $T_1$. Two isomorphic copies $T_2,T_3$ are glued respectively to the leaves of $T_1$ and to vertices at distance $r+1$ from $u$ in the base graph, using a deterministic leaf-pairing that preserves high girth (the pair-swapping method for high-girth regular graphs). The spectral control is carried by a growth-rate lemma: a positive radial test function $s$ is defined on the distance layers from the interface set $X=\{u,u'\}$ so that $As(v)\le|\mu|s(v)$ holds up to half the girth; the lemma then forces the mass of any eigenvector of eigenvalue $\mu$ on the interface to be negligible, yielding the bound $|\mu|\le \frac{3d-1}{\sqrt{d}(2d-1)}\sqrt{d}<\frac{3}{\sqrt2}\sqrt{d}$ for large $d$. Localized eigenvectors come from radial eigenvectors of the finite $d$-ary trees, whose eigenvalues are dense in $(-2\sqrt{d},2\sqrt{d})$; the glued trees carry these vectors with zero extension to the rest of the graph.

What would settle it

Compute the full adjacency spectrum of the explicit graph for a small prime $d$ (say $d=2$) and a moderate $m$ with $\alpha=0.1$, and check whether any nontrivial eigenvalue exceeds $(3/\sqrt{2})\sqrt{d}+\epsilon$ or whether the claimed tree-supported eigenvectors have support larger than $O(m^\alpha)$; a single violation refutes the theorem. A simpler verification is to check the inequality $As(v)\le|\mu|s(v)$ for the explicit test function $s$ at every layer of the constructed graph.

Watch

Extended reading notes

Core claim

The central claim is that high girth and a near-optimal spectral gap are compatible with extreme eigenvector localization. For every prime $d$ and $\alpha\in(0,1/6)$, the paper constructs infinitely many $(d+1)$-regular graphs $G_m$ on $m$ vertices such that (i) every nontrivial eigenvalue of the adjacency matrix has absolute value at most $(3/\sqrt{2})\sqrt{d}$; (ii) the girth is at least $2\alpha\log_d m\,(1-o_d(1))$; and (iii) there are at least $\lfloor\alpha\log_d m\rfloor$ eigenvalues in $(-2\sqrt{d},2\sqrt{d})$ whose eigenvectors vanish outside a set $S_m$ of size $O(m^\alpha)$. Moreover, the eigenvalues realized by these localized eigenvectors are dense in $(-2\sqrt{d},2\sqrt{d})$. Because the graphs satisfy the tree-convergence and spectral-gap hypotheses used in quantum ergodicity theorems on graphs, this shows that those hypotheses cannot imply unique ergodicity in the strong sense of every subsequence of eigenvectors equidistributing.

Load-bearing premise

The spectral argument would collapse if the explicitly built radial test function fails to satisfy $As(v)\le|\mu|s(v)$ at any vertex within half the girth, which is why the parameters are restricted to $\alpha<1/6$ so the base Ramanujan graph's girth stays above $4r$.

Editorial extensions

If this is right

The graphs satisfy the Benjamini–Schramm tree-convergence condition and a spectral gap, yet they carry eigenvectors completely localized on small sets; therefore the two hypotheses used in the graph quantum ergodicity theorem cannot imply unique ergodicity in the sense of every subsequence of eigenvectors becoming equidistributed.
The localized eigenvalues are dense in $(-2\sqrt{d},2\sqrt{d})$, so localization occurs at essentially every frequency in the bulk of the spectrum, not only near the spectral edges.
A modified construction (Theorem 1.3) produces $\lfloor\alpha\log_d m\rfloor$ eigenvalues each with multiplicity $\Omega(m^{1-4\alpha})$, with an orthogonal basis of localized eigenvectors for each eigenspace; this gives many localized modes in a narrow spectral window.
The spectral bound $\frac{3}{\sqrt2}\sqrt{d}\approx 2.121\sqrt{d}$ lies within a few percent of the optimal $2\sqrt{d}$ for an infinite family, and the paper notes this construction cannot be improved to $2\sqrt{d}$ because a certain small set has vertex expansion below $(d+1)/2$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the spectral analysis is correct, the same gluing recipe should work with any good spectral expander as the base, not only Ramanujan graphs; the superharmonic test function only uses the regularity of distance layers, so the $3/\sqrt2$ bound may persist for a wider class of bases after adjusting constants.
The density of localized eigenvalues suggests that, for these graphs, the average over a spectral window of width about $1/\log m$ would likely fail to equidistribute; the paper leaves this question open (Remark 1.2), and a finite computation could test it directly.
Because the construction is explicit and deterministic, it provides a concrete testbed for numerical studies of eigenvector statistics on expanding high-girth graphs, complementing random regular graphs where such localization is much weaker.
One could try to push the localization radius exponent $\alpha$ beyond $1/6$ by using base graphs with girth larger than $\frac23\log_d m$; the paper's restriction $\alpha<1/6$ comes from the currently available girth of explicit Ramanujan families, so a new family with girth $c\log m$ for $c>2/3$ would improve the theorem.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The central result is new and worth knowing: for every prime d and alpha in (0,1/6), there are infinitely many (d+1)-regular graphs that are simultaneously near-Ramanujan, have logarithmic girth, and admit many eigenvectors fully supported on sublinear sets. This strengthens the earlier Ganguly–Srivastava construction by adding a spectral gap, and it gives a clean counterexample to the strong form of quantum ergodicity on graphs. The denseness of the localized eigenvalues is a nice bonus.

The proof is careful and mostly convincing. The key spectral step is Proposition 4.1, which uses Kahale's lemma to bound the mass of any eigenvector on the interface sets. The delicate point is the regularity of the distance layers around X={u,u'}, and the removed matching edges are exactly what make it work: they push the T3 attachments far from X, so within the ball of radius r+t the graph looks like a regular layered tree. I checked that the superharmonicity inequalities in (12) line up with the degree counts, and they do. The dependence on prior work, including the authors' own GS18, is clearly disclosed and not circular.

Soft spots are minor. The claim that the construction is 'explicit' is a bit generous: the matching in Lemma 2.1 comes from an Erdős–Sachs style extremal argument, so it is deterministic but not constructively specified. The spectral gap is (3/sqrt(2)) sqrt(d) rather than the optimal 2 sqrt(d), and the girth is at most about (1/3) log m, so the title's 'high-girth' should be read as logarithmic, not optimal. The multi-tree extension in Theorem 1.3 is plausible but terse; it says the same arguments apply without fully checking the layer structure for multiple interfaces. None of these threaten the main result.

Overall, this is a solid paper that deserves a serious referee. I would send it out and expect acceptance after minor revision, perhaps with a more measured word than 'explicit' and a short appendix on the multi-tree case.

Recommendation: accept, with minor comments.

Referee Report

0 major / 4 minor

Summary. The paper constructs, for every prime d and every alpha in (0,1/6), an infinite family of (d+1)-regular graphs G_m with girth at least 2 alpha log_d(m)(1-o_d(1)), all nontrivial adjacency eigenvalues bounded in absolute value by (3/sqrt(2))sqrt(d), and at least floor(alpha log_d m) eigenvalues whose eigenvectors are supported on a set of size O(m^alpha). The construction combines a deterministic Erdős–Sachs-style pairing of two d-ary trees (Lemma 2.1) with a high-girth non-bipartite Ramanujan graph H of Lubotzky–Phillips–Sarnak, attaching two additional trees at the leaves of a ball in H. The spectral analysis uses Kahale's growth lemma for eigenfunctions to show that the mass of any large-eigenvalue eigenvector on the interface between the trees and H is negligible, yielding the near-Ramanujan bound. A variant with several well-separated attachments produces many localized eigenvectors with large multiplicity, and the set of localized eigenvalues over the family is dense in (-2 sqrt(d), 2 sqrt(d)).

Significance. If the proof is correct, the paper gives the first construction of high-girth expanders with strongly localized eigenvectors, simultaneously achieving near-optimal spectral gap, logarithmic girth, and small support for many eigenvectors. This strengthens the earlier non-expanding examples of Ganguly–Srivastava and provides a discrete analogue of scarring phenomena relevant to quantum ergodicity on graphs, since the constructed graphs satisfy the Benjamini–Schramm and expansion hypotheses of Anantharaman–Le Masson yet have localized eigenfunctions. The proof is largely self-contained and the main spectral estimate rests on a careful application of a lemma of Kahale; the combinatorial tree-pairing lemma is proved in detail. The paper also includes a high-multiplicity variant and a density statement for the localized eigenvalues, both of which are natural strengthenings of the main theorem.

minor comments (4)

[Section 4, proof of Proposition 4.1] The verification of inequality (12) for v in X_{r+1} is terse: the text says it suffices to check that sqrt(d) s_{r+1}/x_1 + sqrt(d) x_2 s_{r+1} <= |mu| s_{r+1}, and that this follows from x_2 <= b + epsilon - 1/x_1. Since x_1 = 1/c and b = c + 1/c, this yields x_2 <= 1/c + epsilon, which is exactly what the displayed inequality needs; spelling out this substitution would make the argument easier to follow.
[Section 4, definition of b] The printed definition of b as `b = 3d-1/√d(2d-1)` is ambiguous. It should read b = (3d-1)/sqrt(d(2d-1)), which equals c + 1/c for c = sqrt((2d-1)/d); the current typography could mislead a reader about the algebra that follows.
[Section 3 and Section 4] After the matching edges u_i v_i are removed, each v_i is disconnected from its former parent u_i within the local ball of radius r+t, so the branches of T3 attach to H only deep beyond the radii used in the proof of Proposition 4.1. Adding a short remark to this effect would preempt the natural concern that the glued trees T2 and T3 interfere with the layered regularity required by Lemma 4.2.
[Lemma 2.1] In the proof of Lemma 2.1, the notation m(r,s) for the number of paths conflicts with the use of m for the number of vertices elsewhere in the paper; renaming the path count (for example, to N(r,s)) would improve clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the spectral and localization results are derived from explicit constructions and independent lemmas, not from fitted inputs or self-referential definitions.

full rationale

The paper's central claim (Theorem 1.2) is proved by an explicit construction: take an LPS Ramanujan graph, attach two d-ary trees via a deterministic Erdős–Sachs pairing, and analyze the spectrum. The near-Ramanujan bound in Proposition 4.1 is obtained by a direct quadratic-form decomposition (equations (7)–(11)) followed by Kahale's Lemma 4.2 applied to explicitly constructed radial test functions. The constant b=(3d-1)/(sqrt(d)(2d-1)) is derived from the recurrence x_{i+1}=min{b+eps-1/x_i, c}, not fitted to force the conclusion; the superharmonicity condition (12) is verified layer-by-layer. The localized eigenvectors come from radial eigenvalues of finite d-ary trees (Lemmas 3.2–3.5), cited from the authors' prior [GS18]; those lemmas are parameter-free, concern tree spectra only, do not assume the target expansion or localization results, and are used as independent mathematical facts, with the key eigenvector construction (Lemma 3.5) proved in the present paper. No quantity is fitted to a subset of the data, no uniqueness theorem is imported from the authors to forbid alternatives, and no known result is merely renamed. The paper even flags its own limitation (Remark 4.1: the graphs are not quite Ramanujan), which shows the argument is not engineered to claim more than the proof gives. Hence there is no circular step.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical or mathematical entities, no fitted constants, and no new axioms. It relies on standard published theorems: LPS Ramanujan graphs, Kahale's eigenfunction growth lemma, and the authors' prior radial-tree lemmas. The only tunable parameter is alpha in (0,1/6), which is a theorem variable rather than a fitted value; the restriction is needed for the disjointness condition (6).

assumptions (4)

standard math Existence of (d+1)-regular non-bipartite Ramanujan graphs with girth at least (2/3)log_d(m) for infinitely many m (LPS88).
Used as the base graph H in Section 3; the construction inherits spectral and girth guarantees from it.
standard math Kahale's Lemma 4.2 on growth of eigenfunction mass near symmetric sets ([Kah95], Lemma 5.1).
Central tool in Proposition 4.1 for bounding eigenvector mass on the interface sets L1 and L2.
standard math Radial eigenvalue facts for finite d-ary trees ([GS18], Lemmas 3.2 and 3.3).
Used to supply localized eigenvectors and density of eigenvalues in (-2sqrt(d),2sqrt(d)).
standard math Tree eigenvector mass lemma ([GS18], Lemma 3.3, restated as Lemma 3.4).
Used for constructing eigenvectors supported on V1 union V2 and for the partial localization remark.

how reviews work

0 comments

Cite this review

Pith. "Pith review of High-girth near-Ramanujan graphs with localized eigenvectors." pith.science (2026). https://pith.science/paper/VQJDKFOR

@misc{pith2026190803694,
  author       = {Pith},
  title        = {Pith review of: High-girth near-Ramanujan graphs with localized eigenvectors},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VQJDKFOR}},
  note         = {Machine review of arXiv:1908.03694}
}

abstract

We show that for every prime $d$ and $\alpha\in (0,1/6)$, there is an infinite sequence of $(d+1)$-regular graphs $G=(V,E)$ with girth at least $2\alpha \log_{d}(|V|)(1-o_d(1))$, second adjacency matrix eigenvalue bounded by $(3/\sqrt{2})\sqrt{d}$, and many eigenvectors fully localized on small sets of size $O(|V|^\alpha)$. This strengthens the results of Ganguly-Srivastava, who constructed high girth (but not expanding) graphs with similar properties, and may be viewed as a discrete analogue of the "scarring" phenomenon observed in the study of quantum ergodicity on manifolds. Key ingredients in the proof are a technique of Kahale for bounding the growth rate of eigenfunctions of graphs, discovered in the context of vertex expansion and a method of Erd\H{o}s and Sachs for constructing high girth regular graphs.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 17 canonical work pages

[1]

Permutations resilient to deletions

Noga Alon, Steve Butler, Ron Graham, and Utkrisht C Rajkumar. Permutations resilient to deletions. Annals of Combinatorics , 22(4):673--680, 2018

work page 2018
[2]

Quantum ergodicity on large regular graphs

Nalini Anantharaman and Etienne Le Masson. Quantum ergodicity on large regular graphs. Duke Math. J. , 164(4):723--765, 2015

work page 2015
[3]

Delocalization of schr \"o dinger eigenfunctions

Nalini Anantharaman. Delocalization of schr \"o dinger eigenfunctions. Proceedings of the ICM, Rio de Janeiro , 2018

work page 2018
[4]

Non-localization of eigenfunctions on large regular graphs

Shimon Brooks and Elon Lindenstrauss. Non-localization of eigenfunctions on large regular graphs. Israel J. Math. , pages 1--14, 2013

work page 2013
[5]

Quantum ergodicity and averaging operators on the sphere

Shimon Brooks, Etienne Le Masson, and Elon Lindenstrauss. Quantum ergodicity and averaging operators on the sphere. International Mathematics Research Notices , 2016(19):6034--6064, 2015

work page 2016
[6]

Ergodicit \'e et fonctions propres du laplacien

Y Colin De Verdiere. Ergodicit \'e et fonctions propres du laplacien. Communications in Mathematical Physics , 102(3):497--502, 1985

work page 1985
[7]

Regul \"a re graphen gegebener taillenweite mit minimaler knotenzahl

Paul Erd o s and Horst Sachs. Regul \"a re graphen gegebener taillenweite mit minimaler knotenzahl. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe , 12(251-257):22, 1963

work page 1963
[8]

On Non-localization of Eigenvectors of High Girth Graphs

Shirshendu Ganguly and Nikhil Srivastava. On non-localization of eigenvectors of high girth graphs. arXiv preprint arXiv:1803.08038. To appear in International Mathematics Research Notices , 2018

work page Pith review arXiv 2018

Show all 19 references

[9]

Ergodic billiards that are not quantum unique ergodic (with an appendix by andrew hassell and luc hillairet)

Andrew Hassell and Luc Hillairet. Ergodic billiards that are not quantum unique ergodic (with an appendix by andrew hassell and luc hillairet). Annals of Mathematics , 171(1):605--618, 2010

2010
[10]

Expander graphs and their applications

Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc. , 43(4):439--561, 2006

2006
[11]

On the second eigenvalue and linear expansion of regular graphs

Nabil Kahale. On the second eigenvalue and linear expansion of regular graphs. In 33rd Annual Symposium on Foundations of Computer Science, 1992. Proceedings. , pages 296--303. IEEE, 1992

1992
[12]

Eigenvalues and expansion of regular graphs

Nabil Kahale. Eigenvalues and expansion of regular graphs. Journal of the ACM (JACM) , 42(5):1091--1106, 1995

1995
[13]

Quantum ergodicity and benjamini--schramm convergence of hyperbolic surfaces

Etienne Le Masson, Tuomas Sahlsten, et al. Quantum ergodicity and benjamini--schramm convergence of hyperbolic surfaces. Duke Mathematical Journal , 166(18):3425--3460, 2017

2017
[14]

Ramanujan graphs

Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica , 8(3):261--277, 1988

1988
[15]

Ramanujan graphs

M Ram Murty. Ramanujan graphs. Journal-Ramanujan Mathematical Society , 18(1):33--52, 2003

2003
[16]

On the second eigenvalue of a graph

Alon Nilli. On the second eigenvalue of a graph. Discrete Mathematics , 91(2):207--210, 1991

1991
[17]

Recent progress on the quantum unique ergodicity conjecture

Peter Sarnak. Recent progress on the quantum unique ergodicity conjecture. Bull. Amer. Math. Soc , 48:211--228, 2012

2012
[18]

Ergodic properties of eigenfunctions

Alexander I Shnirel'man. Ergodic properties of eigenfunctions. Uspekhi Matematicheskikh Nauk , 29(6):181--182, 1974

1974
[19]

Uniform distribution of eigenfunctions on compact hyperbolic surfaces

Steven Zelditch et al. Uniform distribution of eigenfunctions on compact hyperbolic surfaces. Duke mathematical journal , 55(4):919--941, 1987

1987

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Permutations resilient to deletions

Noga Alon, Steve Butler, Ron Graham, and Utkrisht C Rajkumar. Permutations resilient to deletions. Annals of Combinatorics , 22(4):673--680, 2018

work page 2018

[2] [2]

Quantum ergodicity on large regular graphs

Nalini Anantharaman and Etienne Le Masson. Quantum ergodicity on large regular graphs. Duke Math. J. , 164(4):723--765, 2015

work page 2015

[3] [3]

Delocalization of schr \"o dinger eigenfunctions

Nalini Anantharaman. Delocalization of schr \"o dinger eigenfunctions. Proceedings of the ICM, Rio de Janeiro , 2018

work page 2018

[4] [4]

Non-localization of eigenfunctions on large regular graphs

Shimon Brooks and Elon Lindenstrauss. Non-localization of eigenfunctions on large regular graphs. Israel J. Math. , pages 1--14, 2013

work page 2013

[5] [5]

Quantum ergodicity and averaging operators on the sphere

Shimon Brooks, Etienne Le Masson, and Elon Lindenstrauss. Quantum ergodicity and averaging operators on the sphere. International Mathematics Research Notices , 2016(19):6034--6064, 2015

work page 2016

[6] [6]

Ergodicit \'e et fonctions propres du laplacien

Y Colin De Verdiere. Ergodicit \'e et fonctions propres du laplacien. Communications in Mathematical Physics , 102(3):497--502, 1985

work page 1985

[7] [7]

Regul \"a re graphen gegebener taillenweite mit minimaler knotenzahl

Paul Erd o s and Horst Sachs. Regul \"a re graphen gegebener taillenweite mit minimaler knotenzahl. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe , 12(251-257):22, 1963

work page 1963

[8] [8]

On Non-localization of Eigenvectors of High Girth Graphs

Shirshendu Ganguly and Nikhil Srivastava. On non-localization of eigenvectors of high girth graphs. arXiv preprint arXiv:1803.08038. To appear in International Mathematics Research Notices , 2018

work page Pith review arXiv 2018