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
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC



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


H.264 Video 14185.mp4 308 MB video/mp4 rtsp://videos.msri.org/data/000/023/093/original/14185.mp4 Download
Troubles with video?

Please report video problems to itsupport@msri.org.

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