Blanca, Antonio ;
Galanis, Andreas ;
Goldberg, Leslie Ann ;
Stefankovic, Daniel ;
Vigoda, Eric ;
Yang, Kuan
Sampling in Uniqueness from the Potts and RandomCluster 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 socalled 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 qstate Potts model on random Deltaregular 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 linearsized 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 randomcluster representation of the model. In particular, we demonstrate that a percolationtype algorithm succeeds in sampling from the randomcluster model with parameters p,q on random Deltaregular graphs for all values of q >= 1 and p<p_c(q,Delta), where p_c(q,Delta) corresponds to a uniqueness threshold for the model on the Deltaregular tree. When restricted to integer values of q, this yields a simplified algorithm for the ferromagnetic Potts model on random Deltaregular graphs.
BibTeX  Entry
@InProceedings{blanca_et_al:LIPIcs:2018:9437,
author = {Antonio Blanca and Andreas Galanis and Leslie Ann Goldberg and Daniel Stefankovic and Eric Vigoda and Kuan Yang},
title = {{Sampling in Uniqueness from the Potts and RandomCluster Models on Random Regular Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {33:133:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770859},
ISSN = {18688969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9437},
URN = {urn:nbn:de:0030drops94371},
doi = {10.4230/LIPIcs.APPROXRANDOM.2018.33},
annote = {Keywords: sampling, Potts model, random regular graphs, phase transitions}
}
13.08.2018
Keywords: 

sampling, Potts model, random regular graphs, phase transitions 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Issue date: 

2018 
Date of publication: 

13.08.2018 