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 → ∞ , 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. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012