[CSDM] Spielman April 29 at PU PACM colloquium

[Avi Wigderson]

*Date:*April 29, Fine Hall 214, 4:30 pm
*Speaker:*Daniel Spielman, Yale University
*Title:*A good lift: bipartite Ramanujan graphs of all degrees
*Abstract:*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. We also construct infinite families of 
`irregular Ramanujan' graphs, whose eigenvalues are bounded by the 
spectral radius of their universal cover. In particular, we construct 
infinite families of (c,d)-biregular bipartite Ramanujan graphs for all 
c and d greater than 2. 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 the talk should be accessible to a broad audience. Joint work with 
Adam Marcus and Nikhil Srivastava.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/csdm/attachments/20130415/7de8b96b/attachment.html>