[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

THEORY SEMINAR
 
Tues., December 10, 2013
3:00 p.m.
Ryerson 251
 
Nikhil Srivastava
Microsoft Research Bangalore
http://research.microsoft.com/en-us/people/niksri
 
Title: “Bipartite Ramanujan Graphs of Every Degree”.
 
Abstract: Expander graphs are very sparse graphs which are nonetheless very well-connected, in the sense that their adjacency matrices have large spectral gap. There is a limit to how large this gap can be for a d-regular graph, and graphs which achieve the limit are called Ramanujan graphs. A beautiful number-theoretic construction of Lubotzky-Phillips-Sarnak and Margulis shows that infinite families of Ramanujan graphs exist for every d=p+1 where p is prime, leaving open the question of whether they exist for
other degrees.
 
We prove that there exist infinite families of bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence of good 2-lifts of every graph. Our proof exploits a new technique for demonstrating the existence of useful combinatorial objects that we call the ``Method of Interlacing Polynomials''. The proofs are elementary and rely on simple facts from the theory of real stable polynomials. In particular, they do not rely on number theory, and the talk should be accessible to a broad audience.
 
Joint work with Adam Marcus and Dan Spielman
 
Hosts: Prof. Laszlo Babai
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20131207/9edbd380/attachment.htm