{
  "id": "1803.04824",
  "version": "v1",
  "published": "2018-03-13T14:16:19.000Z",
  "updated": "2018-03-13T14:16:19.000Z",
  "title": "Random walks on dynamic configuration models: a trichotomy",
  "authors": [
    "Luca Avena",
    "Hakan Guldas",
    "Remco van der Hofstad",
    "Frank den Hollander"
  ],
  "comment": "14 pages, 5 figures",
  "categories": [
    "math.PR"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-03-13T14:16:19.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60K37",
      "82C27"
    ],
    "keywords": [
      "dynamic configuration models",
      "random walk",
      "mixing time",
      "dynamic random graph",
      "degree sequence"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}