Cutoff on Ramanujan complexes and classical groups

Abstract

The total-variation cutoff phenomenon has been conjectured to hold for simple random walk on all transitive expanders. However, very little is actually known regarding this conjecture, and cutoff on sparse graphs in general. In this paper we establish total-variation cutoff for simple random walk on Ramanujan complexes of type ${\tilde{A}}_d$ ($d\ge 1$). As a result, we obtain explicit generators for the finite classical groups ${\mathrm{PGL}}_n({\mathbb{F}}_q)$ for which the associated Cayley graphs exhibit total-variation cutoff.