BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Cutoff on all Ramanujan Graphs - Yuval Peres (Microsoft Research)
DTSTART:20160114T160000Z
DTEND:20160114T170000Z
UID:TALK62965@talks.cam.ac.uk
CONTACT:Andrew Thomason
DESCRIPTION:The Alon-Boppana bound yields the smallest possible value for 
 the second eigenvalue of a d-regular graph.  Lubotzky\, Phillips\, and Sar
 nak (1988)  defined a connected $d$-regular graph  (with d>2) to be Ramanu
 jan\niff this bound is attained\, i.e.\, for every eigenvalue of the adjac
 ency matrix\, its absolute value is either d\, or at most  twice the squar
 e root of d-1.\n\nWe determine precisely the mixing time of random walk on
  a d-regular Ramanujan graph\, and show it is the time it takes the walk t
 o reach the maximum distance from its starting point. These walks exhibit 
 cutoff: a sharp decrease of the total variation distance to the stationary
  measure in a relatively short time interval (for random d-regular graphs 
 this was proved in 2010 by Lubetzky and Sly.) We deduce new information on
  typical\ndistances: for every vertex  in an n-vertex Ramanujan graph G\, 
 its distance from most other vertices in G is asymptotically  log n (in ba
 se d-1). It remains open how large the diameter can be.\n\nThe key to our 
 proofs is a precise spectral analysis of the non-backtracking walk.  (Join
 t work with Eyal Lubetzky\, NYU http://arxiv.org/abs/1507.04725 )\n
LOCATION:MR12
END:VEVENT
END:VCALENDAR