Cutoff on Graphs and The Sarnak-Xue Density of Eigenvalues

Konstantin Golubev, Amitay Kamber

Published 2019-05-27Version 1

It was recently shown by Lubetzky and Peres and by Sardari that Ramanujan graphs, i.e., graphs with the optimal spectral gap, exhibit cutoff of the simple random walk and have optimal almost-diameter. We prove that this spectral condition can be replaced by a weaker Sarnak-Xue density property to deduce similar results. Namely, if a graph is a spectral expander and satisfies the Sarnak-Xue density property on the number of eigenvalues outside the Alon-Boppana range, it exhibits cutoff of the random walk as well as the optimal almost-radius at almost every point. Abstract. We apply the arguments of Sarnak and Xue to show that density property is equivalent to a certain path-counting property, and show that certain natural Schreier graphs of the $SL_{2}\left(\mathbb{F}_{t}\right)$-action on the projective line satisfy the Sarnak-Xue density condition, and hence exhibit cutoff of the random walk and have optimal almost-diameter.