{
  "id": "2107.10246",
  "version": "v1",
  "published": "2021-07-21T17:50:34.000Z",
  "updated": "2021-07-21T17:50:34.000Z",
  "title": "Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics",
  "authors": [
    "Antonio Blanca",
    "Reza Gheissari"
  ],
  "comment": "41 pages, 3 figures",
  "categories": [
    "math.PR",
    "cs.DM",
    "math-ph",
    "math.MP"
  ],
  "abstract": "We consider the problem of sampling from the ferromagnetic Potts and random-cluster models on a general family of random graphs via the Glauber dynamics for the random-cluster model. The random-cluster model is parametrized by an edge probability $p \\in (0,1)$ and a cluster weight $q > 0$. We establish that for every $q\\ge 1$, the random-cluster Glauber dynamics mixes in optimal $\\Theta(n\\log n)$ steps on $n$-vertex random graphs having a prescribed degree sequence with bounded average branching $\\gamma$, throughout the uniqueness regime $p<p_u(q,\\gamma)$. Notably, this uniqueness threshold does not decay with the maximum degree and only depends on the average degree. In particular, $p_u(q,\\gamma)$ is expected to be sharp, in that for general $q$ and $\\gamma$, the random-cluster Glauber dynamics should slow down dramatically at $p_u(q,\\gamma)$. The family of random graph models we consider include the Erd\\H{o}s--R\\'enyi random graph $G(n,\\gamma/n)$, and so we provide the first polynomial-time sampling algorithm for the ferromagnetic Potts model on the Erd\\H{o}s--R\\'enyi random graphs that works for all $q$ in the full uniqueness regime. We accompany our results with mixing time lower bounds (exponential in the maximum degree) for the Potts Glauber dynamics, in the same settings where our $\\Theta(n \\log n)$ bounds for the random-cluster Glauber dynamics apply. This reveals a significant computational advantage of random-cluster based algorithms for sampling from the Potts Gibbs distribution at high temperatures in the presence of high-degree vertices.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-07-21T17:50:34.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random graph",
      "random-cluster dynamics",
      "unbounded degree",
      "random-cluster model",
      "uniqueness regime"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 41,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}