## 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}(logn)
^{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 logn, 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.

Original language | English |
---|---|

Pages (from-to) | 3360-3375 |

Number of pages | 16 |

Journal | Stochastic Processes and their Applications |

Volume | 129 |

Issue number | 9 |

DOIs | |

Publication status | Published - 1 Sept 2019 |

## Keywords

- Configuration model
- Cutoff
- Mixing time
- Random dynamics
- Random walk