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.