Spectral statistics of Erdős–Rényi graphs I: Local semicircle law
By L'aszl'o ErdHos, Antti Knowles, Horng-Tzer Yau, Jun Yin. 2011
347 citations recorded by the source corpus.
We consider the ensemble of adjacency matrices of Erdős–Renyi random graphs, that is, 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. We prove that, as long as pN→∞ (with a speed at least logarithmic in N), the density of eigenvalues of the Erdős–Renyi ensemble is given by the Wigner semicircle law for spectral windows of length larger than N−1 (up to logarithmic corrections). As a consequence, all eigenvectors are proved to be completely delocalized in the sense that the l∞-norms of the l2-normalized eigenvectors are at most of order N−1/2 with a very high probability. The estimates in this paper will be used in the companion paper [Spectral statistics of Erdős–Renyi graphs II: Eigenvalue spacing and the extreme eigenvalues (2011) Preprint] to prove the universality of eigenvalue distributions both in the bulk and at the spectral edges under the further restriction that pN≫N2/3.
Subfields: Geometry and Topology, Mathematical Physics, Statistics and Probability
View Paper: https://www.semanticscholar.org/paper/9c5eb0a7e6f66ba14001a780db9ec56cd8faf6fe
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
- Lectures on the local semicircle law for Wigner matrices (2016, methodology): “A local law for the Erdős-Rényi graph was derived in [34].”
- Universality of local spectral statistics of random matrices (2011, neutral): “The extension of the local semicircle law to the Erdős-Rényi matrices was recently made in [25].”
- Eigenvector Statistics of Sparse Random Matrices (2016, methodology): “For the first step, the local semicircle laws for sparse random matrices were established in [12] for Erdős-Rényi graphs, and in [3] for p-regular graphs.”
- A Dynamical Approach to Random Matrix Theory (2017, background): “Optimal local law was proved in [56], bulk universality for p N−1/3 in [53] and for p N−1 in [83].”
- Edge universality of correlation matrices (2011, methodology): “The Green function comparison method has subsequently been applied to proving the spectral universality of adjacency matrices of random graphs [3, 4], the universality of eigenvectors of Wigner matrices [20], as well as the the spectrum of additive finite-rank deformations of Wigner matrices and the”
- 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].”
- Universality for the largest eigenvalue of sample covariance matrices with general population (2013, methodology): “ij)ΣM 0ri(Gii) −1G ik(Gkk) −1G kj −r∗ jG (ij)ΣM 0ri(Gii) −1G ik(Gkk) −1G ki(G (k) ii ) −1G(k) ij +r∗ kG (ijk)ΣM 0ri(G (k) ii ) −1G(k) ij (G (i) jj ) −1G(i) jk ≤ O(X3), in Θ. Now we pursue the idea in [9] to introduce a class of rational functions in resolvent matrix elements. For fixed positive integ”
- Delocalization of eigenvectors of random matrices with independent entries (2013, background): “Delocalization properties with varying degrees of strength and generality were then established for several other symmetric and Hermitian ensembles – band matrices [5, 6, 9], sparse matrices (adjacency matrices of Erdös-Renyi graphs) [7, 8], heavy-tailed matrices [2, 1], and sample covariance matric”