{
  "id": "2008.02264",
  "version": "v1",
  "published": "2020-08-05T17:47:59.000Z",
  "updated": "2020-08-05T17:47:59.000Z",
  "title": "Random-cluster dynamics on random graphs in tree uniqueness",
  "authors": [
    "Antonio Blanca",
    "Reza Gheissari"
  ],
  "comment": "31 pages, 5 figures",
  "categories": [
    "math.PR",
    "cs.DM",
    "math-ph",
    "math.MP"
  ],
  "abstract": "We establish a near-optimal rapid mixing bound for the random-cluster Glauber dynamics on random $\\Delta$-regular graphs for all $q\\ge 1$ and $p<p_u(q,\\Delta)$, where the threshold $p_u(q,\\Delta)$ corresponds to a uniqueness/non-uniqueness phase transition for the random-cluster model on the (infinite) $\\Delta$-regular tree. It is expected that for $q>2$ this threshold is sharp, and the Glauber dynamics on random $\\Delta$-regular graphs undergoes an exponential slowdown at $p_u(q,\\Delta)$. More precisely, we show that for every $q\\ge 1$, $\\Delta\\ge 3$, and $p<p_u(q,\\Delta)$, with probability $1-o(1)$ over the choice of a random $\\Delta$-regular graph on $n$ vertices, the Glauber dynamics for the random-cluster model has $O(n(\\log n)^2)$ mixing time. As a corollary, we deduce fast mixing of the Swendsen--Wang dynamics for the Potts model on random $\\Delta$-regular graphs for every $q\\ge 2$, in the tree uniqueness region. Our proof relies on a sharp bound on the \"shattering time\", i.e., the number of steps required to break up any configuration into $O(\\log n)$ sized clusters. This is established by analyzing a delicate and novel iterative scheme to simultaneously reveal the underlying random graph with clusters of the Glauber dynamics configuration on it, at a given time.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-08-05T17:47:59.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random graph",
      "random-cluster dynamics",
      "random-cluster model",
      "tree uniqueness region",
      "uniqueness/non-uniqueness phase transition"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 31,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}