BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Ramanujan Graphs and Finite Free Convolutions of Polynomials - Dan
  Spielman (Yale University)
DTSTART:20150602T133000Z
DTEND:20150602T143000Z
UID:TALK59051@talks.cam.ac.uk
CONTACT:Andrew Thomason
DESCRIPTION:We use the method of interlacing polynomials and a finite dime
 nsional approach to free probability to prove the existence of bipartite R
 amanujan graphs of every degree and number of vertices.  No prior knowledg
 e of Ramanujan graphs or free probability will be assumed.\n\n \n\nRamanuj
 an graphs are defined in terms of the eigenvalues of their adjacency or La
 placian matrices.  In this spectral perspective\, they are the best possib
 le expanders.  Infinite families of Ramanujan graphs were first shown to e
 xist by Margulis and Lubotzky\, Phillips and Sarnak using Deligne's proof 
 of the Ramanujan conjecture.  These constructions were sporadic\, only pro
 ducing graphs of special degrees and numbers of vertices.\n\n \n\nIn this 
 talk\, we outline an elementary proof of the existence of bipartite Ramanu
 jan graphs of very degree and number of vertices.  We do this by consideri
 ng the expected characteristic polynomial of a random d-regular graph.  We
  develop finite analogs of results in free probability to compute this pol
 ynomial and to bound its roots.  By proving that this polynomial is the av
 erage of polynomials in an interlacing family\, we then prove there exists
  a graph in the distribution whose eigenvalues satisfy the Ramanujan bound
 .\n\n \n\nThese results are joint work with Adam Marcus and Nikhil Srivast
 ava.
LOCATION:MR14
END:VEVENT
END:VCALENDAR