Random walks on dynamic configuration models: a trichotomy

Abstract

We consider a dynamic random graph on $n$ vertices that is obtained by starting from a random graph generated according to the configuration model with a prescribed degree sequence and at each unit of time randomly rewiring a fraction ${\alpha }_n$ of the edges. We are interested in the mixing time of a random walk without backtracking on this dynamic random graph in the limit as $n\to \infty$, when ${\alpha }_n$ is chosen such that ${\lim }_{n\to \infty }{\alpha }_n(\log n{)}^2=\beta \in [0,\infty ]$. In [1] we found that, under mild regularity conditions on the degree sequence, the mixing time is of order $1/\sqrt{{\alpha }_n}$ when $\beta =\infty$. In the present paper we investigate what happens when $\beta \in [0,\infty )$. It turns out that the mixing time is of order $\log n$, with the scaled mixing time exhibiting a one-sided cutoff when $\beta \in (0,\infty )$ and a two-sided cutoff when $\beta =0$. The occurrence of a one-sided cutoff is a rare phenomenon. In our setting it comes from a competition between the time scales of mixing on the static graph, as identified by Ben-Hamou and Salez [4], and the regeneration time of first stepping across a rewired edge.

14 pages, 5 figures