Abstract

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 )