Sparse random graphs: Eigenvalues and eigenvectors
- 5 March 2012
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 42 (1) , 110-134
Abstract
In this paper, we prove the semi‐circular law for the eigenvalues of regular random graph Gn,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., 2012Keywords
All Related Versions
Funding Information
- Vietnam's National Foundation for Science and Technology Development, NAFOSTED
- NSF (DMS-0901216, AFOSAR-FA-9550-09-1-0167)
This publication has 27 references indexed in Scilit:
- Spectral techniques applied to sparse random graphsRandom Structures & Algorithms, 2005
- The Spectra of Random Graphs with Given Expected DegreesInternet Mathematics, 2004
- Sparse random matrices: the eigenvalue spectrum revisitedJournal of Physics A: General Physics, 2002
- Random regular graphs of high degreeRandom Structures & Algorithms, 2001
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- The degree sequence of a random graph. I. The modelsRandom Structures & Algorithms, 1997
- Some geometric aspects of graphs and their eigenfunctionsDuke Mathematical Journal, 1993
- 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
- On the Distribution of the Roots of Certain Symmetric MatricesAnnals of Mathematics, 1958