Pith. sign in

REVIEW 2 major objections 4 minor 4 cited by

Spectra of high-dimensional sparse random geometric graphs

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Sparse geometric graphs converge to the semicircle law at high dimension

desk verdict Novel spectral universality results for sparse random geometric graphs, but the main estimate fails for 2-edge-connected components with multiple junction vertices. read the letter →

arxiv 2507.06556 v5 pith:LQ5T5TBP submitted 2025-07-09 math.PR math.COmath.STstat.TH

Yifan Cao , Yizhe Zhu This is my paper · ORCID
classification math.PRmath.COmath.STstat.TH MSC 60B2005C8060D05
keywords randomgeometricgraphsempiricalspectraldistributionsemicirclelawsparsemomentmethodhigh-dimensionalgeometrygapKuramotosynchronization
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, in high dimensions, the global eigenvalue distribution of a sparse random geometric graph is indistinguishable from that of an Erdős–Rényi graph with the same edge density. The vertices are random points on the unit sphere, and edges are drawn when two points are close; the dependence among edges created by this geometry is shown to be asymptotically invisible to the spectrum. Under $np\to\infty$ and dimension $d=\omega(np\log^2(1/p))$, the normalized adjacency matrix converges to the semicircle law; when $p=\alpha/n$ and $d=\omega(\log^2 n)$, it converges to the same limiting distribution as $G(n,\alpha/n)$. These are the first limiting spectral results for sparse high-dimensional random geometric graphs. A quantitative bound on the second eigenvalue and an application to synchronization on Kuramoto networks follow.

What carries the argument

The proof uses the moment method on the centered adjacency matrix $Q=A-\mathbb{E}A$. Closed walks are split into tree-like walks (each edge traversed twice, contributing Catalan numbers) and all other walks. The non-tree contribution is controlled by decomposing each closed-walk graph into its block-cut tree (2-edge-connected components joined by bridges) and then peeling leaf components one at a time; within each 2-edge-connected component an ear decomposition peels paths whose endpoints are already conditioned, reducing expectations to products of marginal probabilities. The geometric dependence enters through the $p$-cap random walk on the sphere: the rate at which the walker's distribution approaches uniform controls subgraph probabilities (Lemma A.5), and the uniform contraction factor $C\tau<1$ under $d\ge C\log(1/p)$ makes each extra ear's contribution vanish.

What would settle it

For fixed $p$, increase $n$ and choose $d = np\log^2(1/p)$; compute the fourth empirical moment of $A/\sqrt{np(1-p)}$ for large $n$ and check whether it approaches 2, the semicircle moment, because the $S_2$ bound is the only source of a non-vanishing correction. Alternatively, compute numerically the cycle probability $\mathbb{P}(C_4 \subset G)-p^4$ and check whether it obeys the bound $C p^3 (C\tau)^2 \sqrt{\log(1/p)}$ from Lemma A.5.

Watch

Extended reading notes

Core claim

The central claim is a universality phenomenon: despite nontrivial edge correlations from latent geometry, the limiting spectral distribution of $G(n,d,p)$ equals that of the independent-edge Erdős–Rényi graph as soon as dimension grows fast enough. For $p\to 0$ with $np\to\infty$, the empirical spectral distribution of $A/\sqrt{np(1-p)}$ converges weakly in probability to Wigner's semicircle law under $d=\omega(np\log^2(1/p))$. For $p=\alpha/n$, with $d=\omega(\log^2 n)$, the normalized adjacency matrix has the same limiting spectral distribution as the Erdős–Rényi graph with expected degree $\alpha$. The proof also yields a second-eigenvalue bound $\lambda(A)\le O(\log^4 n\sqrt{np}+\tau np)$ in wider parameter regimes than earlier work.

Load-bearing premise

The argument rests on the p-cap random walk on the sphere mixing to near-uniform after each step, with a contraction factor $C\tau$ that stays uniformly below 1 whenever $d$ is at least a large constant times $\log(1/p)$; if that mixing bound fails at the required constant, the non-tree closed walks need not have vanishing contribution and the semicircle convergence could fail.

Editorial extensions

If this is right

  • For $np\to\infty$ and $d=\omega(np\log^2(1/p))$, the entire bulk spectrum of the adjacency matrix obeys the semicircle law, so spectral statistics cannot distinguish the geometric model from the Erdős–Rényi model.
  • For bounded expected degree $p=\alpha/n$, spectral tests cannot separate $G(n,d,p)$ from $G(n,\alpha/n)$ once $d=\omega(\log^2 n)$.
  • The new second-eigenvalue bound holds for all $d=\Omega(\log(1/p))$ and $np=\Omega(\log^4 n)$, removing the prior restrictions $np=\omega(d^3\log^4 n)$ and $\tau\ge 1/\sqrt{np}$.
  • As a corollary, the homogeneous Kuramoto model on sparse random geometric graphs synchronizes with high probability under $np=\Omega(\log^{10} n)$ and $d=\Omega(\log(1/p)\log^2 n)$, relaxing the previously required parameter regime.
  • The paper conjectures that the sharp threshold for semicircle convergence is $d\gg np\log(1/p)$, just one logarithmic factor below the proved condition.

