DIMACS TR: 93-70
Eigenvalues and Expansion of Regular Graphs
Author: 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}$. For a linear-sized subset $X$ and integer $t\ge2$,
we show that the set of nodes at distance $t$ from $X$ has size at
least $k(k-2)(k-1)^{t-2}|X|/2$. Given a graph $H$, we exhibit a
necessary and sufficient condition for the existence of a family of
$k$-regular graphs having a given asymptotic bound on the second
eigenvalue, and containing $H$ as an induced subgraph. As a
byproduct, we obtain improved bounds on random walks on expanders,
we construct selection networks (resp. extrovert graphs) of smaller
size (resp. degree) than was previously known, and we construct
highly expanding non-Ramanujan graphs.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-70.ps
DIMACS Home Page