Journal of the Association for Computing Machinery, Vol. 42, No. 5, September 1995 (To appear)

Eigenvalues and Expansion of Regular Graphs

NABIL KAHALE

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 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.

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

Copyright 1995 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.