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 α 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 → ∞ , when α n is chosen such that lim n → ∞ α n ( log n ) 2 = β ∈ [ 0 , ∞ ] . In Avena et al. (2018) we found that, under mild regularity conditions on the degree sequence, the mixing time is of order 1 ∕ α n when β = ∞ . In the present paper we investigate what happens when β ∈ [ 0 , ∞ ) . It turns out that the mixing time is of order log n , with the scaled mixing time exhibiting a one-sided cutoff when β ∈ ( 0 , ∞ ) and a two-sided cutoff when β = 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 (2017), and the regeneration time of first stepping across a rewired edge.