Author(s):

Erdős, László; Knowles, Antti; Yau, HorngTzer; Yin, Jun

Article Title: 
Spectral statistics of ErdősRényi graphs I: Local semicircle law

Affiliation 

Abstract: 
We consider the ensemble of adjacency matrices of ErdősRé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ősRényi ensemble is given by the Wigner semicircle law for spectral windows of length larger than N1 (up to logarithmic corrections). As a consequence, all eigenvectors are proved to be completely delocalized in the sense that the ℓ∞norms of the ℓ2normalized eigenvectors are at most of order N1/2 with a very high probability. The estimates in this paper will be used in the companion paper [Spectral statistics of ErdősRé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ősRényi graphs

Journal Title:

Annals of Probability

Volume: 
41

Issue 
3 B

ISSN:

00911798

Publisher:

Institute of Mathematical Statistics

Date Published:

20130501

Start Page: 
2279

End Page:

2375

URL: 

DOI: 
10.1214/11AOP734

Open access: 
yes (repository) 