Towards Constructing Expanders via Lifts: Hopes and Limitations

In this talk, I 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), 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 k-lifts. based on joint and ongoing work with Naman Agarwal  Karthik Chandrasekaran and Vivek Madan

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.