
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
LubotzkyNagnibeda that showed that there is a tree all of whose finite
quotients are not ``Ramanujan'' in the sense of
LubotzkyPhilipsSarnak and Greenberg.
Our main result is a ``relative version'' of the BroderShamir 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 BroderShamir
setting, our result slightly improves theirs.
{\bf MSC 2000 numbers:} Primary: 05C50; Secondary: 05C80, 68R10.
