Cutoff for Random Walk on Dynamical Erdős--Rényi Graph

Abstract

We consider dynamical percolation on the complete graph $K_n$, where each edge refreshes its state at rate $\mu \ll 1/n$, and is then declared open with probability $p=\lambda /n$ where $\lambda >1$. We study a random walk on this dynamical environment which jumps at rate $1/n$ along every open edge. We show that the mixing time of the full system exhibits cutoff at $\log n/\mu$. We do this by showing that the random walk component mixes faster than the environment process; along the way, we control the time it takes for the walk to become isolated.

v2. Small mistakes corrected and simplified coupling argument. Accepted version || v3. Added publication details. Updated to author's new name, from "Thomas" to "Olesker-Taylor"