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


Author(s): Erdős, László; Knowles, Antti; Yau, Horng-Tzer; Yin, Jun
Article Title: Spectral statistics of Erdős-Rényi graphs I: Local semicircle law
Affiliation
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 = 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-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 ℓ∞-norms of the ℓ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 »N2/3.
Keywords: Local semicircle law; Density of states; Erdős-Rényi graphs
Journal Title: Annals of Probability
Volume: 41
Issue 3 B
ISSN: 0091-1798
Publisher: Institute of Mathematical Statistics  
Date Published: 2013-05-01
Start Page: 2279
End Page: 2375
URL:
DOI: 10.1214/11-AOP734
Open access: yes (repository)