Spectra of lifted Ramanujan graphs

Abstract

A random $n$-lift of a base graph $G$ is its cover graph $H$ on the vertices $[n]\times V(G)$, where for each edge $u v$ in $G$ there is an independent uniform bijection $π$, and $H$ has all edges of the form $(i,u),(π(i),v)$. A main motivation for studying lifts is understanding Ramanujan graphs, and namely whether typical covers of such a graph are also Ramanujan. Let $G$ be a graph with largest eigenvalue $λ_1$ and let $ρ$ be the spectral radius of its universal cover. Friedman (2003) proved that every "new" eigenvalue of a random lift of $G$ is $O(ρ^{1/2}λ_1^{1/2})$ with high probability, and conjectured a bound of $ρ+o(1)$, which would be tight by results of Lubotzky and Greenberg (1995). Linial and Puder (2008) improved Friedman's bound to $O(ρ^{2/3}λ_1^{1/3})$. For $d$-regular graphs, where $λ_1=d$ and $ρ=2\sqrt{d-1}$, this translates to a bound of $O(d^{2/3})$, compared to the conjectured $2\sqrt{d-1}$. Here we analyze the spectrum of a random $n$-lift of a $d$-regular graph whose nontrivial eigenvalues are all at most $λ$ in absolute value. We show that with high probability the absolute value of every nontrivial eigenvalue of the lift is $O((λ\vee ρ) \log ρ)$. This result is tight up to a logarithmic factor, and for $λ\leq d^{2/3-ε}$ it substantially improves the above upper bounds of Friedman and of Linial and Puder. In particular, it implies that a typical $n$-lift of a Ramanujan graph is nearly Ramanujan.

34 pages, 4 figures