Pith. sign in

REVIEW 3 major objections 5 minor 4 cited by

Eigenvalue gaps of the Laplacian of random graphs

T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read The eigenvalue gaps of a random graph Laplacian are controlled by a quantitative bound: for any fixed edge probability p and any polynomial-scale threshold δ, the chance that two consecutive eigenvalues are closer than δ n^{-1/2} is at…

desk verdict Strong, novel result with two proof gaps that need fixing before the theorem is fully supported. read the letter →

arxiv 2501.00234 v2 pith:UYYY63T5 submitted 2024-12-31 math.PR math.CO

Nicholas Christoffersen , Kyle Luh , Hoi H. Nguyen , Jingheng Wang This is my paper · ORCID
classification math.PRmath.CO MSC 60B2060C0505C8015B52
keywords eigenvaluegapsgraphLaplacianErdős-Rényirandomgraphssimplespectrumdelocalizationleastcommondenominatorovercrowdingmatrices
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

Random Erdős–Rényi graphs have Laplacians whose eigenvalues are all distinct with probability tending to one, and the paper proves a quantitative version of this: for any fixed edge probability p and any polynomial-scale threshold δ, the chance that any two consecutive eigenvalues are closer than δ $n^{{-1/2}}$ is at most O($n^{{o(1)}}$δ). A union bound over the n gaps gives that the minimum eigenvalue gap is at least $n^{{-3/2-o(1)}}$ with probability 1-o(1). This matters because algorithms for quantum walks on graphs, spectral clustering, and graph neural networks assume or benefit from simple spectra and non-degenerate gaps, and the result supplies a theoretical guarantee for those assumptions. The proof works for both the combinatorial Laplacian and its centered version, and along the way establishes new delocalization and small-ball estimates for Laplacian eigenvectors that are of independent interest.

What carries the argument

The mechanism that carries the argument is a spectrum-preserving reshuffling of the last two columns of the Laplacian: replacing (c_{n-1}, c_n) by (c_{n-1}+c_n)/√2 and (c_{n-1}-c_n)/√2 preserves the spectrum while creating fresh independent randomness on the set of vertices adjacent to exactly one of the two last vertices. This converts the small-gap event into a small-ball estimate |v·c_n| ≤ $n^{{o(1)}}$δ for an eigenvector v of the (n-1)-by-(n-1) minor. To make that estimate uniform in v, the paper proves affine no-gaps delocalization (no segment v_I of linear size is well approximated by a constant vector after any shift), no-structure delocalization (segments v_I have large least common denominator, the smallest scaling at which a normalized vector lands near the integer lattice), and an overcrowding bound showing that rectangular minors of the Laplacian are nearly isometric. These ingredients let the proof run the classical interlacing and eigenvector-gap argument despite the Laplacian's dependent diagonal entries.

What would settle it

Compute the probability that the eigenvector of the smallest nonzero eigenvalue of the Laplacian of G(n,1/2) has last coordinate below $n^{{-1/2-o(1)}}$. If that probability is not o(1), the proof's assumption that |b| ≥ $n^{{-1/2-o(1)}}$ fails and the small-b case would require a new argument; if it is o(1), the gap is harmless and the theorem still stands. A direct simulation of |b| for moderate n, or a conditional calculation given the no-gaps and no-structure events, would settle which holds.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.2: for fixed 0<p<1 and any fixed constant A, for any δ ≥ $n^{{-A}}$, the probability that the random graph Laplacian L_n of G(n,p) has a pair of consecutive eigenvalues within δ $n^{{-1/2}}$ is O($n^{{o(1)}}$δ). Consequently the spectrum is simple with probability 1-o(1), and the minimum gap is at least $n^{{-3/2-o(1)}}$ with probability 1-o(1). An equivalent statement, Theorem 2.1, holds for the centered Laplacian L_n = L_n - EL_n, whose dependent diagonal entries are handled directly; the proof is carried out for the centered model and then transferred to L_n by a Weyl-type argument that isolates the zero eigenvalue. The paper also proves affine no-gaps delocalization and no-structure delocalization for Laplacian eigenvectors, an overcrowding estimate for the spectrum of rectangular minors, and a bound showing that eigenvectors cannot have more than one coordinate of size below $n^{{-B}}$.

Load-bearing premise

The load-bearing premise is that the chosen eigenvector's last coordinate has size at least $n^{{-1/2-o(1)}}$; the cited no-gaps results only guarantee that all but a constant fraction of the coordinates are that large, and the proof does not separately handle the possibility that the last coordinate is small.

Editorial extensions