Reading between the lines

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

  • The same ear-peeling machinery should transfer to other latent-space graph models, such as toroidal or Gaussian-mixture geometries, provided an analogous cap-mixing estimate holds.
  • If the conjectured threshold $d\gg np\log(1/p)$ is true, then spectral indistinguishability holds strictly beyond the entropic testing threshold $d\asymp np\log(1/p)$ found for total-variation and low-degree tests, implying a regime where geometry is spectrally invisible but statistically detectable.
  • The second-eigenvalue method may extend to produce a near-optimal $O(\sqrt{np})$ bound if the combinatorial count over closed walks can be sharpened; a natural test is whether the trace bound holds with $k=\Theta(\log n)$ for general subgraphs of excess one.
  • The proof imports the $p$-cap random walk mixing estimate without reproving it, so a failure of that bound at the stated constant would break the $S_2$ estimate; independent verification of Lemma A.4 is the most direct check on the whole argument.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper studies the empirical spectral distribution of sparse high-dimensional random geometric graphs G(n,d,p), where vertices are i.i.d. uniform on the sphere and edges are formed by thresholding inner products. Two main limiting results are claimed: a semicircle law when np→∞ and d=ω(np log^2(1/p)), and convergence to the Erdős–Rényi limiting spectral measure when p=α/n and d=ω(log^2 n). The proofs use the moment method, splitting closed walks into tree-like walks (S1) and non-tree walks (S2), with S2 controlled by a block-cut tree and ear-decomposition peeling algorithm. A second-eigenvalue bound and a synchronization application are also presented. The central derivation is a direct moment estimate, with subgraph probability bounds imported from a prior paper.

Significance. If correct, the results would be the first limiting spectral theorems for sparse high-dimensional random geometric graphs, and the second-eigenvalue bound would improve previous work by removing technical conditions. The block-cut tree/ear-decomposition approach is a novel and potentially useful technique for handling edge dependence in the moment method. The paper also gives concrete, falsifiable statements and a clear application to the Kuramoto model. However, the current manuscript contains a load-bearing gap in the S2 bound: the peeling argument is only justified for a 2-edge-connected component with a single junction vertex, while the sequential peeling procedure produces components with multiple fixed junction vertices. A second, independent gap appears in the tree-walk counting for the constant-expected-degree case. The theorems may be true, but the proofs as written do not establish them.

major comments (2)
  1. [§4.3.1, Step 3; equations (12)–(14), (17)–(19), and Lemma 6.1] The sequential peeling of the block-cut tree is not justified for internal 2-edge-connected components. Step 2 bounds a leaf 2-edge-connected component only when it contains exactly one junction vertex, using the cancellation in (13): every proper subset of edges of the initial cycle is a forest whose expectation is zero because at most one endpoint is fixed. After removing leaf components, the remaining 2-edge-connected component can contain two or more original junction vertices. For example, in a chain of three triangles connected by two bridges, the middle triangle has two fixed junction vertices once the two leaf triangles are processed. For a cycle with two fixed vertices, a proper subset consisting of one of the two internally disjoint paths between the fixed vertices does not have zero expectation; already a single edge with both endpoints fixed has expectation 1{<v0,v1>≥τ}−p, which is not zero. Hence identity (13) fails for this case, the bound (17) is not established for such components, and consequently (19) is not proven for every G∈G2. Since Lemma 6.1 and the S2 bound in §4.3.2 depend directly on (19), the proofs of Theorems 2.1, 2.2, 2.3, and 2.6 are incomplete for graphs whose block-cut tree has internal 2-edge-connected nodes.
  2. [§5.1, equations (29)–(30) and the claimed equality with (1)] The tree-walk count in the constant-expected-degree case does not account for walks that traverse a tree edge more than twice. In (29), the sum is over rooted planar trees T with ℓ edges, and each such tree is treated as if it corresponds to one closed walk of length k=2m via a depth-first search traversal. But the DFS traversal has length 2ℓ; when ℓ<m it is not a closed walk of length 2m. A closed walk on an ℓ-edge tree of length 2m must traverse at least one edge with multiplicity greater than 2, and there are generally several distinct walks on the same labeled tree realizing different multiplicity vectors. For example, when m=3 and ℓ=2, a path of two edges admits closed walks with multiplicities (4,2) and (2,4), not merely the single DFS walk of length 4. The paper neither specifies the multiplicity vector m(e) in the expectation in (29) nor sums over the multiplicity patterns and their walk counts. Therefore the reduction from (29) to (30) and the claimed equality with (1), in particular the α^{ℓ−m} terms for ℓ<m, are not derived. This is load-bearing for Theorem 2.2.
