Sparse random graphs: Eigenvalues and eigenvectors

Linh V. Tran, Van H. Vu, Ke Wang

Research output: Contribution to journalArticlepeer-review

89 Scopus citations


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 Erdos-Rényi random graph G(n,p), answering a question raised by Dekel-Lee-Linial.

Original languageEnglish (US)
Pages (from-to)110-134
Number of pages25
JournalRandom Structures and Algorithms
Issue number1
StatePublished - Jan 2013
Externally publishedYes


  • Infinity norm of eigenvector
  • Regular random graphs
  • Semi-circular law
  • Sparse random matrix


Dive into the research topics of 'Sparse random graphs: Eigenvalues and eigenvectors'. Together they form a unique fingerprint.

Cite this