If this is right

  • For every fixed p, the Laplacian of G(n,p) has simple spectrum with probability 1-o(1), so graph algorithms that assume distinct Laplacian eigenvalues are justified on random inputs.
  • The minimum eigenvalue gap is at least n^{-3/2-o(1)} with probability 1-o(1), giving a concrete stability window for spectral graph partitioning and graph neural network positional encodings.
  • The same conclusion holds for the centered Laplacian L_n - EL_n, the model whose bulk spectral statistics match the free convolution of a semicircle and a Gaussian.
  • Laplacian eigenvectors are affine-delocalized: every segment of linear size carries mass at least (log n)^{-O(1)} after any shift, and segments have large least common denominator, so they are far from arithmetic structure.
  • With high probability an eigenvector cannot have more than one coordinate of size below n^{-B}; in particular, soft nodes — vanishing or near-vanishing eigenvector entries — are essentially forbidden in random graphs.

Reading between the lines

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

  • The reshuffling trick acts as a general recipe for dependent-entry matrices: an orthogonal rotation that creates fresh randomness in a low-dimensional block may replace the independence assumption that fails for Laplacians, so a similar strategy could apply to stochastic block model Laplacians or random weighted graphs.
  • The bound O(n^{o(1)}δ) is a first-order repulsion estimate; if the method can be sharpened to O(δ^2), it would match the quadratic level repulsion of the GOE that bulk eigenvalue statistics already suggest for this model.
  • The 'at most one small coordinate' theorem suggests a concrete testable extension for spectral graph theory: counting nodal domains of random graphs should almost surely show no zero components, so nodal domain counts should equal those predicted for generic eigenfunctions.
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.

Referee Report

3 major / 5 minor

Summary. The paper studies eigenvalue gaps of the Laplacian of an Erdős–Rényi graph G(n,p). The main theorem (Theorem 1.2) asserts that for fixed 0<p<1 and any A, for δ ≥ n^{-A}, the maximum over i of P(|λ_{i+1}(L_n)−λ_i(L_n)| ≤ δ n^{-1/2}) is O(n^{o(1)}δ), so the spectrum is simple with probability 1−o(1) and the minimum gap is at least n^{-3/2−o(1)}. The proof works with the centered Laplacian L_n, establishes affine no-gaps delocalization (Theorem 2.3), no-structure delocalization via the least common denominator (Theorem 2.4), an overcrowding estimate (Theorem 2.6), and a small-coordinate bound (Theorem 2.7). A switching/reshuffling argument decouples the last two columns, reducing the gap event to a small-ball probability for a structured vector. The uncentered case follows by a Weyl comparison with L_n.

Significance. If correct, this is a substantial contribution: it appears to be the first proof of simplicity of the spectrum and quantitative gap bounds for the graph Laplacian, a model with dependent entries and a different bulk distribution than Wigner matrices. The auxiliary delocalization results, particularly the affine no-gaps estimate and the no-structure (LCD) delocalization for eigenvectors, are new and likely to be useful beyond this paper. The proof is constructive and quantitative, and it builds on earlier published tools (Cauchy interlacing, Talagrand concentration, LCD small-ball estimates, restricted invertibility) rather than fitting parameters to the target conclusion.

major comments (3)
  1. [Section 7, proof of Theorem 2.1] The sentence 'By Theorem 2.3 and Claim 3.4, we assume that |b| ≥ n^{-1/2-o(1)}' is not justified. Claim 3.4 states only that at most ⌊c0 n⌋−1 coordinates can lie below (c1/c0)^{1/2}/√n; it gives no information about a fixed coordinate, and the last coordinate of an eigenvector of L'_n may be zero (e.g., the null vector Q^T 1 has last coordinate 0). The derivation of |v^T c_n| ≤ n^{o(1)}δ from |b| |v^T c_n| ≤ δ n^{-1/2} divides by |b|, so the small-b case is not covered. No alternative argument is supplied. This is load-bearing: without a bound on |v^T c_n| when |b| is small, the reduction of the gap event to the small-ball probability over the switched column c_n fails, so the proofs of Theorem 2.1 and hence Theorem 1.2 are incomplete as written.
  2. [Section 4, proof of Theorem 2.6] The parameter choice τ = K log n / k is not valid over the stated range k ≥ C log n. Since τ is used to form column blocks of size 2τ, it must be a positive integer; for k ≫ log n (for instance k = n^{1−δ0} in Section 5, or k = Θ(n/log^C n) as highlighted after Theorem 2.6), τ = o(1) and 2τ is not an integer, while the binomial variable B(2τ,p) is no longer meaningful. Even ignoring integrality, the Chernoff bound P(|X−2τp| ≥ δ2τp) ≤ 2 exp(−2δ^2τp/3) with δ=1/2 gives a failure probability close to 1 when τ→0, so the claim P(|X−2τp| < δ2τp) ≥ 1−k/(5n) is false in this regime. Consequently, the proof of the overcrowding estimate does not cover the values of k that are used in the no-gaps and no-structure delocalization arguments (Sections 5 and 6).
  3. [Section 2.2, Theorem 2.4 statement] The inequality in the event is reversed. The proof in Section 6 bounds the probability of the existence of v and I with LCD_{κ,γ}(v_I) ∈ [D0, 2D0) for D0 ≍ n^A, i.e., the structured (small-LCD) event; it does not bound the probability of LCD ≥ n^A. As stated, the theorem asserts the opposite of what is proved. The proof of Theorem 2.1 in Section 7 uses the correct version ('LCD ≥ n^{2A} with probability 1−n^{−ω(1)}'), so the statement must be corrected to LCD_{κ,γ}(v_I) ≤ n^A.
