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:Cutoff on all Ramanujan Graphs - Yuval Peres (Micr
osoft Research)
DTSTART;TZID=Europe/London:20160114T160000
DTEND;TZID=Europe/London:20160114T170000
UID:TALK62965AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/62965
DESCRIPTION:The Alon-Boppana bound yields the smallest possibl
e value for the second eigenvalue of a d-regular g
raph. Lubotzky\, Phillips\, and Sarnak (1988) de
fined a connected $d$-regular graph (with d>2) to
be Ramanujan\niff this bound is attained\, i.e.\,
for every eigenvalue of the adjacency matrix\, it
s absolute value is either d\, or at most twice t
he square root of d-1.\n\nWe determine precisely t
he mixing time of random walk on a d-regular Raman
ujan graph\, and show it is the time it takes the
walk to reach the maximum distance from its starti
ng point. These walks exhibit cutoff: a sharp decr
ease of the total variation distance to the statio
nary measure in a relatively short time interval (
for random d-regular graphs this was proved in 201
0 by Lubetzky and Sly.) We deduce new information
on typical\ndistances: for every vertex in an n-v
ertex Ramanujan graph G\, its distance from most o
ther vertices in G is asymptotically log n (in ba
se d-1). It remains open how large the diameter ca
n be.\n\nThe key to our proofs is a precise spectr
al analysis of the non-backtracking walk. (Joint
work with Eyal Lubetzky\, NYU http://arxiv.org/abs
/1507.04725 )\n
LOCATION:MR12
CONTACT:Andrew Thomason
END:VEVENT
END:VCALENDAR