Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs

DOI10.4230/LIPICS.APPROX-RANDOM.2018.33arXiv1804.08111MaRDI QIDQ6300643FDOQ6300643

Leslie Ann Goldberg, Eric Vigoda, Andreas Galanis, Kuan Yang, D. Štefankovič, Antonio Blanca

Publication date: 22 April 2018

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 uniqueness regime of the regular tree, but positive algorithmic results have been for the most part elusive. In this paper, for all integers $qgeq3$ and $Deltageq3$, 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 may 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 simplify the algorithm significantly by utilising the random-cluster representation of the model. In particular, we show 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 $qgeq1$ and $p<p_c(q,Delta)$, where $p_c(q,Delta)$ corresponds to a uniqueness threshold for the model on the $Delta$-regular tree. When restricted to integer values of $q$, this yields a simplified algorithm for the ferromagnetic Potts model on random $Delta$-regular graphs.

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Phase transitions (general) in equilibrium statistical mechanics (82B26) Percolation (82B43) Statistical mechanics of magnetic materials (82D40)

This page was built for publication: Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6300643)