Sparse random graphs: Eigenvalues and Eigenvectors

Abstract

In this paper we prove the semi-circular law for the eigenvalues of regular random graph $G_{n,d}$ in the case $d\to \infty$, complementing a previous result of McKay for fixed $d$. We also obtain a upper bound on the infinity norm of eigenvectors of Erdős-Rényi random graph $G(n,p)$, answering a question raised by Dekel-Lee-Linial.

30 pages, 3 figures