Sampling in uniqueness from the potts and random-cluster models on random regular graphs

Blanca, A; Galanis, A; Goldberg, LA; Štefankovic, D; Vigoda, E; Yang, K

Conference item

Sampling in uniqueness from the potts and random-cluster models on random regular graphs

Abstract:: We consider the problem of sampling from the Potts model on random regular graphs. It is conjectured that sampling is possible when the temperature of the model is in the so-called uniqueness regime of the regular tree, but positive algorithmic results have been for the most part elusive. In this paper, for all integers q >= 3 and Delta >= 3, we develop algorithms that produce samples within error o(1) from the q-state Potts model on random Delta-regular graphs, whenever the temperature is in uniqueness, for both the ferromagnetic and antiferromagnetic cases. The algorithm for the antiferromagnetic Potts model is based on iteratively adding the edges of the graph and resampling a bichromatic class that contains the endpoints of the newly added edge. Key to the algorithm is how to perform the resampling step efficiently since bichromatic classes can potentially induce linear-sized components. To this end, we exploit the tree uniqueness to show that the average growth of bichromatic components is typically small, which allows us to use correlation decay algorithms for the resampling step. While the precise uniqueness threshold on the tree is not known for general values of q and Delta in the antiferromagnetic case, our algorithm works throughout uniqueness regardless of its value. In the case of the ferromagnetic Potts model, we are able to simplify the algorithm significantly by utilising the random-cluster representation of the model. In particular, we demonstrate that a percolation-type algorithm succeeds in sampling from the random-cluster model with parameters p,q on random Delta-regular graphs for all values of q >= 1 and p

Publication status:: Published

Peer review status:: Peer reviewed

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Cite

Cite this record

APA Style

Blanca, A., Galanis, A., Goldberg, L. A., Štefankovic, D., Vigoda, E., & Yang, K. (2018). Sampling in uniqueness from the potts and random-cluster models on random regular graphs. 116, 1–15.

MLA Style

Blanca, A., et al. Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs. Schloss Dagstuhl, 2018, pp. 1–15.

Chicago Style

Blanca, A, A Galanis, LA Goldberg, D Štefankovic, E Vigoda, and K Yang. 2018. “Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs.” In , 116:1–15. Schloss Dagstuhl.
Share
Print