{
  "id": "2010.16227",
  "version": "v1",
  "published": "2020-10-30T12:48:58.000Z",
  "updated": "2020-10-30T12:48:58.000Z",
  "title": "Cutoffs for exclusion and interchange processes on finite graphs",
  "authors": [
    "Joe P. Chen",
    "Rodrigo Marinho"
  ],
  "comment": "v1: 17 pages, 4 figures",
  "categories": [
    "math.PR",
    "cond-mat.stat-mech",
    "math.CO"
  ],
  "abstract": "We prove a general theorem on cutoffs for symmetric exclusion and interchange processes on finite graphs $G_N=(V_N,E_N)$, under the assumption that either the graphs converge geometrically and spectrally to a compact metric measure space, or they are isomorphic to discrete Boolean hypercubes. Specifically, cutoffs occur at times $\\displaystyle t_N= (2\\gamma_1^N)^{-1}\\log |V_N|$, where $\\gamma_1^N$ is the spectral gap of the symmetric random walk process on $G_N$. Under the former assumption, our theorem is applicable to the said processes on graphs such as: the $d$-dimensional discrete grids and tori for any integer dimension $d$; the $L$-th powers of cycles for fixed $L$, a.k.a. the $L$-adjacent transposition shuffle; and self-similar fractal graphs and products thereof.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-10-30T12:48:58.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "35K05",
      "82C22",
      "60B10",
      "60B15",
      "60J27"
    ],
    "keywords": [
      "finite graphs",
      "interchange processes",
      "compact metric measure space",
      "symmetric random walk process",
      "discrete boolean hypercubes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}