Relative Expanders or Weakly Relatively Ramanujan Graphs
• Postscript version.
• Dvi version.
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.