Logo

Mathematical Sciences Research Institute

Home » Workshop » Schedules » Towards Constructing Expanders via Lifts: Hopes and Limitations

Towards Constructing Expanders via Lifts: Hopes and Limitations

Hot Topics: Kadison-Singer, Interlacing Polynomials, and Beyond March 09, 2015 - March 13, 2015

March 11, 2015 (09:30 AM PDT - 10:30 AM PDT)
Speaker(s): Alexandra Kolla (University of Illinois at Urbana-Champaign)
Location: MSRI: Simons Auditorium
Video

Abstract

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

Supplements No Notes/Supplements Uploaded
Video/Audio Files

14185

H.264 Video 14185.mp4 308 MB video/mp4 rtsp://videos.msri.org/data/000/023/093/original/14185.mp4 Download
Buy the DVD

If none of the options work for you, you can always buy the DVD of this lecture. The videos are sold at cost for $20USD (shipping included). Please Click Here to send an email to MSRI to purchase the DVD.

See more of our Streaming videos on our main VMath - Streaming Video page.