On the second eigenvalue of random regular graphs
- 1 October 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (02725428), 286-294
- https://doi.org/10.1109/sfcs.1987.45
Abstract
Expanders have many applications in Computer Science. It is known that random d-regular graphs are very efficient expanders, almost surely. However, checking whether a particular graph is a good expander is co-NP-complete. We show that the second eigenvalue of d-regular graphs, λ2, is concentrated in an interval of width O(√d) around its mean, and that its mean is O(d3/4). The result holds under various models for random d-regular graphs. As a consequence a random d-regular graph on n vertices, is, with high probability a certifiable efficient expander for n sufficiently large. The bound on the width of the interval is derived from martingale theory and the bound on E(λ2) is obtained by exploring the properties of random walks in random graphs.Keywords
This publication has 12 references indexed in Scilit:
- Ramanujan graphsCombinatorica, 1988
- Better expanders and superconcentratorsJournal of Algorithms, 1987
- Sharp concentration of the chromatic number on random graphsG n, pCombinatorica, 1987
- The token distribution problemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Eigenvalues and expandersCombinatorica, 1986
- λ1, Isoperimetric inequalities for graphs, and superconcentratorsJournal of Combinatorial Theory, Series B, 1985
- Random walks on finite groups and rapidly mixing markov chainsPublished by Springer Nature ,1983
- The complexity of testing whether a graph is a superconcentratorInformation Processing Letters, 1981
- The expected eigenvalue distribution of a large regular graphLinear Algebra and its Applications, 1981
- The eigenvalues of random symmetric matricesCombinatorica, 1981