minor comments (5)
  1. [Section 2.1] The informal 'but let's ignore this minor problem for now' regarding the √2 normalization should be replaced by a precise statement, since the normalization affects the distribution of the switched entries and the small-ball application.
  2. [Section 4, Lemma 4.1 proof] In Case 2, the threshold 't Pn i=1 Ex2 i pii' appears dimensionally inconsistent; it should presumably be t√(∑ Ex_i^2 p_ii) or tT√k.
  3. [Abstract] The phrase 'the presence of small entries in the eigenvectors' is the opposite of the content of Theorem 2.7, which bounds the number of small entries; rephrase as 'bounds on the number of small entries'.
  4. [Section 7, proof of Theorem 2.1] After deriving |v·c_n| ≤ n^{o(1)}δ, the application of Theorem 3.7 requires the subvector v_{I_{n-2}} to have non-negligible norm; this follows from Theorem 2.3 but should be stated explicitly.
  5. [Section 2.5, remark after Theorem 2.4] The bound '1√log logn ≤ λn' should be typeset as 1/√log log n ≤ λ_n to avoid confusion with the earlier bound in Theorem 2.3.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the Laplacian gap theorem is derived from internally proved delocalization/overcrowding statements and independent small-ball results; the Section 7 small-|b| step is a genuine proof gap but not a circular reduction.

full rationale

I walked the derivation chain of Theorem 1.2 / Theorem 2.1. The gap event is reduced, via Cauchy interlacing and the last-column decomposition, to a small-ball probability over a randomly switched column: if |b| is large, |v·c_n(L'_n)| ≤ n^{o(1)}δ, and then Theorem 3.7 (an external small-ball result from Rudelson–Vershynin) is applied to the independently rerandomized coordinates over I_{n-2}. The supporting delocalization statements (affine no-gaps, no-structure, overcrowding, small coordinates) are proved in Sections 4–6 rather than assumed. The target gap bound never appears as an input; no parameter is fitted to data; no uniqueness theorem is imported to forbid alternatives. The cited results from [55], [52], and [53] overlap with the author list, but they are external statements whose hypotheses do not include the present theorem (e.g., the Nguyen–Wood anti-concentration Theorem 5.1 and the Nguyen–Tao–Vu net lemmas, the latter also available in [59]); these are independent support, not self-referential inputs. I also flag a non-circular correctness risk in the proof of Theorem 2.1 (Section 7): the sentence 'By Theorem 2.3 and Claim 3.4, we assume that |b| ≥ n^{-1/2-o(1)} (as these results imply that with probability 1−n^{-ω(1)} the set of indices where |b| ≥ n^{-1/2-o(1)} is of size Θ(n))' is an invalid inference, since Claim 3.4 only guarantees that all but Θ(n) coordinates are large, not that the fixed last coordinate b is large; the case of small b is not treated separately, so the bound |v·c_n| ≤ n^{o(1)}δ is not justified in that case. This is a proof gap / missing case, not a circularity: nothing in the paper defines the target gap in terms of the small-b assumption or fits the assumption to the conclusion. Lemma 7.2 also says its proof is 'identical' and is omitted, which is an omission rather than a circular step. Overall, the central derivation is self-contained against external benchmarks and the score is 0.

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

The core claim does not rest on fitted constants or invented objects; it depends on standard probability and linear algebra machinery and a symmetry argument for the switching process.

assumptions (3)
  • domain assumption Fixed edge probability p in G(n,p)
    The theorem and all constants depend on p; the sparse case p tending to 0 is explicitly left open.
  • standard math Standard random matrix input theorems are assumed
    Cauchy interlacing, Weyl inequalities, Talagrand concentration, and LCD small-ball bounds are used throughout, citing prior work [51], [58], [59].
  • domain assumption The neighbor reshuffling operation preserves the law of the random Laplacian
    Central to the fresh randomness Step 2; asserted in Section 2.1 and used in Sections 5 and 7.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Eigenvalue gaps of the Laplacian of random graphs." pith.science (2026). https://pith.science/paper/UYYY63T5

@misc{pith2026250100234,
  author       = {Pith},
  title        = {Pith review of: Eigenvalue gaps of the Laplacian of random graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UYYY63T5}},
  note         = {Machine review of arXiv:2501.00234}
}
read the original abstract

