Spectral statistics of Erdős-Rényi graphs I: Local semicircle law

Abstract

We consider the ensemble of adjacency matrices of Erdős-Rényi random graphs, that is, graphs on $N$ vertices where every edge is chosen independently and with probability $p\equiv p(N)$. We rescale the matrix so that its bulk eigenvalues are of order one. We prove that, as long as $pN\to \infty$ (with a speed at least logarithmic in $N$), the density of eigenvalues of the Erdős-Rényi 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 ${\ell }^{\infty }$-norms of the ${\ell }^2$-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-Rényi 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\gg N^{2/3}$.

Published in at http://dx.doi.org/10.1214/11-AOP734 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (4)

• Local semicircle law and complete delocalization for Wigner random matrices
• Spectral Statistics of Erd{\H o}s-Rényi Graphs II: Eigenvalue Spacing and the Extreme Eigenvalues
• Semicircle law on short scales and delocalization of eigenvectors for Wigner random matrices
• Bulk Universality and Related Properties of Hermitian Matrix Models

Cited by in corpus (52)

• Universality of covariance matrices
• Averaging Fluctuations in Resolvents of Random Band Matrices
• A goodness-of-fit test for stochastic block models
• Edge Universality for Deformed Wigner Matrices
• Sparse Sachdev-Ye-Kitaev model, quantum chaos and gravity duals
• A Necessary and Sufficient Condition for Edge Universality of Wigner matrices
• The outliers of a deformed Wigner matrix
• Bulk universality of sparse random matrices
• Delocalization and Diffusion Profile for Random Band Matrices
• Local Kesten--McKay law for random regular graphs
• Local semicircle law for random regular graphs
• Bulk eigenvalue statistics for random regular graphs
• A necessary and sufficient condition for edge universality at the largest singular values of covariance matrices
• Fluctuations of the free energy of the spherical Sherrington-Kirkpatrick model with ferromagnetic interaction
• Delocalization of eigenvectors of random matrices with independent entries
• Correlated Random Matrices: Band Rigidity and Edge Universality
• Ferromagnetic to paramagnetic transition in spherical spin glass
• A simple random matrix model for the vibrational spectrum of jammed packings
• Edge rigidity and universality of random regular graphs of intermediate degree
• Spectral statistics of random geometric graphs
• How fast do quantum walks mix?
• Centrality metrics and localization in core-periphery networks
• Edge universality of separable covariance matrices
• Delocalization at small energy for heavy-tailed random matrices
• From Extreme Values of I.I.D. Random Fields to Extreme Eigenvalues of Finite-volume Anderson Hamiltonian
• Bounds for the Stieltjes Transform and the Density of States of Wigner Matrices
• Exponential growth of random determinants beyond invariance
• Analog quantum algorithms for the mixing of Markov chains
• A Graphon Approach to Limiting Spectral Distributions of Wigner-type Matrices
• Spherical spin glass model with external field
• Multifractal phase in the weighted adjacency matrices of random Erdös-Rényi graphs
• Vertices cannot be hidden from quantum spatial search for almost all random graphs
• Inferring hidden states in Langevin dynamics on large networks: Average case performance
• Local circular law for the product of a deterministic matrix with a random matrix
• Disentangling Giant Component and Finite Cluster Contributions in Sparse Matrix Spectra
• Diluted banded random matrices: Scaling behavior of eigenfunction and spectral properties
• Sample canonical correlation coefficients of high-dimensional random vectors: local law and Tracy-Widom limit
• Sparse General Wigner-type Matrices: Local Law and Eigenvector Delocalization
• Spectral partitioning in equitable graphs
• A spectral signature of breaking of ensemble equivalence for constrained random graphs
• Spectral gap and edge universality of dense random regular graphs
• The Asymptotic Distribution of Modularity in Weighted Signed Networks
• Linear processes in high-dimension: phase space and critical properties
• Localization of eigenvectors of non-Hermitian banded noisy Toeplitz matrices
• Random Perturbations of Matrix Polynomials
• Central limit theorem for the principal eigenvalue and eigenvector of Chung-Lu random graphs
• Overlap of a spherical spin glass model with microscopic external field
• Spectral similarity for Barabási-Albert and Chung-Lu models
• A Cyclic Layerwise QAOA Training
• Block-Approximated Exponential Random Graphs
• Disorder-promoted stability
• Kronecker-product random matrices and a matrix least squares problem