minor comments (4)
  1. [Abstract and Theorem 2.1] The abstract states the condition d=Ω(np log(1/p)), while Theorem 2.1 requires d=ω(np log^2(1/p)). The abstract should match the theorem statement.
  2. [§4.1, equation (4)] The condition is written as i_j ≠ j_{j−1}; this should be i_j ≠ i_{j−1}.
  3. [§4.3.1, equation (17)] The expression for the exponent of log(1/p) has misplaced parentheses: it should read (log(1/p))^{(s_{C_i}−t_{C_i}−x_{C_i})/2}, not log(...)/2(1/p).
  4. [§5.3] The variance is stated as Var(...) = (1); this should presumably be o(1).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the moment-method derivation is self-contained relative to external subgraph probability lemmas, with no fitted constants or self-citation chain carrying the argument.

full rationale

The central derivation chain is a direct moment-method estimate: S1 uses leaf peeling and E[Q_e^2]=p(1-p), and S2 imports cycle/path probability bounds from [44, Lemma A.5], an external benchmark whose quoted assumptions (d >= C1 log(1/p), Ctau<1) do not include the target semicircle or Erdős–Rényi limit. Theorems 2.1 and 2.2 are not equivalent by construction to p, d, or the model definition; the claimed universality is a nontrivial asymptotic statement about vanishing non-tree contributions. Theorem 2.3 similarly uses the same estimate (19) plus [44, Claim 3.10], again external. The only apparent vulnerability is a possible proof gap in Section 4.3.1 Step 3 (peeling leaf 2-edge-connected components that may later contain multiple junction vertices), but that is a correctness and rigor concern, not circularity: no fitted parameter is renamed a prediction, no self-citation is load-bearing, and no theorem is defined in terms of the target result. The skeptical objection about chains of triangles attacks the validity of (13) for components with two fixed endpoints, which is a missing case in the proof rather than a derivation that assumes its conclusion.

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

The paper introduces no free parameters; all constants are universal and none are fitted to data. The heavy geometric input, the p-cap mixing estimate and subgraph probability bounds, comes from [44] and is not self-cited by the present authors. The counting lemma in Theorem 2.3 also comes from [44].

assumptions (8)
  • domain assumption The G(n,d,p) model: i.i.d. uniform points on S^{d-1}, edges when inner product exceeds tau with E[1{<v_i,v_j> >= tau}] = p.
    Defines the object of study in Section 1.
  • domain assumption p-cap random walk mixing bound on the sphere (Lemma A.4, from [44]).
    Used to prove subgraph probability estimates (Lemma A.5); imported without proof from [44].
  • domain assumption Subgraph probability estimates for cycles and paths (Lemma A.5, from [44]).
    Central to the S2 bound in Sections 4 and 5; cited from [44].
  • domain assumption Counting lemma for closed walks with given parameters (Lemma 6.2, Claim 3.10 in [44]).
    Used in the proof of Theorem 2.3 to count walk patterns.
  • standard math Ear decomposition theorem and block-cut tree decomposition (Section 3.2, 3.3, Lemma 3.4).
    Combinatorial tools for decomposing closed-walk graphs.
  • standard math Moment method convergence criteria for empirical spectral distributions (Section 4.5).
    Standard random matrix theory results, e.g., [6, 4].
  • standard math Rank inequality for empirical spectral distributions (Lemma A.1).
    Used to compare A with Q and B.
  • domain assumption Deterministic synchronization theorem of Kassabov et al. (Lemma 7.1).
    Used to translate spectral gap bounds into global synchronization for the Kuramoto model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Spectra of high-dimensional sparse random geometric graphs." pith.science (2026). https://pith.science/paper/LQ5T5TBP

@misc{pith2026250706556,
  author       = {Pith},
  title        = {Pith review of: Spectra of high-dimensional sparse random geometric graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LQ5T5TBP}},
  note         = {Machine review of arXiv:2507.06556}
}
abstract

