Cutoff on all Ramanujan Graphs

Add to your list(s) Download to your calendar using vCal

• Yuval Peres (Microsoft Research)
• Thursday 14 January 2016, 16:00-17:00
• MR12.

If you have a question about this talk, please contact Andrew Thomason.

The Alon-Boppana bound yields the smallest possible value for the second eigenvalue of a d-regular graph. Lubotzky, Phillips, and Sarnak (1988) defined a connected $d$-regular graph (with d>2) to be Ramanujan iff this bound is attained, i.e., for every eigenvalue of the adjacency matrix, its absolute value is either d, or at most twice the square root of d-1.

We determine precisely the mixing time of random walk on a d-regular Ramanujan graph, and show it is the time it takes the walk to 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 distances: for every vertex in an n-vertex Ramanujan graph G, its distance from most other vertices in G is asymptotically log n (in base d-1). It remains open how large the diameter can be.

The key to our proofs is a precise spectral analysis of the non-backtracking walk. (Joint work with Eyal Lubetzky, NYU http://arxiv.org/abs/1507.04725 )

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.