 Location
 MSRI: Simons Auditorium
 Video

 Abstract
In this talk, I will examine the spectrum of random klifts of dregular graphs. We show that, for random shift klifts (which includes 2lifts), 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), if k is *small enough*, 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. I will also discuss some impossibility results for large k, which, as one consequence, imply that there is no hope of constructing large Ramanujan graphs from abelian klifts. based on joint and ongoing work with Naman Agarwal Karthik Chandrasekaran and Vivek Madan
 Supplements


