Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.20693 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914499232006144 |
|---|---|
| author | Blanca, Antonio Gheissari, Reza Park, Heehyun Zhang, Xusheng |
| author_facet | Blanca, Antonio Gheissari, Reza Park, Heehyun Zhang, Xusheng |
| contents | We study the random-cluster model on trees and treelike graphs at low temperatures. This is a model of dependent percolation parametrized by an edge probability $p\in (0,1)$ and a clustering weight $q\in [1,\infty)$, generalizing independent Bernoulli percolation ($q=1$) and closely related to the classical ferromagnetic Ising and Potts spin systems at integer $q$. For $q>2$, approximately sampling from this model on graphs of degree at most $Δ$ is computationally hard. At parameter $p$ below the tree uniqueness threshold $p_{\mathsf{u}}(q,Δ)$, it is expected that sampling is easy and local Markov chains mix rapidly on all bounded degree graphs. On typical graphs (e.g., random regular graphs), the same is predicted at $p > p_{\mathsf{s}}(q,Δ)$, where $p_{\mathsf{s}}(q,Δ)$ is a second uniqueness transition point on the $Δ$-regular wired tree.
Our first result establishes this non-uniqueness/uniqueness phase transition at $p_{\mathsf{s}}(q,Δ)$ for all $q$ on the infinite $Δ$-regular wired tree, resolving a conjecture of H{ä}ggstr{ö}m (1996). For this, we establish weak spatial mixing at $p>p_{\mathsf{s}}(q,Δ)$ under sufficiently wired boundary conditions. We use this understanding of decay of correlations to show that on the wired tree on $n$ vertices, whenever $q>1$ and $p>p_{\mathsf{s}}(q,Δ)$, the mixing time of random-cluster Glauber dynamics is a near-optimal $n^{1+o(1)}$. We then extend these results on spatial and temporal mixing from the tree to treelike geometries with mostly wired boundaries and use them to show that the random-cluster Glauber dynamics mix rapidly on the random $Δ$-regular graph for all $p>p_{\mathsf{s}}(q,Δ)$ as long as $q \ge C \log Δ$, providing an efficient sampling algorithm for both the random-cluster and Potts models in this context. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_20693 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Uniqueness and Mixing in the Low-Temperature Random-Cluster Model on Trees and Random Graphs Blanca, Antonio Gheissari, Reza Park, Heehyun Zhang, Xusheng Probability We study the random-cluster model on trees and treelike graphs at low temperatures. This is a model of dependent percolation parametrized by an edge probability $p\in (0,1)$ and a clustering weight $q\in [1,\infty)$, generalizing independent Bernoulli percolation ($q=1$) and closely related to the classical ferromagnetic Ising and Potts spin systems at integer $q$. For $q>2$, approximately sampling from this model on graphs of degree at most $Δ$ is computationally hard. At parameter $p$ below the tree uniqueness threshold $p_{\mathsf{u}}(q,Δ)$, it is expected that sampling is easy and local Markov chains mix rapidly on all bounded degree graphs. On typical graphs (e.g., random regular graphs), the same is predicted at $p > p_{\mathsf{s}}(q,Δ)$, where $p_{\mathsf{s}}(q,Δ)$ is a second uniqueness transition point on the $Δ$-regular wired tree. Our first result establishes this non-uniqueness/uniqueness phase transition at $p_{\mathsf{s}}(q,Δ)$ for all $q$ on the infinite $Δ$-regular wired tree, resolving a conjecture of H{ä}ggstr{ö}m (1996). For this, we establish weak spatial mixing at $p>p_{\mathsf{s}}(q,Δ)$ under sufficiently wired boundary conditions. We use this understanding of decay of correlations to show that on the wired tree on $n$ vertices, whenever $q>1$ and $p>p_{\mathsf{s}}(q,Δ)$, the mixing time of random-cluster Glauber dynamics is a near-optimal $n^{1+o(1)}$. We then extend these results on spatial and temporal mixing from the tree to treelike geometries with mostly wired boundaries and use them to show that the random-cluster Glauber dynamics mix rapidly on the random $Δ$-regular graph for all $p>p_{\mathsf{s}}(q,Δ)$ as long as $q \ge C \log Δ$, providing an efficient sampling algorithm for both the random-cluster and Potts models in this context. |
| title | Uniqueness and Mixing in the Low-Temperature Random-Cluster Model on Trees and Random Graphs |
| topic | Probability |
| url | https://arxiv.org/abs/2604.20693 |