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, 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. 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 [13] to prove the universality of eigenvalue distributions both in the bulk and at the spectral edges under the further restriction that pN ≫ N 2/3.