Spectral Statistics of Erdős-Rényi Graphs II: Eigenvalue Spacing and the Extreme Eigenvalues

By L. Erdős, Antti Knowles, Horng-Tzer Yau, Jun Yin. 2011

291 citations recorded by the source corpus.

We consider the ensemble of adjacency matrices of Erdős-Rényi random graphs, i.e. graphs on N vertices where every edge is chosen independently and with probability p ≡ p(N). We rescale the matrix so that its bulk eigenvalues are of order one. Under the assumption $${p N \gg N^{2/3}}$$, we prove the universality of eigenvalue distributions both in the bulk and at the edge of the spectrum. More precisely, we prove (1) that the eigenvalue spacing of the Erdős-Rényi graph in the bulk of the spectrum has the same distribution as that of the Gaussian orthogonal ensemble; and (2) that the second largest eigenvalue of the Erdős-Rényi graph has the same distribution as the largest eigenvalue of the Gaussian orthogonal ensemble. As an application of our method, we prove the bulk universality of generalized Wigner matrices under the assumption that the matrix entries have at least 4 + ε moments.

Subfields: Geometry and Topology, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/0a86ed89fcfb2e51df9a47a5223d15b4960d91be

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geometry and Topology

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Universality for the largest eigenvalue of sample covariance matrices with general population (2013, methodology): “This strategy was raised in [17, 18, 19] for deriving both bulk and edge universality of a class of generalized Wigner matrices, and used in [11] for the local spectral statistics of Erdös-Rényi graphs.”
The Isotropic Semicircle Law and Deformation of Wigner Matrices (2011, background): “proving the spectral universality of adjacency matrices of random graphs [15, 16] as well as the universality of eigenvectors of Wigner matrices [30].”
Extremal eigenvalues of critical Erdős–Rényi graphs (2021, result): “The behaviour of the extremal eigenvalues is more subtle, and has been investigated in several recent works [2, 3, 7, 6, 9, 12, 8, 13, 14, 19, 11].”
Eigenvector distribution of Wigner matrices (2011, unknown): “(3.29) Defining ∆Xij,k := SikSjk −RikRjk , (3.30) we therefore have the trivial bound with high probability |∆Xij,k| 6 ϕCN−1/2Λ3−sε (k 6= i, j) , (3.31) where we abbreviated s := max { 1(i ∈ {a, b}) + 1(k ∈ {a, b}) , 1(j ∈ {a, b}) + 1(k ∈ {a, b}) } = 1 ( {i, j} ∩ {a, b} 6= ∅ ) + 1(k ∈ {a, b}) .”
Transition from Tracy–Widom to Gaussian fluctuations of extremal eigenvalues of sparse Erdős–Rényi graphs (2017, background): “Edge universality for sparse ensembles was proven first in the regime p N−1/3 in the works [16, 19] and then extended to the regime p N−2/3 in [46].”
Universality of covariance matrices (2011, methodology): “For proving bulk universality of eigenvalues, we follow the general approach for the universality of Gaussian divisible ensembles [17, 18, 10, 11, 25, 26] by embedding the covariance matrix into a stochastic flow of matrices and so that the eigenvalues evolve according to a distinguished coupled sys”