Planting and MCMC sampling from the Potts Model

Conference item

We consider the problem of sampling from the ferromagnetic q-state Potts model on the random d-regular graph with parameter β > 0. A key difficulty that arises in sampling from the model is the existence of a “metastability” window β ∈ (βu, β′ u), where roughly the distribution has two competing modes, the so-called disordered and ordered phases. This causes classical Markov-chain algorithms to be slow mixing from worst-case initialisations. Nevertheless, Helmuth, Jenssen and Perkins (SODA ’19) designed a sampling algorithm that works for all β, when d ≥ 5 and q = d Ω(d), using polymers and cluster expansion methods; more recently, their analysis technique has been adapted to show that a Markov chain (random-cluster dynamics) mixes fast when initialised appropriately, in the same regime of q, d, β.

Despite these positive algorithmic results, a well-known bottleneck behind cluster-expansion arguments is that they inherently only work for large q, whereas it is widely conjectured that sampling on the random d-regular graph is possible for all q, d ≥ 3. The only result so far that applies to general q, d ≥ 3 is by Blanca and Gheissari who showed that the random-cluster dynamics mixes fast in the “uniqueness” regime β < βu where roughly only the disordered mode exists. For β ≥ βu however, a second subdominant mode emerges creating bottlenecks and giving rise to correlations which have been hard to handle, especially for small values of q and d.

Our main contribution is to perform a delicate analysis of the Potts distribution and the random cluster dynamics that goes beyond the threshold βu. We use planting as the main tool, a technique used in the analysis of random CSPs to capture how the space of solutions is correlated with the structure of the random instance. While planting arguments provide only weak sampling guarantees generically, here we instead combine planting with the analysis of random-cluster dynamics to obtain significantly stronger guarantees. We are thus able to show that the random-cluster dynamics initialised from all-out mixes fast for all integers q, d ≥ 3 beyond the uniqueness threshold βu, all the way to the optimal threshold βc ∈ (βu, β′ 33 u) where the dominant mode switches from disordered to ordered. A more involved analysis also applies to the ordered regime β > βc where we obtain an algorithm for all d ≥ 3 and q ≥ (5d) 5 , improving significantly upon the previous range of q, d by Carlson, Davies, Fraiman, Kolla, Potukuchi, and Yap (FOCS’22).

Authors: Galanis, A; Goldberg, L; Smolarova, P

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Schloss Dagstuhl
• Host title: 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)
• Pages: 39:1-39:19
• Series: Leibniz International Proceedings in Informatics (LIPIcs)
• Series number: 364
• Publication date: 2026-02-25
• Acceptance date: 2025-12-12
• Event title: Symposium on Theoretical Aspects of Computer Science (STACS 2026)
• Event location: Grenoble, France
• Event website: https://stacs2026.imag.fr/
• Event start date: 2026-03-10
• Event end date: 2026-03-13
• DOI: 10.4230/LIPIcs.STACS.2026.39
• Language: English
• Keywords: approximate sampling; Glauber dynamics; Potts model; random cluster model