Abstract: A Markov chain over a finite state space is said to exhibit the total variation cutoff phenomenon if, starting from some Dirac measure, the total variation distance to the stationary distribution drops abruptly from near maximal to near zero. It is conjectured that simple random walks on the family of $k$-regular, transitive graphs with a two sided $\epsilon$ spectral gap exhibit total variation cutoff (for any fixed $k$ and $\epsilon). This is known to be true only in a small number of cases. In this talk we discuss a new family of such graphs that exhibit cutoff, namely the $1$-skeleton of Ramanujan complexes. This family is the first natural one -- occurring as Cayley graphs of $PGL(d, q)$ -- for which the cutoff point is at a non-optimal time. Joint work with Ori Parzanchevski.
Thu, 27/06/2019 - 10:00 to 11:15