It is well-known that a random walk on a (connected, finite, non-bipartite) graph converges to its invariant distribution. For some graphs it has been observed that this convergence happens rather abruptly. This phenomenon is called cutoff, and it has been established widely, but in general there is little understanding for what causes it.

In this work we consider a model with a small amount of randomness. Given some deterministic graphs, we apply a random perturbation on them and based on the strength of the perturbation, we establish a phase transition in whether the resulting graphs have cutoff.

The first part of the talk will be an overview about mixing times and cutoff. In the second part we will focus on our model and explain the ideas behind the results.

Based on joint work with Jonathan Hermon, Andela Sarkovic and Perla Sousi.