We show that, with very high probability, the random graph Laplacian has simple spectrum. Our method provides a quantitatively effective estimate of the spectral gaps. Along the way, we establish results on affine no-gaps delocalization, no-structure delocalization, overcrowding and small entries of the eigenvectors for the Laplacian model. These findings are of independent interest.

Figures

Figures reproduced from arXiv: 2501.00234 by the authors.

Figure 1
Figure 1. Reshuffling neighbors. in the literature, except in the no-gaps delocalization aspect. (Although in the finite field setting, this local aspect has been studied in [54] for null vectors.) 2.2. No-Gaps and No-Structure Delocalization. Step 1 of our modified plan has two substeps. • Substep 1(i). We first show that with high probability, ∥vI ∥2 is not too small for all I of size Θ(n) (Theorem 2.3). • Substep 1(ii). We… view at source ↗
Figure 2
Figure 2. |Is| > |Im| ([ Is ][ F ) Im ] [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 4
Figure 4. |Is| > |Im| ([ Is ][ F ) I ′ m ⊂ Im ( J∗ ) ] [PITH_FULL_IMAGE:figures/full_fig_p020_4.png] view at source ↗
Figures from the paper (2 more)
Figure 6
Figure 6. Figure 6: Finding non-structured subvectors. Proof. Assume D(vI ) = D is achieved at vI1 with the corresponding shift a1 ∈ A. Then by Fact 3.6, as 1 ≤ ∥vI ∥2/∥vI1 ∥2 ≤ c −1 n , LCDκ,γ(vI ) ≥ c −1 n LCDκ,γ′ (v1) ≥ c −1 n LCDκ,γ′ (v1 − a1). □ As a consequence of the above claim, a…
Figure 7
Figure 7. Figure 7: Decomposition into i.i.d. parts. Then, from the equation ∥M21vI + M22vI c ∥2 ≤ ε coming from (41), we apply M′ 22, which yields ∥M′ 22M21vI + M′ 22M22|Tc vI c |Tc + vI c |T ∥2 ≤ ε∥M′ 22∥2 ≤ ε/dn √ n. In other words, if we fix a realization of M21 (and hence M12) and M2…

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. Dynamical phase retrieval for Schr{\"o}dinger evolution on finite graphs

    math.CA 2026-07 accept novelty 7.0 of 10

    Under B₂ spectrum, invertible squared-eigenvector matrix, and pairwise eigenvector support overlap, graph Schrödinger evolution does phase retrieval for every initial state, and this holds for almost every real diagon...

  2. Geometry of Reason: Spectral Signatures of Valid Mathematical Reasoning

    cs.LG 2026-01 reject novelty 6.0 of 10

    Spectral features of attention are claimed to classify proof validity with near-perfect effect sizes, but the main evaluation relabels proofs using the classifier's own outputs.

  3. Mass-Scale Analysis of In-the-Wild Conversations Reveals Complexity Bounds on LLM Jailbreaking

    cs.CL 2025-07 conditional novelty 6.0 of 10

    Across 2M+ in-the-wild LLM conversations, jailbreak attempts show no higher complexity than normal chats, and assistant toxicity has declined over time, suggesting bounded attack sophistication.

  4. Repeated singular values of a random symmetric matrix and decoupled singular value estimates

    math.PR 2025-04 conditional novelty 6.0 of 10

    For a random symmetric matrix with Bernoulli or subgaussian entries, the paper proves a product-form joint lower-tail estimate for the least singular value at two separated bulk locations, and shows the bulk singular ...

Reference graph

Works this paper leans on

74 extracted references · 67 canonical work pages · cited by 4 Pith papers

  1. [1]

    RalphAbboud, IsmailIlkanCeylan, MartinGrohe, andThomasLukasiewicz.Thesurprisingpowerofgraphneuralnetworks with random node initialization.arXiv preprint arXiv:2010.01179, 2020

    arXiv 2010

  2. [2]

    Quantum walks on graphs

    Dorit Aharonov, Andris Ambainis, Julia Kempe, and Umesh Vazirani. Quantum walks on graphs. InProceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pages 50–59. ACM, New York, 2001

    work page 2001

  3. [3]

    Anderson, Alice Guionnet, and Ofer Zeitouni.An introduction to random matrices, volume 118 ofCambridge Studies in Advanced Mathematics

    Greg W. Anderson, Alice Guionnet, and Ofer Zeitouni.An introduction to random matrices, volume 118 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2010

    work page 2010

  4. [4]

    Measuring the stability of spectral clustering

    Eleonora Andreotti, Dominik Edelmann, Nicola Guglielmi, and Christian Lubich. Measuring the stability of spectral clustering. Linear Algebra Appl., 610:673–697, 2021

    work page 2021

  5. [5]

    Silverstein.Spectral analysis of large dimensional random matrices

    Zhidong Bai and Jack W. Silverstein.Spectral analysis of large dimensional random matrices. Springer Series in Statistics. Springer, New York, second edition, 2010

    work page 2010

  6. [6]

    Bandeira

    Afonso S. Bandeira. Random Laplacian matrices and convex relaxations.Found. Comput. Math., 18(2):345–379, 2018. 10As in the previous section, herecn−1, cn are not exactly the last two columns ofLn. 27

    work page 2018

  7. [7]

    Cambridge University Press, 2004

    Lowell W Beineke and Robin J Wilson.Topics in algebraic graph theory, volume 102. Cambridge University Press, 2004

    work page 2004

  8. [8]

    Extreme gaps between eigenvalues of random matrices.Ann

    Gérard Ben Arous and Paul Bourgade. Extreme gaps between eigenvalues of random matrices.Ann. Probab., 41(4):2648– 2681, 2013

    work page 2013

Show all 74 references
  1. [9]

    Simplicity of eigenvalues and non-vanishing of eigenfunctions of a quantum graph.J

    Gregory Berkolaiko and Wen Liu. Simplicity of eigenvalues and non-vanishing of eigenfunctions of a quantum graph.J. Math. Anal. Appl., 445(1):803–818, 2017

    2017

  2. [10]

    Türker Bıyı koğlu, Wim Hordijk, Josef Leydold, Tomaˇ z Pisanski, and Peter F. Stadler. Graph Laplacians, nodal domains, and hyperplane arrangements.Linear Algebra Appl., 390:155–174, 2004

    2004

  3. [11]

    Extreme gaps between eigenvalues of Wigner matrices.J

    Paul Bourgade. Extreme gaps between eigenvalues of Wigner matrices.J. Eur. Math. Soc. (JEMS), 24(8):2823–2873, 2022

    2022

  4. [12]

    Extreme eigenvalues of laplacian random matrices with gaussian entries.arXiv preprint arXiv:2211.17175, 2022

    Andrew Campbell, Kyle Luh, Sean O’Rourke, Santiago Arenas-Velilla, and Victor Pérez-Abreu. Extreme eigenvalues of laplacian random matrices with gaussian entries.arXiv preprint arXiv:2211.17175, 2022

    2022 arXiv

  5. [13]

    The least singular value of a random symmetric matrix.Forum Math

    Marcelo Campos, Matthew Jenssen, Marcus Michelen, and Julian Sahasrabudhe. The least singular value of a random symmetric matrix.Forum Math. Pi, 12:Paper No. e3, 69, 2024

    2024

  6. [14]

    Caputo, I

    J.-G. Caputo, I. Khames, and A. Knippel. On graph Laplacian eigenvectors with components in{−1, 0, 1}. Discrete Appl. Math., 269:120–129, 2019

    2019

  7. [15]

    Eigenvectors of graph laplacians: a landscape.arXiv preprint arXiv:2301.08369, 2023

    J-G Caputo and Arnaud Knippel. Eigenvectors of graph laplacians: a landscape.arXiv preprint arXiv:2301.08369, 2023

    2023 arXiv

  8. [16]

    Oscillations of networks: the role of soft nodes.Journal of Physics A: Mathematical and Theoretical, 46(3):035101, 2012

    Jean-Guy Caputo, Arnaud Knippel, and Elie Simo. Oscillations of networks: the role of soft nodes.Journal of Physics A: Mathematical and Theoretical, 46(3):035101, 2012

    2012

  9. [17]

    Analog quantum algorithms for the mixing of Markov chains

    Shantanav Chakraborty, Kyle Luh, and Jérémie Roland. Analog quantum algorithms for the mixing of Markov chains. Phys. Rev. A, 102(2):022423, 20, 2020

    2020

  10. [18]

    How fast do quantum walks mix?Phys

    Shantanav Chakraborty, Kyle Luh, and Jérémie Roland. How fast do quantum walks mix?Phys. Rev. Lett., 124(5):050501, 7, 2020

    2020

  11. [19]

    Academic Press, Inc., Orlando, FL, 1984

    Isaac Chavel.Eigenvalues in Riemannian geometry, volume 115 ofPure and Applied Mathematics. Academic Press, Inc., Orlando, FL, 1984. Including a chapter by Burton Randol, With an appendix by Jozef Dodziuk

    1984

  12. [20]

    Estimates of the gaps between consecutive eigenvalues of Laplacian

    Daguang Chen, Tao Zheng, and Hongcang Yang. Estimates of the gaps between consecutive eigenvalues of Laplacian. Pacific J. Math., 282(2):293–311, 2016

    2016

  13. [21]

    Exponential algorithmic speedup by a quantum walk

    Andrew M Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A Spielman. Exponential algorithmic speedup by a quantum walk. InProceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 59–68, 2003

    2003

  14. [22]

    PhD thesis, Massachusetts Institute of Technology, 2004

    Andrew MacGregor Childs.Quantum information processing in continuous time. PhD thesis, Massachusetts Institute of Technology, 2004

    2004

  15. [23]

    On the Laplacian eigenvalues ofGn,p

    Amin Coja-Oghlan. On the Laplacian eigenvalues ofGn,p. Combin. Probab. Comput., 16(6):923–946, 2007

    2007

  16. [24]

    Nicholas A. Cook. On the singularity of adjacency matrices for random regular digraphs.Probab. Theory Related Fields, 167(1-2):143–200, 2017

    2017

  17. [25]

    Lee, and Nathan Linial

    Yael Dekel, James R. Lee, and Nathan Linial. Eigenvectors of random graphs: nodal domains.Random Structures Algo- rithms, 39(1):39–58, 2011

    2011

  18. [26]

    Applied numerical linear algebra.SocietyforIndustrialandAppliedMathematics(SIAM),Philadelphia, PA, 1997

    JamesW.Demmel. Applied numerical linear algebra.SocietyforIndustrialandAppliedMathematics(SIAM),Philadelphia, PA, 1997

    1997

  19. [27]

    Spectral distributions of adjacency and Laplacian matrices of random graphs.Ann

    Xue Ding and Tiefeng Jiang. Spectral distributions of adjacency and Laplacian matrices of random graphs.Ann. Appl. Probab., 20(6):2086–2117, 2010

    2010

  20. [28]

    Spectral statistics of erdős-Rényi Graphs II: Eigenvalue spacing and the extreme eigenvalues.Comm

    László Erdős, Antti Knowles, Horng-Tzer Yau, and Jun Yin. Spectral statistics of erdős-Rényi Graphs II: Eigenvalue spacing and the extreme eigenvalues.Comm. Math. Phys., 314(3):587–640, 2012

    2012

  21. [29]

    Bulk universality for generalized Wigner matrices.Probab

    László Erdős, Horng-Tzer Yau, and Jun Yin. Bulk universality for generalized Wigner matrices.Probab. Theory Related Fields, 154(1-2):341–407, 2012

    2012

  22. [30]

    Small gaps of GOE.Geom

    Renjie Feng, Gang Tian, and Dongyi Wei. Small gaps of GOE.Geom. Funct. Anal., 29(6):1794–1827, 2019

    2019

  23. [31]

    Molecular graph eigenvectors for molecular coordinates: System demonstration

    Patrick W Fowler, Tomaž Pisanski, and John Shawe-Taylor. Molecular graph eigenvectors for molecular coordinates: System demonstration. InInternational Symposium on Graph Drawing, pages 282–285. Springer, 1994

    1994

  24. [32]

    Genericity of simple eigenvalues for a metric graph.Israel J

    Leonid Friedlander. Genericity of simple eigenvalues for a metric graph.Israel J. Math., 146:149–156, 2005

    2005

  25. [33]

    Fyodorov

    Yan V. Fyodorov. Spectral properties of random reactance networks and random matrix pencils.J. Phys. A, 32(42):7429– 7446, 1999

    1999

  26. [34]

    Stability properties of graph neural networks.IEEE Trans

    Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks.IEEE Trans. Signal Process., 68:5680–5695, 2020

    2020

  27. [35]

    Springer Science & Business Media, 2001

    Chris Godsil and Gordon F Royle.Algebraic graph theory, volume 207. Springer Science & Business Media, 2001

    2001

  28. [36]

    Golub and Charles F

    Gene H. Golub and Charles F. Van Loan.Matrix computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, fourth edition, 2013

    2013

  29. [37]

    New spectral methods for ratio cut partitioning and clustering.IEEE transactions on computer-aided design of integrated circuits and systems, 11(9):1074–1085, 1992

    Lars Hagen and Andrew B Kahng. New spectral methods for ratio cut partitioning and clustering.IEEE transactions on computer-aided design of integrated circuits and systems, 11(9):1074–1085, 1992

    1992

  30. [38]

    A spectral approach to bandwidth and separator problems in graphs.Linear and Multilinear Algebra, 39(1-2):73–90, 1995

    Christoph Helmberg, Franz Rendl, Bojan Mohar, and Svatopluk Poljak. A spectral approach to bandwidth and separator problems in graphs.Linear and Multilinear Algebra, 39(1-2):73–90, 1995

    1995

  31. [39]

    Spectral statistics of sparse ő-Rényi graph Laplacians.Ann

    Jiaoyang Huang and Benjamin Landon. Spectral statistics of sparse ő-Rényi graph Laplacians.Ann. Inst. Henri Poincaré Probab. Stat., 56(1):120–154, 2020

    2020

  32. [40]

    Low eigenvalues of Laplacian matrices of large random graphs.Probab

    Tiefeng Jiang. Low eigenvalues of Laplacian matrices of large random graphs.Probab. Theory Related Fields, 153(3-4):671– 690, 2012

    2012

  33. [41]

    Quantum random walks: an introductory overview.Contemporary Physics, 44(4):307–327, 2003

    Julia Kempe. Quantum random walks: an introductory overview.Contemporary Physics, 44(4):307–327, 2003. 28

    2003

  34. [42]

    The expressive power of graph neural networks.Graph Neural Networks: Foundations, Frontiers, and Applications, pages 63–98, 2022

    Pan Li and Jure Leskovec. The expressive power of graph neural networks.Graph Neural Networks: Foundations, Frontiers, and Applications, pages 63–98, 2022

    2022

  35. [43]

    Distance encoding: Design provably more powerful neural networks for graph representation learning.Advances in Neural Information Processing Systems, 33:4465–4478, 2020

    Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning.Advances in Neural Information Processing Systems, 33:4465–4478, 2020

    2020

  36. [44]

    Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, and Pierre Youssef

    Alexander E. Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, and Pierre Youssef. Circular law for sparse random regular digraphs.J. Eur. Math. Soc. (JEMS), 23(2):467–501, 2021

    2021

  37. [45]

    Tail bounds for gaps between eigenvalues of sparse random matrices.Electron

    Patrick Lopatto and Kyle Luh. Tail bounds for gaps between eigenvalues of sparse random matrices.Electron. J. Probab., 26:Paper No. 130, 26, 2021

    2021

  38. [46]

    Expander graphs in pure and applied mathematics.Bull

    Alexander Lubotzky. Expander graphs in pure and applied mathematics.Bull. Amer. Math. Soc. (N.S.), 49(1):113–162, 2012

    2012

  39. [47]

    Sparse random matrices have simple spectrum.Ann

    Kyle Luh and Van Vu. Sparse random matrices have simple spectrum.Ann. Inst. Henri Poincaré Probab. Stat., 56(4):2307– 2328, 2020

    2020

  40. [48]

    Laplacian canonization: A minimalist approach to sign and basis invariant spectral embedding.Advances in Neural Information Processing Systems, 36:11296–11337, 2023

    George Ma, Yifei Wang, and Yisen Wang. Laplacian canonization: A minimalist approach to sign and basis invariant spectral embedding.Advances in Neural Information Processing Systems, 36:11296–11337, 2023

    2023

  41. [49]

    Brendan D. McKay. Subgraphs of random graphs with specified degrees.Congr. Numer., 33:213–223, 1981

    1981

  42. [50]

    Eigenvalues in combinatorial optimization

    Bojan Mohar and Svatopluk Poljak. Eigenvalues in combinatorial optimization. InCombinatorial and graph-theoretical problems in linear algebra (Minneapolis, MN, 1991), volume 50 ofIMA Vol. Math. Appl., pages 107–151. Springer, New York, 1993

    1991

  43. [51]

    Restricted invertibility revisited

    Assaf Naor and Pierre Youssef. Restricted invertibility revisited. InA journey through discrete mathematics, pages 657–691. Springer, Cham, 2017

    2017

  44. [52]

    Random matrices: tail bounds for gaps between eigenvalues.Probab

    Hoi Nguyen, Terence Tao, and Van Vu. Random matrices: tail bounds for gaps between eigenvalues.Probab. Theory Related Fields, 167(3-4):777–816, 2017

    2017

  45. [53]

    Hoi H. Nguyen. Random matrices: overcrowding estimates for the spectrum.J. Funct. Anal., 275(8):2197–2224, 2018

    2018

  46. [54]

    Nguyen and Melanie Matchett Wood

    Hoi H. Nguyen and Melanie Matchett Wood. Random integral matrices: universality of surjectivity and the cokernel. Invent. Math., 228(1):1–76, 2022

    2022

  47. [55]

    Local and global universality of random matrix cokernels.Mathematische Annalen, pages 1–94, 2024

    Hoi H Nguyen and Melanie Matchett Wood. Local and global universality of random matrix cokernels.Mathematische Annalen, pages 1–94, 2024

    2024

  48. [56]

    PhD thesis, University of Houston, 2014

    Amy Nyberg.The Laplacian spectra of random geometric graphs. PhD thesis, University of Houston, 2014

    2014

  49. [57]

    Amy Nyberg, Thilo Gross, and Kevin E. Bassler. Mesoscopic structures and the Laplacian spectra of random geometric graphs. J. Complex Netw., 3(4):543–551, 2015

    2015

  50. [58]

    The Littlewood-Offord problem and invertibility of random matrices.Adv

    Mark Rudelson and Roman Vershynin. The Littlewood-Offord problem and invertibility of random matrices.Adv. Math., 218(2):600–633, 2008

    2008

  51. [59]

    Smallest singular value of a random rectangular matrix.Comm

    Mark Rudelson and Roman Vershynin. Smallest singular value of a random rectangular matrix.Comm. Pure Appl. Math., 62(12):1707–1739, 2009

    2009

  52. [60]

    No-gaps delocalization for general random matrices

    Mark Rudelson and Roman Vershynin. No-gaps delocalization for general random matrices. Geom. Funct. Anal., 26(6):1716–1776, 2016

    2016

  53. [61]

    Partitioning of unstructured problems for parallel processing.Computing systems in engineering, 2(2- 3):135–148, 1991

    Horst D Simon. Partitioning of unstructured problems for parallel processing.Computing systems in engineering, 2(2- 3):135–148, 1991

    1991

  54. [62]

    The asymptotic distribution of a single eigenvalue gap of a Wigner matrix.Probab

    Terence Tao. The asymptotic distribution of a single eigenvalue gap of a Wigner matrix.Probab. Theory Related Fields, 157(1-2):81–106, 2013

    2013

  55. [63]

    Random matrices: universality of local eigenvalue statistics.Acta Math., 206(1):127–204, 2011

    Terence Tao and Van Vu. Random matrices: universality of local eigenvalue statistics.Acta Math., 206(1):127–204, 2011

    2011

  56. [64]

    Random matrices have simple spectrum.Combinatorica, 37(3):539–553, 2017

    Terence Tao and Van Vu. Random matrices have simple spectrum.Combinatorica, 37(3):539–553, 2017

    2017

  57. [65]

    Uhlenbeck

    K. Uhlenbeck. Generic properties of eigenfunctions.Amer. J. Math., 98(4):1059–1078, 1976

    1976

  58. [66]

    Invertibility of symmetric random matrices.Random Structures Algorithms, 44(2):135–182, 2014

    Roman Vershynin. Invertibility of symmetric random matrices.Random Structures Algorithms, 44(2):135–182, 2014

    2014

  59. [67]

    Vinson.Closest spacing of consecutive eigenvalues

    Jade P. Vinson.Closest spacing of consecutive eigenvalues. ProQuest LLC, Ann Arbor, MI, 2001. Thesis (Ph.D.)–Princeton University

    2001

  60. [68]

    Equivariant and stable positional encoding for more powerful graph neural networks.arXiv preprint arXiv:2203.00199, 2022

    Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks.arXiv preprint arXiv:2203.00199, 2022

    2022 arXiv

  61. [69]

    Generic properties of Steklov eigenfunctions.Trans

    Lihan Wang. Generic properties of Steklov eigenfunctions.Trans. Amer. Math. Soc., 375(11):8241–8255, 2022

    2022

  62. [70]

    Persistent topological laplacians–a survey.arXiv preprint arXiv:2312.07563, 2023

    Xiaoqi Wei and Guo-Wei Wei. Persistent topological laplacians–a survey.arXiv preprint arXiv:2312.07563, 2023

    2023 arXiv

  63. [71]

    Eugene P. Wigner. Characteristic vectors of bordered matrices with infinite dimensions.Ann. of Math. (2), 62:548–564, 1955

    1955

  64. [72]

    Graph neural networks: A review of methods and applications.AI open, 1:57–81, 2020

    Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications.AI open, 1:57–81, 2020

    2020

  65. [73]

    On the multiplicity one conjecture in min-max theory.Ann

    Xin Zhou. On the multiplicity one conjecture in min-max theory.Ann. of Math. (2), 192(3):767–820, 2020

    2020

  66. [74]

    Graph convolutional neural networks via scattering.Applied and Computational Har- monic Analysis, 49(3):1046–1074, 2020

    Dongmian Zou and Gilad Lerman. Graph convolutional neural networks via scattering.Applied and Computational Har- monic Analysis, 49(3):1046–1074, 2020. 29 Department of Mathematics, University of Colorado Boulder, Campus Box 395, Boulder, CO 80309 USA Email address: nicholas.c...

    2020

Pith tools

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