 |
Relative Expanders or Weakly Relatively Ramanujan Graphs
- Postscript version.
- Dvi version.
- PDF version.
-
Abstract:
Let $G$ be a fixed graph with largest (adjacency matrix) eigenvalue
$\lambda_0$ and with its universal cover having spectral radius
$\rho$.
We show that a random cover of large degree over $G$
has its ``new'' eigenvalues bounded in absolute value
by roughly $\sqrt{\lambda_0\rho}$.
This gives a positive result about finite quotients of certain trees
having ``small'' eigenvalues, provided we ignore the ``old'' eigenvalues.
This positive result contrasts with the negative result of
Lubotzky-Nagnibeda that showed that there is a tree all of whose finite
quotients are not ``Ramanujan'' in the sense of
Lubotzky-Philips-Sarnak and Greenberg.
Our main result is a ``relative version'' of the Broder-Shamir bound on
eigenvalues of random regular graphs. Some of their combinatorial techniques
are replaced by spectral techniques on the universal cover of $G$. For
the choice of $G$ that specializes our theorem to the Broder-Shamir
setting, our result slightly improves theirs.
{\bf MSC 2000 numbers:} Primary: 05C50; Secondary: 05C80, 68R10.
|