Journal of the ACM Bibliography

Nabil Kahale. Eigenvalues and expansion of regular graphs. Journal of the ACM, 42(5):1091-1106, September 1995. [BibTeX entry]

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 of k/4 on the expansion of linear sized subsets of k-regular Ramanujan graphs. We improve the lower bound on the expansion of Ramanujan graphs to approximately k/2. Moreover, we construct a family of k-regular graphs with asymptotically optimal second eigenvalue and linear expansion equal to k/2. This shows that k/2 is the best bound one can obtain using the second eigenvalue method. We also show an upper bound of roughly 1 + \sqrt{k-1} on the average degree of linear-sized induced subgraphs of Ramanujan graphs. This compares positively with the classical bound 2\sqrt{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. Copyright 1995 by ACM, Inc.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Preliminary version

A preliminary version of these results was presented in:

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory

General Terms: Algorithms, Theory

Additional Key Words and Phrases: Eigenvalues, expander graphs, induced subgraphs, load balancing, Ramanujan graphs, random walks, selection networks

Selected papers that cite this one

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database