Document Open Access Logo

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

Authors Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic, Eric Vigoda, Kuan Yang

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.33.pdf
  • Filesize: 0.49 MB
  • 15 pages

Document Identifiers

Author Details

Antonio Blanca
  • School of Computer Science, Georgia Institute of Technology, Atlanta GA 30332, USA
Andreas Galanis
  • Department of Computer Science, University of Oxford, Parks Road, Oxford, OX1 3QD, UK
Leslie Ann Goldberg
  • Department of Computer Science, University of Oxford, Parks Road, Oxford, OX1 3QD, UK
Daniel Stefankovic
  • Department of Computer Science, University of Rochester, Rochester, NY 14627, USA
Eric Vigoda
  • School of Computer Science, Georgia Institute of Technology, Atlanta GA 30332, USA
Kuan Yang
  • Department of Computer Science, University of Oxford, Parks Road, Oxford, OX1 3QD, UK

Funding

  • Blanca, Antonio: Research supported in part by NSF grants CCF-1617306 and CCF-1563838.
  • Galanis, Andreas: The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) ERC grant agreement no. 334828. The paper reflects only the authors' views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein.
  • Stefankovic, Daniel: Research supported in part by NSF grant CCF-1563757.

Cite AsGet BibTex

Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic, Eric Vigoda, and Kuan Yang. Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.33

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<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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Randomness, geometry and discrete structures
  • Theory of computation → Design and analysis of algorithms
Keywords
  • sampling
  • Potts model
  • random regular graphs
  • phase transitions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. K. S. Alexander. Mixing properties and exponential decay for lattice systems in finite volumes. Ann. Probab., 32(1A):441-487, 2004. Google Scholar
  2. V. Beffara and H. Duminil-Copin. The self-dual point of the two-dimensional random-cluster model is critical for q ≥ 1. Probability Theory and Related Fields, 153(3):511-542, 2012. Google Scholar
  3. M. Bordewich, C. Greenhill, and V. Patel. Mixing of the Glauber dynamics for the ferromagnetic Potts model. Random Structures &Algorithms, 48(1):21-52, 2016. Google Scholar
  4. G. R. Brightwell and P. Winkler. Random colorings of a Cayley tree. Contemporary combinatorics, 10:247-276, 2002. Google Scholar
  5. A. Dembo, A. Montanari, A. Sly, and N. Sun. The replica symmetric solution for Potts models on d-regular graphs. Communications in Mathematical Physics, 327(2):551-575, 2014. Google Scholar
  6. C. Efthymiou. A simple algorithm for random colouring G(n, d/n) using (2 + ε)d colours. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, pages 272-280, 2012. Google Scholar
  7. C. Efthymiou. A simple algorithm for sampling colorings of G(n,d/n) up to the Gibbs uniqueness threshold. SIAM Journal on Computing, 45(6):2087-2116, 2016. Google Scholar
  8. C. Efthymiou, T. P. Hayes, D. Štefankovič, and E. Vigoda. Sampling random colorings of sparse random graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18, pages 1759-1771, 2018. Google Scholar
  9. A. Galanis, L. A. Goldberg, and K. Yang. Uniqueness of the 3-state antiferromagnetic Potts model on the tree. arXiv/1804.03514, 2018. Google Scholar
  10. A. Galanis, D. Štefankovič, and E. Vigoda. Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region. J. ACM, 62(6):50:1-50:60, 2015. Google Scholar
  11. A. Galanis, D. Štefankovič, E. Vigoda, and L. Yang. Ferromagnetic Potts model: Refined #BIS-hardness and related results. SIAM Journal on Computing, 45(6):2004-2065, 2016. Google Scholar
  12. A. Gerschenfeld and A. Montanari. Reconstruction for models on random graphs. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS '07, pages 194-204, 2007. Google Scholar
  13. G. Grimmett. The Random-Cluster Model. Springer, 2006. Google Scholar
  14. O. Häggström. The random-cluster model on a homogeneous tree. Probability Theory and Related Fields, 104(2):231-253, 1996. Google Scholar
  15. J. Jonasson. The random cluster model on a general graph and a phase transition characterization of nonamenability. Stochastic Processes and their Applications, 79(2):335-354, 1999. Google Scholar
  16. J. Jonasson. Uniqueness of uniform random colorings of regular trees. Statistics &Probability Letters, 57(3):243-248, 2002. Google Scholar
  17. F. Martinelli and E. Olivieri. Approach to equilibrium of Glauber dynamics in the one phase region. I. The attractive case. Comm. Math. Phys., 161(3):447-486, 1994. Google Scholar
  18. F. Martinelli and E. Olivieri. Approach to equilibrium of Glauber dynamics in the one phase region. II. The general case. Communications in Mathematical Physics, 161(3):487-514, 1994. Google Scholar
  19. F. Martinelli, E. Olivieri, and R. H. Schonmann. For 2-D lattice spin systems weak mixing implies strong mixing. Communications in Mathematical Physics, 165(1):33-47, 1994. Google Scholar
  20. M. Mézard and A. Montanari. Information, Physics, and Computation. Oxford University Press, 2009. Google Scholar
  21. E. Mossel and A. Sly. Rapid mixing of Gibbs sampling on graphs that are sparse on average. Random Structures &Algorithms, 35(2):250-270, 2009. Google Scholar
  22. E. Mossel and A. Sly. Exact thresholds for Ising-Gibbs samplers on general graphs. Ann. Probab., 41(1):294-328, 2013. Google Scholar
  23. E. Mossel, D. Weitz, and N. Wormald. On the hardness of sampling independent sets beyond the tree threshold. Probability Theory and Related Fields, 143(3):401-439, 2009. Google Scholar
  24. A. Sinclair, P. Srivastava, D. Štefankovič, and Y. Yin. Spatial mixing and the connective constant: optimal bounds. Probability Theory and Related Fields, 168(1):153-197, 2017. Google Scholar
  25. A. Sinclair, P. Srivastava, and M. Thurley. Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. Journal of Statistical Physics, 155(4):666-686, 2014. Google Scholar
  26. A. Sinclair, P. Srivastava, and Y. Yin. Spatial mixing and approximation algorithms for graphs with bounded connective constant. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, pages 300-309, 2013. Google Scholar
  27. L. E. Thomas. Bound on the mass gap for finite volume stochastic Ising models at low temperature. Communications in Mathematical Physics, 126(1):1-11, 1989. Google Scholar
  28. Y. Yin and C. Zhang. Sampling in Potts model on sparse random graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, pages 47:1-47:22, 2016. Google Scholar
  29. J. Zhang, H. Liang, and F. Bai. Approximating partition functions of the two-state spin system. Information Processing Letters, 111(14):702-710, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact