TY - GEN
T1 - Sampling from Potts on Random Graphs of Unbounded Degree via Random-Cluster Dynamics
AU - Blanca, Antonio
AU - Gheissari, Reza
N1 - Funding Information:
Thanks the Miller Institute for Basic Research for its support.
Publisher Copyright:
© Antonio Blanca and Reza Gheissari.
PY - 2022/9/1
Y1 - 2022/9/1
N2 - 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 ∈ (0, 1) and a cluster weight q > 0. We establish that for every q ≥ 1, the random-cluster Glauber dynamics mixes in optimal Θ(n log n) steps on n-vertex random graphs having a prescribed degree sequence with bounded average branching γ throughout the full high-temperature uniqueness regime p < pu(q, γ). The family of random graph models we consider includes the Erdős-Rényi random graph G(n, γ/n), and so we provide the first polynomial-time sampling algorithm for the ferromagnetic Potts model on Erdős-Rényi random graphs for the full tree uniqueness regime. We accompany our results with mixing time lower bounds (exponential in the largest degree) for the Potts Glauber dynamics, in the same settings where our Θ(n log n) bounds for the random-cluster Glauber dynamics apply. This reveals a novel and significant computational advantage of random-cluster based algorithms for sampling from the Potts model at high temperatures.
AB - 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 ∈ (0, 1) and a cluster weight q > 0. We establish that for every q ≥ 1, the random-cluster Glauber dynamics mixes in optimal Θ(n log n) steps on n-vertex random graphs having a prescribed degree sequence with bounded average branching γ throughout the full high-temperature uniqueness regime p < pu(q, γ). The family of random graph models we consider includes the Erdős-Rényi random graph G(n, γ/n), and so we provide the first polynomial-time sampling algorithm for the ferromagnetic Potts model on Erdős-Rényi random graphs for the full tree uniqueness regime. We accompany our results with mixing time lower bounds (exponential in the largest degree) for the Potts Glauber dynamics, in the same settings where our Θ(n log n) bounds for the random-cluster Glauber dynamics apply. This reveals a novel and significant computational advantage of random-cluster based algorithms for sampling from the Potts model at high temperatures.
UR - http://www.scopus.com/inward/record.url?scp=85139094359&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85139094359&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX/RANDOM.2022.24
DO - 10.4230/LIPIcs.APPROX/RANDOM.2022.24
M3 - Conference contribution
AN - SCOPUS:85139094359
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022
A2 - Chakrabarti, Amit
A2 - Swamy, Chaitanya
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 25th International Conference on Approximation Algorithms for Combinatorial Optimization Problems and the 26th International Conference on Randomization and Computation, APPROX/RANDOM 2022
Y2 - 19 September 2022 through 21 September 2022
ER -