Sparse random graphs: Eigenvalues and eigenvectors

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

Research output: Contribution to journalArticlepeer-review

87 Scopus citations

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 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
Volume42
Issue number1
DOIs
StatePublished - Jan 2013

Keywords

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

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

Cite this