We determine the limiting empirical spectral distribution of sparse high-dimensional random geometric graphs. The vertices are independent uniform points on the unit sphere $S^{d-1}$, and two vertices are joined when their inner product exceeds a threshold chosen to give edge density $p$. The edges therefore have the same marginal probabilities as in an Erd\H{o}s--R\'enyi graph, but the latent geometry introduces dependence among them. We show that these correlations are asymptotically invisible to the global spectrum in two sparse regimes. If $p\to0$, $np\to\infty$, and $d=\Omega(np\log(1/p))$, then the empirical spectral distribution of $A/\sqrt{np}$ converges in probability to the semicircle law. If $p=\alpha/n$ for a fixed $\alpha>0$ and $d=\omega(\log n)$, then the empirical spectral distribution of $A/\sqrt{\alpha}$ converges in probability to the limiting spectral distribution of $\mathcal G(n,\alpha/n)$. The proof combines the moment method with a cluster expansion that decomposes geometric dependence into weak local interactions, allowing us to control every fixed walk pattern in the moment calculation.

Figures

Figures reproduced from arXiv: 2507.06556 by the authors.

Figure 1
Figure 1. Empirical spectral distributions of the Erd˝os-R´enyi graph G(2500, 0.01) (left) and the geometric graph G(2500, 300, 0.01) (right) [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Empirical spectral distributions of the Erd˝os-R´enyi graph G(2500, 2.23/2500) (left) and the geometric graph G(2500, 100, 2.23/2500) (right) From Lemma A.3, τ ≍ q log(1/p) d . Therefore, when d = Ω(np), Theorem 2.3 implies λ(A) = O(log4 (n) √np), showing that in high–dimensional regimes, the expansion of G(n, d, p) matches that of the Erd˝os-R´enyi graph [27, 40], up to a poly log(n) factor. The generalized Alon-Bo… view at source ↗
Figure 3
Figure 3. Ear decomposition of a 2-edge-connected graph with 11 vertices, where R1 = {(1, 2)(2, 3),(3, 4),(4, 1)}, R2 = {(2, 5),(5, 6),(6, 7),(7, 4)}, R3 = {(4, 11),(11, 7)}, and R4 = {(5, 8),(8, 9),(9, 10),(10, 7)} 3.3. Block-cut tree. Another ingredient in our proof is the block-cut tree. Any connected graph can be decomposed into a tree of 2-edge-connected components, which is called the block-cut tree of the graph [33]. W… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: In this example, the graph contains one bridge component (shown in red), (8, 2, 1, 5), and two 2-edge-connected components (shown in black): (8, 9, 10) and (2, 3, 4, 6, 7). Definition 3.7 (junction vertex). We define junction vertices as vertices in the intersection be…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

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

  1. On the edge eigenvalues of sparse random geometric graphs

    math.PR 2025-09 conditional novelty 8.0 of 10

    For Gaussian-sampled random geometric graphs in the sparse regime, the first nontrivial edge eigenvalues of the scaled random-walk Laplacian converge in probability to 2(k-1)/sigma^2-type eigenvalues of a weighted Lap...

  2. Majority Dynamics on Resampled Sparse Erd\H{o}s--R\'enyi Graphs: Gaussian Winner Selection and Pace to Unanimity

    math.PR 2026-08 conditional novelty 7.0 of 10

    For majority dynamics on resampled sparse Erdős-Rényi graphs, the first update performs a Gaussian coin flip that decides the winner, and unanimity follows within (1+o(1)) log N / log log N rounds.

  3. Spectral Concentration and Recovery in Sparse High-Dimensional Random Geometric Graphs

    stat.ML 2026-07 accept novelty 7.0 of 10

    Sparse geometric graph adjacency spectra concentrate at the connectivity scale, yielding improved latent-vector recovery and the first connectivity-scale exact label recovery in the Gaussian mixture block model.

  4. Distinguishability threshold for random geometric graphs

    math.PR 2026-07 conditional novelty 6.0 of 10

    Random geometric graphs and Erdős–Rényi graphs are statistically indistinguishable when d ≫ n^3p^3(log 1/p)^3, for all p between n^{-1/5} polylog(n) and 1/3.

Reference graph

Works this paper leans on

63 extracted references · 53 canonical work pages · cited by 4 Pith papers

  1. [44]

    Local and global expansion in random geo- metric graphs

    Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang. Local and global expansion in random geo- metric graphs. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 817–825, 2023

    work page 2023

  2. [1]

    Guarantees for spontaneous synchronization on random geometric graphs.SIAM Journal on Applied Dynamical Systems, 23(1):779–790, 2024

    Pedro Abdalla, Afonso S Bandeira, and Clara Invernizzi. Guarantees for spontaneous synchronization on random geometric graphs.SIAM Journal on Applied Dynamical Systems, 23(1):779–790, 2024

    work page 2024

  3. [2]

    Expander graphs are globally synchronizing.arXiv preprint arXiv:2210.12788, 2022

    Pedro Abdalla, Afonso S Bandeira, Martin Kassabov, Victor Souza, Steven H Strogatz, and Alex Townsend. Expander graphs are globally synchronizing.arXiv preprint arXiv:2210.12788, 2022

    arXiv 2022

  4. [3]

    On the spectrum of dense random geometric graphs.The Annals of Applied Probability, 32(3):1734–1773, 2022

    Kartick Adhikari, Robert J Adler, Omer Bobrowski, and Ron Rosenthal. On the spectrum of dense random geometric graphs.The Annals of Applied Probability, 32(3):1734–1773, 2022

    work page 2022

  5. [4]

    Number 118

    Greg W Anderson, Alice Guionnet, and Ofer Zeitouni.An introduction to random matrices. Number 118. Cam- bridge university press, 2010

    work page 2010

  6. [5]

    Testing Thresholds and Spectral Properties of High-Dimensional Random Toroidal Graphs via Edgeworth-Style Expansions

    Samuel Baguley, Andreas G¨ obel, Marcus Pappik, and Leon Schiller. Testing thresholds and spectral properties of high-dimensional random toroidal graphs via edgeworth-style expansions.arXiv preprint arXiv:2502.18346, 2025

    work page Pith review arXiv 2025

  7. [6]

    Springer, 2010

    Zhidong Bai and Jack W Silverstein.Spectral analysis of large dimensional random matrices, volume 20. Springer, 2010

    2010

  8. [7]

    On the fourier coefficients of high-dimensional random geometric graphs

    Kiril Bangachev and Guy Bresler. On the fourier coefficients of high-dimensional random geometric graphs. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 549–560, 2024

    2024

Show all 63 references
  1. [8]

    Sandwiching random geometric graphs and erdos-renyi with applications: Sharp thresholds, robust testing, and enumeration

    Kiril Bangachev and Guy Bresler. Sandwiching random geometric graphs and erdos-renyi with applications: Sharp thresholds, robust testing, and enumeration. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 310–321, 2025

    2025

  2. [9]

    Spectral radii of sparse random matrices

    Florent Benaych-Georges, Charles Bordenave, and Antti Knowles. Spectral radii of sparse random matrices. In Annales de l’Institut Henri Poincar´ e-Probabilit´ es et Statistiques, volume 56, pages 2141–2161, 2020

    2020

  3. [10]

    Eigenvalues of euclidean random matrices.Random Structures & Algorithms, 33(4):515–532, 2008

    Charles Bordenave. Eigenvalues of euclidean random matrices.Random Structures & Algorithms, 33(4):515–532, 2008

    2008

  4. [11]

    Resolvent of large random graphs.Random Structures & Algorithms, 37(3):332–352, 2010

    Charles Bordenave and Marc Lelarge. Resolvent of large random graphs.Random Structures & Algorithms, 37(3):332–352, 2010

    2010

  5. [12]

    Threshold for detecting high dimensional geometry in anisotropic random geometric graphs.Random Structures & Algorithms, 64(1):125–137, 2024

    Matthew Brennan, Guy Bresler, and Brice Huang. Threshold for detecting high dimensional geometry in anisotropic random geometric graphs.Random Structures & Algorithms, 64(1):125–137, 2024

    2024

  6. [13]

    Testing for high-dimensional geometry in random graphs.Random Structures & Algorithms, 49(3):503–532, 2016

    S´ ebastien Bubeck, Jian Ding, Ronen Eldan, and Mikl´ os Z R´ acz. Testing for high-dimensional geometry in random graphs.Random Structures & Algorithms, 49(3):503–532, 2016

    2016

  7. [14]

    The spectrum of random inner-product kernel matrices.Random Matrices: Theory and Applications, 2(04):1350010, 2013

    Xiuyuan Cheng and Amit Singer. The spectrum of random inner-product kernel matrices.Random Matrices: Theory and Applications, 2(04):1350010, 2013

    2013

  8. [15]

    Scaling limit of the kuramoto model on random geometric graphs.SIAM Journal on Applied Mathematics, 85(4):1719–1748, 2025

    Francisco Cirelli, Pablo Groisman, Ruojun Huang, and Hern´ an Vivas. Scaling limit of the kuramoto model on random geometric graphs.SIAM Journal on Applied Mathematics, 85(4):1719–1748, 2025

    2025

  9. [16]

    Christensen

    Jesper Dall and M. Christensen. Random geometric graphs.Physical Review E, 66(1):016121, 2002. 22 YIF AN CAO AND YIZHE ZHU

    2002

  10. [17]

    The energy landscape of the kuramoto model in random geometric graphs in a circle.SIAM Journal on Applied Dynamical Systems, 24(1):1–15, 2025

    Cecilia De Vita, Juli´ an Fern´ andez Bonder, and Pablo Groisman. The energy landscape of the kuramoto model in random geometric graphs in a circle.SIAM Journal on Applied Dynamical Systems, 24(1):1–15, 2025

    2025

  11. [18]

    Phase synchronization in random geometric graphs on the 2d sphere.arXiv preprint arXiv:2504.01151, 2025

    Cecilia De Vita, Pablo Groisman, and Ruojun Huang. Phase synchronization in random geometric graphs on the 2d sphere.arXiv preprint arXiv:2504.01151, 2025

    2025

  12. [19]

    High-dimensional random geometric graphs and their clique number.Electronic Journal of Probability, 16:2481 – 2508, 2011

    Luc Devroye, Andr´ as Gy¨ orgy, G´ abor Lugosi, and Frederic Udina. High-dimensional random geometric graphs and their clique number.Electronic Journal of Probability, 16:2481 – 2508, 2011

    2011

  13. [20]

    The spectrum of random kernel matrices: universality results for rough and varying kernels

    Yen Do and Van Vu. The spectrum of random kernel matrices: universality results for rough and varying kernels. Random Matrices: Theory and Applications, 2(03):1350005, 2013

    2013

  14. [21]

    Synchronization in complex networks of phase oscillators: A survey.Auto- matica, 50(6):1539–1564, 2014

    Florian D¨ orfler and Francesco Bullo. Synchronization in complex networks of phase oscillators: A survey.Auto- matica, 50(6):1539–1564, 2014

    2014

  15. [22]

    Synchronization in complex oscillator networks and smart grids.Proceedings of the National Academy of Sciences, 110(6):2005–2010, 2013

    Florian D¨ orfler, Michael Chertkov, and Francesco Bullo. Synchronization in complex oscillator networks and smart grids.Proceedings of the National Academy of Sciences, 110(6):2005–2010, 2013

    2005

  16. [23]

    Universality for the global spectrum of random inner-product kernel matrices in the polynomial regime.arXiv preprint arXiv:2310.18280, 2023

    Sofiia Dubova, Yue M Lu, Benjamin McKenna, and Horng-Tzer Yau. Universality for the global spectrum of random inner-product kernel matrices in the polynomial regime.arXiv preprint arXiv:2310.18280, 2023

    2023 arXiv

  17. [24]

    The spectrum of kernel random matrices.Annals of statistics, 38(1):1–50, 2010

    Noureddine El Karoui. The spectrum of kernel random matrices.Annals of statistics, 38(1):1–50, 2010

    2010

  18. [25]

    Spectra of large diluted but bushy random graphs.Random Structures & Algorithms, 49(1):160–184, 2016

    Nathana¨ el Enriquez and Laurent M´ enard. Spectra of large diluted but bushy random graphs.Random Structures & Algorithms, 49(1):160–184, 2016

    2016

  19. [26]

    Spectra of the conjugate kernel and neural tangent kernel for linear-width neural networks.Advances in neural information processing systems, 33:7710–7721, 2020

    Zhou Fan and Zhichao Wang. Spectra of the conjugate kernel and neural tangent kernel for linear-width neural networks.Advances in neural information processing systems, 33:7710–7721, 2020

    2020

  20. [27]

    Spectral techniques applied to sparse random graphs.Random Structures & Algo- rithms, 27(2):251–275, 2005

    Uriel Feige and Eran Ofek. Spectral techniques applied to sparse random graphs.Random Structures & Algo- rithms, 27(2):251–275, 2005

    2005

  21. [28]

    American Mathematical Soc., 2008

    Joel Friedman.A proof of Alon ’s second eigenvalue conjecture and related problems. American Mathematical Soc., 2008

    2008

  22. [29]

    Global law of conjugate kernel random matrices with heavy-tailed weights

    Alice Guionnet and Vanessa Piccolo. Global law of conjugate kernel random matrices with heavy-tailed weights. arXiv preprint arXiv:2502.18428, 2025

    2025

  23. [30]

    On the normalized laplacian spectra of random geometric graphs.Journal of Theoretical Probability, 36(1):46–77, 2023

    Mounia Hamidouche, Laura Cottatellucci, and Konstantin Avrachenkov. On the normalized laplacian spectra of random geometric graphs.Journal of Theoretical Probability, 36(1):46–77, 2023

    2023

  24. [31]

    Fitting a geometric graph to a protein–protein inter- action network.Bioinformatics, 24(8):1093–1099, 2008

    Desmond J Higham, Marija Raˇ sajski, and Nataˇ sa Prˇ zulj. Fitting a geometric graph to a protein–protein inter- action network.Bioinformatics, 24(8):1093–1099, 2008

    2008

  25. [32]

    Latent space approaches to social network analysis

    Peter D Hoff, Adrian E Raftery, and Mark S Handcock. Latent space approaches to social network analysis. Journal of the american Statistical association, 97(460):1090–1098, 2002

    2002

  26. [33]

    Algorithm 447: efficient algorithms for graph manipulation.Communications of the ACM, 16(6):372–378, 1973

    John Hopcroft and Robert Tarjan. Algorithm 447: efficient algorithms for graph manipulation.Communications of the ACM, 16(6):372–378, 1973

    1973

  27. [34]

    The random graph process is globally synchronizing

    Vishesh Jain, Clayton Mizgerd, and Mehtaab Sawhney. The random graph process is globally synchronizing. arXiv preprint arXiv:2501.12205, 2025

    2025 arXiv

  28. [35]

    On spectral radii of unraveled balls.Journal of Combinatorial Theory, Series B, 136:72–80, 2019

    Zilin Jiang. On spectral radii of unraveled balls.Journal of Combinatorial Theory, Series B, 136:72–80, 2019

    2019

  29. [36]

    Delocalization and limiting spectral distribution of erd˝ os-r´ enyi graphs with constant expected degree.Electronic Communications in Probability, 2018

    Paul Jung and Jaehun Lee. Delocalization and limiting spectral distribution of erd˝ os-r´ enyi graphs with constant expected degree.Electronic Communications in Probability, 2018

    2018

  30. [37]

    Sufficiently dense kuramoto networks are globally synchronizing.Chaos: An Interdisciplinary Journal of Nonlinear Science, 31(7), 2021

    Martin Kassabov, Steven H Strogatz, and Alex Townsend. Sufficiently dense kuramoto networks are globally synchronizing.Chaos: An Interdisciplinary Journal of Nonlinear Science, 31(7), 2021

    2021

  31. [38]

    A global synchronization theorem for oscillators on a random graph.Chaos: An Interdisciplinary Journal of Nonlinear Science, 32(9), 2022

    Martin Kassabov, Steven H Strogatz, and Alex Townsend. A global synchronization theorem for oscillators on a random graph.Chaos: An Interdisciplinary Journal of Nonlinear Science, 32(9), 2022

    2022

  32. [39]

    Self-entrainment of a population of coupled non-linear oscillators

    Yoshiki Kuramoto. Self-entrainment of a population of coupled non-linear oscillators. InInternational symposium on mathematical problems in theoretical physics: January 23–29, 1975, kyoto university, kyoto/Japan, pages 420–

    1975

  33. [40]

    Concentration and regularization of random graphs.Random Structures & Algorithms, 51(3):538–561, 2017

    Can M Le, Elizaveta Levina, and Roman Vershynin. Concentration and regularization of random graphs.Random Structures & Algorithms, 51(3):538–561, 2017

    2017

  34. [41]

    Spectral clustering in the gaussian mixture block model.arXiv preprint arXiv:2305.00979, 2023

    Shuangping Li and Tselil Schramm. Spectral clustering in the gaussian mixture block model.arXiv preprint arXiv:2305.00979, 2023

    2023 arXiv

  35. [42]

    On the landscape of synchronization networks: A perspective from nonconvex optimization.SIAM Journal on Optimization, 29(3):1879–1907, 2019

    Shuyang Ling, Ruitu Xu, and Afonso S Bandeira. On the landscape of synchronization networks: A perspective from nonconvex optimization.SIAM Journal on Optimization, 29(3):1879–1907, 2019

    1907

  36. [43]

    Testing thresholds for high-dimensional sparse random geometric graphs

    Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang. Testing thresholds for high-dimensional sparse random geometric graphs. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 672–677, 2022

    2022

  37. [45]

    A probabilistic view of latent space graphs and phase transitions.Bernoulli, 29(3):2417–2441, 2023

    Suqi Liu and Mikl´ os Z R´ acz. A probabilistic view of latent space graphs and phase transitions.Bernoulli, 29(3):2417–2441, 2023. SPECTRA OF HIGH-DIMENSIONAL SPARSE RANDOM GEOMETRIC GRAPHS 23

    2023

  38. [46]

    A random matrix approach to neural networks.The Annals of Applied Probability, 28(2):1190–1248, 2018

    Cosme Louart, Zhenyu Liao, and Romain Couillet. A random matrix approach to neural networks.The Annals of Applied Probability, 28(2):1190–1248, 2018

    2018

  39. [47]

    An equivalence principle for the spectrum of random inner-product kernel matrices with polynomial scalings.The Annals of Applied Probability, 35(4):2411–2470, 2025

    Yue M Lu and Horng-Tzer Yau. An equivalence principle for the spectrum of random inner-product kernel matrices with polynomial scalings.The Annals of Applied Probability, 35(4):2411–2470, 2025

    2025

  40. [48]

    Impossibility of latent inner product recovery via rate distortion

    Cheng Mao and Shenduo Zhang. Impossibility of latent inner product recovery via rate distortion. In2024 60th Annual Allerton Conference on Communication, Control, and Computing, pages 01–08. IEEE, 2024

    2024

  41. [49]

    Connectivity of large wireless networks under a general connection model.IEEE transactions on information theory, 59(3):1761–1772, 2012

    Guoqiang Mao and Brian DO Anderson. Connectivity of large wireless networks under a general connection model.IEEE transactions on information theory, 59(3):1761–1772, 2012

    2012

  42. [50]

    Parallel ear decomposition search (eds) and st-numbering in graphs.Theoretical Computer Science, 47:277–298, 1986

    Yael Maon, Baruch Schieber, and Uzi Vishkin. Parallel ear decomposition search (eds) and st-numbering in graphs.Theoretical Computer Science, 47:277–298, 1986

    1986

  43. [51]

    Generalization error of random feature and kernel methods: hypercontractivity and kernel matrix concentration.Applied and Computational Harmonic Analysis, 59:3–84, 2022

    Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Generalization error of random feature and kernel methods: hypercontractivity and kernel matrix concentration.Applied and Computational Harmonic Analysis, 59:3–84, 2022

    2022

  44. [52]

    Universality of kernel random matrices and kernel regression in the quadratic regime.arXiv preprint arXiv:2408.01062, 2024

    Parthe Pandit, Zhichao Wang, and Yizhe Zhu. Universality of kernel random matrices and kernel regression in the quadratic regime.arXiv preprint arXiv:2408.01062, 2024

    2024

  45. [53]

    Nonlinear random matrix theory for deep learning.Advances in neural information processing systems, 30, 2017

    Jeffrey Pennington and Pratik Worah. Nonlinear random matrix theory for deep learning.Advances in neural information processing systems, 30, 2017

    2017

  46. [54]

    Oxford University Press, 2003

    Mathew Penrose.Random Geometric Graphs. Oxford University Press, 2003

    2003

  47. [55]

    Basic models and questions in statistical network analysis.Statistics Surveys, 11:1–47, 2017

    Mikl´ os Z R´ acz and S´ ebastien Bubeck. Basic models and questions in statistical network analysis.Statistics Surveys, 11:1–47, 2017

    2017

  48. [56]

    A theorem on graphs, with an application to a problem of traffic control.The American Mathematical Monthly, 46(5):281–283, 1939

    Herbert Ellis Robbins. A theorem on graphs, with an application to a problem of traffic control.The American Mathematical Monthly, 46(5):281–283, 1939

    1939

  49. [57]

    The kuramoto model in complex networks.Physics Reports, 610:1–98, 2016

    Francisco A Rodrigues, Thomas K DM Peron, Peng Ji, and J¨ urgen Kurths. The kuramoto model in complex networks.Physics Reports, 610:1–98, 2016

    2016

  50. [58]

    Enumerative combinatorics volume 1 second edition.Cambridge studies in advanced mathe- matics, 2011

    Richard P Stanley. Enumerative combinatorics volume 1 second edition.Cambridge studies in advanced mathe- matics, 2011

    2011

  51. [59]

    There is no non-zero stable fixed point for dense networks in the homogeneous kuramoto model

    Richard Taylor. There is no non-zero stable fixed point for dense networks in the homogeneous kuramoto model. Journal of Physics A: Mathematical and Theoretical, 45(5):055102, 2012

    2012

  52. [60]

    Sparse random graphs: Eigenvalues and eigenvectors.Random Structures & Algorithms, 42(1):110–134, 2013

    Linh V Tran, Van H Vu, and Ke Wang. Sparse random graphs: Eigenvalues and eigenvectors.Random Structures & Algorithms, 42(1):110–134, 2013

    2013

  53. [61]

    Spectral norm of random matrices.Combinatorica, 27(6):721–736, 2007

    Van H Vu. Spectral norm of random matrices.Combinatorica, 27(6):721–736, 2007

    2007

  54. [62]

    Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks.The Annals of Applied Probability, 34(2):1896–1947, 2024

    Zhichao Wang and Yizhe Zhu. Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks.The Annals of Applied Probability, 34(2):1896–1947, 2024

    1947

  55. [63]

    A graphon approach to limiting spectral distributions of wigner-type matrices.Random Structures & Algorithms, 56(1):251–279, 2020

    Yizhe Zhu. A graphon approach to limiting spectral distributions of wigner-type matrices.Random Structures & Algorithms, 56(1):251–279, 2020. AppendixA.Additional proofs and auxiliary lemmas A.1.Proof of Lemma 3.4. Proof of Lemma 3.4.The if and only if statement is due to [56]...

    2020

Pith tools

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