COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

## Cutoff on all Ramanujan GraphsAdd 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
- Interested Talks
- MR12
- School of Physical Sciences
- bld31
Note that ex-directory lists are not shown. |
## Other listsIMS-MRL External Seminar series Cavendish Graduate Students' Conference 2009 Cambridge Radiology Forum## Other talksEnvironmental shocks and demographic consequences in England: 1280-1325 and 1580-1640 compared Using Inclusive Design to Focus on User Experience (UX) “Structural Biology and Chemistry of Histone Deacetylases in Human Disease and Drug Discover Dynamical large deviations in glassy systems Rather more than Thirty-Nine Steps: the life of John Buchan Improving on Nature: Biotechnology and the Ethics of Animal Enhancement |