We are interested in understanding the mixing time (i.e. the time to reach equilibrium) for a discrete-time random walk moving on a network changing over time in a random fashion. To this aim, we consider a specific model where the underlying evolving network has n vertices, it is initially sampled from the so-called configuration model (a random graph ensemble with a prescribed vertex-degree sequence) and at each time-unit a given  fraction of the edge set is randomly rewired. We characterize the mentioned mixing-time for a random walk without backtracking as a function of the fraction of rewired edges. This work extends to a dynamic setup previous works on random walks on static random graphs. In particular, we show that the mixing-time is speeded-up by the presence of the edge-rewiring dynamics and depending on whether such a dynamics is slow, moderate or fast, we show the presence of so-called cutoff , half-cutoff, or absence of cutoff, respectively. 

Joint work with Hakan Guldas, Remco van der Hofstad and Frank den Hollander