Abstract
In this talk, we will examine the spectrum of random k-lifts of d-regular graphs. We show that, for random shift k-lifts (which includes 2-lifts), if all the nontrivial eigenvalues of the base graph G are at most \lambda in absolute value, then with high probability depending only on the number n of nodes of G (and not on k), the absolute value of every nontrivial eigenvalue of the lift is at most O(\lambda).
While previous results on random lifts were asymptotically true with high probability in the degree of the lift k, our result is the first upperbound on spectra of lifts for bounded k. In particular, it implies that a typical small lift of a Ramanujan graph is almost Ramanujan, which might prove crucial in constructing large Ramanujan expanders of all degrees.
Joint work with Naman Agarwal and Vivek Madan.