Source-linked AI summary
Sparse random graphs: Eigenvalues and Eigenvectors
Linh Tran, Van Vu, Ke Wang
TL;DR
The paper addresses spectral laws for random regular graphs and delocalization of eigenvectors in Erdős–Rényi graphs. It proves semicircle-law convergence for random regular graphs with d →∞ and establishes vanishing infinity norms for suitable eigenvector bases, with quantitative bounds away from spectral edges.
Problem
The paper studies the semicircle law for random regular graphs with growing degree and asks whether Erdős–Rényi eigenvectors have vanishing infinity norm.
Method
The paper uses random-matrix methods and a concentration theorem for eigenvalue counts on fine spectral scales.
Results
Random d-regular graphs have semicircle-law ESD when d →∞, while G(n,p) has an orthonormal eigenbasis with ||u_i||∞ = o(1) almost surely for p = ω(log n/n).
Takeaways & Limitations
The results extend semicircle-law knowledge beyond fixed-degree regular graphs and positively answer the stated Erdős–Rényi eigenvector question.
Takeaways & Limitations
The rank conclusion for random regular graphs is only partial progress toward full rank, and the perturbation setup assumes a symmetric Gaussian matrix with independent standard-normal upper-triangular entries.
Abstract
from arXiv · showhide
In this paper we prove the semi-circular law for the eigenvalues of regular random graph $G_{n,d}$ in the case $d\rightarrow \infty$, complementing a previous result of McKay for fixed $d$. We also obtain a upper bound on the infinity norm of eigenvectors of Erdős-Rényi random graph $G(n,p)$, answering a question raised by Dekel-Lee-Linial.
1 Introduction
The paper studies spectral distributions of Erdős–Rényi and random regular graphs, proving semicircle-law results for growing degree and bounds on eigenvector infinity norms. It also extends spectral concentration to smaller intervals and establishes partial rank information for random regular graphs.
- Scope: The paper studies eigenvalues and eigenvectors of Erdős–Rényi G(n,p) and random regular G_n,d graphs.These are basic random-graph models whose adjacency spectra encode structural information.
- Semicircle law: For p = ω(1/n), the normalized ESD of G(n,p) converges to the standard semicircle distribution.The limiting density has support on [−2,2].
- Eigenvector infinity norms: Every unit eigenvector of G(n,p) can be chosen with infinity norm o(1) almost surely when p = ω(log n/n).This positively answers a question raised by Dekel, Lee, and Linial.
- Scope boundary: The semicircle law fails when np = O(1) because isolated vertices create positive limiting mass at eigenvalue 0.Thus the Erdős–Rényi result requires a regime where np grows.
- Semicircle law: When d →∞, the normalized ESD of random d-regular graphs converges in distribution to the semicircle distribution, extending McKay’s fixed-degree result.The paper establishes the conjecture for all degree growth regimes covered by d →∞, using a method different from earlier work.
- Semicircle law: For intervals of length at least δ^-4/5 d^-1/10 log^1/5 d, the ESD of G_n,d satisfies a concentration result when d →∞.This gives convergence information at smaller spectral scales than the global law.
- Rank: For d = n^Θ(1), the rank of G_n,d is at least n − n^c with probability 1 − o(1), for some constant 0 < c < 1.This is presented as partial progress toward the conjecture that G_n,d almost surely has full rank.
- Eigenvector infinity norms: For eigenvalues bounded away from −2 and 2, the paper obtains a quantitative infinity-norm bound under p = g(n) log n/n.The corresponding eigenvectors satisfy ||u_i||∞ = O_κ((np)^−1/2) with overwhelming probability.
2 Semicircle law for regular random graphs
The proof establishes concentration of eigenvalue counts in intervals for normalized random matrices, then transfers the result from G(n,p) to random regular graphs through comparison. Auxiliary convex Lipschitz functions and a concentration inequality control interval counts at bulk and spectral-edge scales.
- Comparison method: The comparison method transfers concentration from G(n,p) to G_n,d by relating the probability of spectral-count failure to the probability that G(n,p) is np-regular.The regularity probability is bounded below using Lemma 2.1, while concentration for G(n,p) comes from the matrix concentration lemma.
- Concentration input: A bounded-entry Hermitian matrix with mean-zero, variance-one entries and fourth moment M4=o(n) has concentrated eigenvalue counts for intervals of length at least Ω(δ^-2/3(M4/n)^1/3).The result applies to eigenvalues of 1/√n M and supplies the key concentration input.
- Erdős-Rényi model: Applying the concentration lemma to the normalized adjacency matrix of G(n,p) yields concentration for intervals when np→∞.The application uses the normalized matrix and takes the entry bound K=1/√p.
- Proof mechanism: The proof replaces interval indicators by auxiliary convex Lipschitz functions and compares their eigenvalue statistics using a concentration inequality.The indicator of an interval is neither convex nor Lipschitz, motivating the construction of comparison functions.
- Bulk and edge regimes: The argument treats bulk and edge intervals separately because the semicircle mass scales differently near the spectral edge.In the bulk, the mass is proportional to interval length; near the edge, it scales as |I|^3/2.
- Concentration bounds: The upper- and lower-bound arguments combine auxiliary functions with convergence-rate estimates to obtain the desired concentration inequalities.The proof concludes after analogous bounds for the two directions.
3 Infinity norm of the eigenvectors
The section proves an infinity-norm bound for eigenvectors of G(n,p) by transferring results from a Gaussian-perturbed matrix and controlling eigenvector coordinates through minor spectra and concentration.
- 3.1 Small perturbation lemma: The perturbation argument transfers eigenvector delocalization from A_n + ϵN_n to A_n with some loss.The perturbation has simple eigenvalues almost surely, and continuity plus a small-perturbation lemma provides the transfer.
- 3.2 Auxiliary lemmas: The projection lemma bounds the random component in the span of these nearby minor eigenvectors.It applies to centered iid coordinates and yields the needed lower bound for the coordinate formula.
- 3.2 Auxiliary lemmas: Concentration for the ESD supplies many minor eigenvalues near the target eigenvalue, with overwhelming probability.The number of nearby eigenvalues is controlled in bulk intervals and at the spectral edge.
- 3.2 Auxiliary lemmas: The eigenvector coordinates are expressed using eigenvalues and eigenvectors of the bottom-right minor B_n−1.The coordinate formula reduces the bound to controlling denominators and projected random vectors.
Appendices
The appendix completes the proofs of Theorem 1.3, Lemma 3.4, and Lemma 3.5.
- The appendix contains the remaining proofs of Theorem 1.3, Lemma 3.4, and Lemma 3.5.
A Proof of Theorem 1.3
The proof of Theorem 1.3 establishes the semicircle law for the normalized adjacency matrix using the moment method and a classification of contributing closed walks.
- The moment method expands trace moments as sums over closed walks on the complete graph.Independence and zero means imply that only walks in which every edge appears at least twice contribute.
- The normalized ESD converges in distribution to the semicircle law with density ρ_sc supported on [−2, 2].The proof establishes convergence through moments on a compact support.
- Good walks are classified by the number of distinct edges, separating walks with fewer than m edges from those with exactly m edges when k = 2m.The two classes are estimated separately in the moment calculation.
- The number of walks of the second type is supplied by a prior counting result, completing the corresponding moment estimate.The appendix invokes Lemma A.2 for this enumeration and then obtains the second conclusion of (A.1).
B Proof of Lemma 3.4:
Lemma 3.4 is proved by applying Talagrand’s inequality to the projection norm of a bounded centered random vector and controlling its median by variance estimates.
- Talagrand’s inequality gives concentration for the convex 1-Lipschitz map Y → ||π_H(Y)||.The coordinates of Y are bounded in magnitude by 1.
- The orthogonal projection matrix satisfies trace(P^2) = trace(P), enabling control of the projected variance.This identity is used together with Chebyshev’s inequality in the median estimate.
- Choosing L = 4/σ and bounding the positive deviation yields the required median bound.The proof shows E(E+) < 1/4 and concludes the target inequality from the preceding relations.
C Proof of Lemma 3.5:
The proof establishes control of the empirical spectral distribution through the Stieltjes transform, using concentration of eigenvalue counts and resolvent estimates. These bounds yield convergence to the semicircle Stieltjes transform with overwhelming probability.
- Resolvent decomposition: The matrix decomposition uses Wn,k, obtained by deleting the kth row and column, and the independent row vector ak.The entries of ak have mean zero and variance 1/n and are independent of Wn,k.
- Bulk concentration: For p = g(n) log n/n, bulk eigenvalue counts concentrate on intervals of width Ω(g(n)^0.6 log n/np) with overwhelming probability.The concentration lemma is used together with the comparison between Mn and Wn to establish the required empirical spectral distribution control.
- Stieltjes-transform reduction: The proof reduces empirical spectral distribution control to a uniform bound on the Stieltjes transform over a fixed spectral region.Proposition C.3 converts uniform Stieltjes-transform control into eigenvalue-count control on intervals in the bulk.
- Resolvent estimates: Yk = E(Yk|Wn,k) + o(1) uniformly with overwhelming probability for all admissible z.The conditional estimate is first identified through the Stieltjes transform of Wn,k, then upgraded to the random quantity itself.
- Identification of the limit: The self-consistent relation implies either sn(z) = s(z) + o(1) or sn(z) = −z + o(1), and positivity of the imaginary part excludes the second branch.A continuity argument rules out the second possibility entirely, yielding the desired Stieltjes-transform conclusion.