Eigenvalues and expansion of regular graphs
Author:
Open Access
- 1 September 1995
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 42 (5) , 1091-1106
Abstract
The spectral method is the best currently known technique to prove lower bounds on expansion. Ramanujan graphs, which have asymptotically optimal second eigenvalue, are the best-known explicit expanders. The spectral method yielded a lower bound ofk/4 on the expansion of linear-sized subsets ofk-regular Ramanujan graphs. We improve the lower bound on the expansion of Ramanujan graphs to approximatelyk/2. Moreover, we construct a family ofk-regular graphs with asymptotically optimal second eigenvalue and linear expansion equal tok/2. This shows thatk/2 is the best bound one can obtain using the second eigenvalue method. We also show an upper bound of roughly 1 + √k - 1 on the average degree of linear-sized induced subgraphs of Ramanujan graphs. This compares positively with the classical bound 2√k - 1. As a byproduct, we obtain improved results on random walks on expanders and construct selection networks (respectively, extrovert graphs) of smaller size (respectively, degree) than was previously known.Keywords
This publication has 17 references indexed in Scilit:
- On the second eigenvalue and random walks in randomd-regular graphsCombinatorica, 1991
- Selection NetworksSIAM Journal on Computing, 1991
- On the second eigenvalue of a graphDiscrete Mathematics, 1991
- Explicit construction of linear sized tolerant networksDiscrete Mathematics, 1988
- Ramanujan graphsCombinatorica, 1988
- Better expanders and superconcentratorsJournal of Algorithms, 1987
- Eigenvalues and expandersCombinatorica, 1986
- Expanders and DiffusersSIAM Journal on Algebraic Discrete Methods, 1986
- λ1, Isoperimetric inequalities for graphs, and superconcentratorsJournal of Combinatorial Theory, Series B, 1985
- Graph-theoretic properties in computational complexityJournal of Computer and System Sciences, 1976