University of Cambridge > > Combinatorics Seminar > Cutoff on all Ramanujan Graphs

Cutoff on all Ramanujan Graphs

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

  • UserYuval Peres (Microsoft Research)
  • ClockThursday 14 January 2016, 16:00-17:00
  • HouseMR12.

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 )

This talk is part of the Combinatorics Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2019, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity