Sparse random graphs: Eigenvalues and Eigenvectors
Authors:
Preprint
Abstract
In this paper we prove the semi-circular law for the eigenvalues of regular random graph $G_{n,d}$ in the case $d\rightarrow \infty$, complementing a previous result of McKay for fixed $d$. We also obtain a upper bound on the infinity norm of eigenvectors of Erd\H{o}s-R\'enyi random graph $G(n,p)$, answering a question raised by Dekel-Lee-Linial.
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Non-localization of eigenfunctions on large regular graphsIsrael Journal of Mathematics, 2012
- Spectra of Large Random TreesJournal of Theoretical Probability, 2011
- Random matrices: Universality of local eigenvalue statisticsActa Mathematica, 2011
- Random Matrices: Universality of Local Eigenvalue Statistics up to the EdgeCommunications in Mathematical Physics, 2010
- Local Semicircle Law and Complete Delocalization for Wigner Random MatricesCommunications in Mathematical Physics, 2008
- Rate of convergence to the semi-circular lawProbability Theory and Related Fields, 2003
- Random regular graphs of high degreeRandom Structures & Algorithms, 2001
- Asymptotic enumeration by degree sequence of graphs with degreeso(n 1/2)Combinatorica, 1991
- On the second eigenvalue and random walks in randomd-regular graphsCombinatorica, 1991
- The expected eigenvalue distribution of a large regular graphLinear Algebra and its Applications, 1981