BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Combinatorics Seminar
SUMMARY:Ramanujan Graphs and Finite Free Convolutions of P
olynomials - Dan Spielman (Yale University)
DTSTART;TZID=Europe/London:20150602T143000
DTEND;TZID=Europe/London:20150602T153000
UID:TALK59051AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/59051
DESCRIPTION:We use the method of interlacing polynomials and a
finite dimensional approach to free probability t
o prove the existence of bipartite Ramanujan graph
s of every degree and number of vertices. No prio
r knowledge of Ramanujan graphs or free probabilit
y will be assumed.\n\n \n\nRamanujan graphs are de
fined in terms of the eigenvalues of their adjacen
cy or Laplacian matrices. In this spectral perspe
ctive\, they are the best possible expanders. Inf
inite families of Ramanujan graphs were first show
n to exist by Margulis and Lubotzky\, Phillips and
Sarnak using Deligne's proof of the Ramanujan con
jecture. These constructions were sporadic\, only
producing graphs of special degrees and numbers o
f vertices.\n\n \n\nIn this talk\, we outline an e
lementary proof of the existence of bipartite Rama
nujan graphs of very degree and number of vertices
. We do this by considering the expected characte
ristic polynomial of a random d-regular graph. We
develop finite analogs of results in free probabi
lity to compute this polynomial and to bound its r
oots. By proving that this polynomial is the aver
age of polynomials in an interlacing family\, we t
hen prove there exists a graph in the distribution
whose eigenvalues satisfy the Ramanujan bound.\n\
n \n\nThese results are joint work with Adam Marcu
s and Nikhil Srivastava.
LOCATION:MR14
CONTACT:Andrew Thomason
END:VEVENT
END:VCALENDAR