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 language | English (US) |
|---|---|
| Pages (from-to) | 110-134 |
| Number of pages | 25 |
| Journal | Random Structures and Algorithms |
| Volume | 42 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jan 2013 |
Keywords
- Infinity norm of eigenvector
- Regular random graphs
- Semi-circular law
- Sparse random matrix