Cutoff on all Ramanujan Graphs
summary
Any sequence of non-bipartite d-regular Ramanujan graphs has simple random walk cutoff at time d/(d-2) · log_{d-1} n with only lower-order corrections, and the result extends to weakly Ramanujan families and random lifts; proof builds the walk from the non-backtracking random walk, exploits the Bass formula and an explicit two-by-two Jordan decomposition for the non-backtracking matrix, shows its eigenvalues lie on the circle of radius √(d−1), and translates those spectral estimates into l1 mixing bounds that match the stated constant.
AI-written summary · about