Document Open Access Logo

Metastability of the Potts Ferromagnet on Random Regular Graphs

Authors Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Štefankovič, Eric Vigoda

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.45.pdf
  • Filesize: 0.78 MB
  • 20 pages

Document Identifiers

Author Details

Amin Coja-Oghlan
  • Faculty of Computer Science, TU Dortmund, Germany
Andreas Galanis
  • Department of Computer Science, University of Oxford, UK
Leslie Ann Goldberg
  • Department of Computer Science, University of Oxford, UK
Jean Bernoulli Ravelomanana
  • Faculty of Computer Science, TU Dortmund, Germany
Daniel Štefankovič
  • Department of Computer Science, Univerity of Rochester, NY, USA
Eric Vigoda
  • Computer Science, University of California Santa Barbara, CA, USA

Funding

  • Coja-Oghlan, Amin: supported by DFG CO 646/3 and 646/4.
  • Ravelomanana, Jean Bernoulli: supported by DFG CO 646/4.
  • Štefankovič, Daniel: supported by NSF grant CCF-2007287.
  • Vigoda, Eric: supported by NSF CCF-2007022.

Cite AsGet BibTex

Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Štefankovič, and Eric Vigoda. Metastability of the Potts Ferromagnet on Random Regular Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 45:1-45:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.45

Abstract

We study the performance of Markov chains for the q-state ferromagnetic Potts model on random regular graphs. While the cases of the grid and the complete graph are by now well-understood, the case of random regular graphs has resisted a detailed analysis and, in fact, even analysing the properties of the Potts distribution has remained elusive. It is conjectured that the performance of Markov chains is dictated by metastability phenomena, i.e., the presence of "phases" (clusters) in the sample space where Markov chains with local update rules, such as the Glauber dynamics, are bound to take exponential time to escape, and therefore cause slow mixing. The phases that are believed to drive these metastability phenomena in the case of the Potts model emerge as local, rather than global, maxima of the so-called Bethe functional, and previous approaches of analysing these phases based on optimisation arguments fall short of the task. Our first contribution is to detail the emergence of the metastable phases for the q-state Potts model on the d-regular random graph for all integers q,d ≥ 3, and establish that for an interval of temperatures, delineated by the uniqueness and a broadcasting threshold on the d-regular tree, the two phases coexist. The proofs are based on a conceptual connection between spatial properties and the structure of the Potts distribution on the random regular graph, rather than complicated moment calculations. This significantly refines earlier results by Helmuth, Jenssen, and Perkins who had established phase coexistence for a small interval around the so-called ordered-disordered threshold (via different arguments) that applied for large q and d ≥ 5. Based on our new structural understanding of the model, we obtain various algorithmic consequences. We first complement recent fast mixing results for Glauber dynamics by Blanca and Gheissari below the uniqueness threshold, showing an exponential lower bound on the mixing time above the uniqueness threshold. Then, we obtain tight results even for the non-local and more elaborate Swendsen-Wang chain, where we establish slow mixing/metastability for the whole interval of temperatures where the chain is conjectured to mix slowly on the random regular graph. The key is to bound the conductance of the chains using a random graph "planting" argument combined with delicate bounds on random-graph percolation.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
Keywords
  • Markov chains
  • sampling
  • random regular graph
  • Potts model

Metrics

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

Related Versions

References

  1. Emmanuel Abbe. Community detection and stochastic block models: Recent developments. Journal of Maching Learning Research, 18(1):6446-6531, 2017. Google Scholar
  2. Dimitris Achlioptas, Assaf Naor, and Yuval Peres. Rigorous location of phase transitions in hard optimization problems. Nature, 435(7043):759-764, 2005. Google Scholar
  3. Victor Bapst and Amin Coja-Oghlan. Harnessing the Bethe free energy. Random Structures and Algorithms, 49:694-741, 2016. Google Scholar
  4. Jean Barbier, Chun Lam Clement Chan, and Nicolas Macris. Concentration of multi-overlaps for random dilute ferromagnetic spin models. Journal of Statistical Physics, 180:534-557, 2019. Google Scholar
  5. Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, erg, Daniel Štefankovič, Eric Vigoda, and Kuan Yang. Sampling in uniqueness from the Potts and random-cluster models on random regular graphs. SIAM Journal on Discrete Mathematics, 34(1):742-793, 2020. Google Scholar
  6. Antonio Blanca and Reza Gheissari. Random-cluster dynamics on random regular graphs in tree uniqueness. Communications in Mathematical Physics, 386(2):1243-1287, 2021. Google Scholar
  7. Antonio Blanca and Alistair Sinclair. Dynamics for the mean-field random-cluster model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 528-543, 2015. Google Scholar
  8. Antonio Blanca, Alistair Sinclair, and Xusheng Zhang. The critical mean-field Chayes-Machta dynamics. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), 2021. Google Scholar
  9. Magnus Bordewich, Catherine Greenhill, and Viresh Patel. Mixing of the Glauber dynamics for the ferromagnetic Potts model. Random Structures and Algorithms, 48(1):21-52, 2016. Google Scholar
  10. Charlie Carlson, Ewan Davies, Nicolas Fraiman, Alexandra Kolla, Aditya Potukuchi, and Corrine Yap. Algorithms for the ferromagnetic Potts model on expanders. arXiv preprint, 2022. URL: http://arxiv.org/abs/2204.01923.
  11. Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, Joon Lee, and Jean Bernoulli Ravelomanana. The sparse parity matrix. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 822-833, 2022. Google Scholar
  12. Amin Coja-Oghlan, Charilaos Efthymiou, and Samuel Hetterich. On the chromatic number of random regular graphs. Journal of Combinatorial Theory, Series B, 116:367-439, 2016. Google Scholar
  13. Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari, Mihyun Kang, and Tobias Kapetanopoulos. Charting the replica symmetric phase. Communications in Mathematical Physics, 359(2):603-698, 2018. Google Scholar
  14. Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, and Philipp Loick. Optimal group testing. Combinatorics, Probability and Computing, 30(6):811-848, 2021. Google Scholar
  15. Amin Coja-Oghlan, Florent Krzakala, Will Perkins, and Lenka Zdeborová. Information-theoretic thresholds from the cavity method. Advances in Mathematics, 333:694-795, 2018. Google Scholar
  16. Amin Coja-Oghlan, Philipp Loick, Balázs F Mezei, and Gregory B Sorkin. The Ising antiferromagnet and max cut on random regular graphs. arXiv preprint, 2020. URL: http://arxiv.org/abs/2009.10483.
  17. Paul Cuff, Jian Ding, Oren Louidor, Eyal Lubetzky, Yuval Peres, and Allan Sly. Glauber dynamics for the mean-field Potts model. Journal of Statistical Physics, 149(3):432-477, 2012. Google Scholar
  18. Amir Dembo and Andrea Montanari. Ising models on locally tree-like graphs. The Annals of Applied Probability, 20(2):565-592, 2010. Google Scholar
  19. Amir Dembo, Andrea Montanari, Allan Sly, and Nike Sun. The replica symmetric solution for Potts models on d-regular graphs. Communications in Mathematical Physics, 327(2):551-575, 2014. Google Scholar
  20. Amir Dembo, Andrea Montanari, and Nike Sun. Factor models on locally tree-like graph. The Annals of Probability, 41(6):4162-4213, 2013. Google Scholar
  21. Charilaos Efthymiou. On sampling symmetric Gibbs distributions on sparse random graphs and hypergraphs. arXiv preprint, 2020. URL: http://arxiv.org/abs/2007.07145.
  22. Andreas Galanis, Daniel Stefankovic, Eric Vigoda, and Linji Yang. Ferromagnetic Potts model: Refined #BIS-hardness and related results. SIAM Journal of Computation, 45(6):2004-2065, 2016. Google Scholar
  23. Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Swendsen-Wang algorithm on the mean-field Potts model. Random Structures and Algorithms, 54(1):82-147, 2019. Google Scholar
  24. Reza Gheissari and Eyal Lubetzky. Mixing times of critical two-dimensional Potts models. Communications on Pure and Applied Mathematics, 71(5):994-1046, 2018. Google Scholar
  25. Reza Gheissari, Eyal Lubetzky, and Yuval Peres. Exponentially slow mixing in the mean-field Swendsen-Wang dynamics. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018. Google Scholar
  26. Reza Gheissari and Alistair Sinclair. Low-temperature Ising dynamics with random initializations. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.11296.
  27. Vivek K Gore and Mark R Jerrum. The Swendsen-Wang process does not always mix rapidly. Journal of Statistical Physics, 97(1):67-86, 1999. Google Scholar
  28. Olle Häggström. The random-cluster model on a homogeneous tree. Probability Theory and Related Fields, 104(2):231-253, 1996. Google Scholar
  29. Tyler Helmuth, Matthew Jenssen, and Will Perkins. Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs. arXiv preprint, 2020. URL: http://arxiv.org/abs/2006.11580.
  30. Svante Janson, Andrzej Rucinski, and Tomasz Luczak. Random graphs. John Wiley and Sons, 2011. Google Scholar
  31. Jungkyoung Lee. Energy landscape and metastability of curie-weiss-potts model. Journal of Statistical Physics, 187(1):1-46, 2022. Google Scholar
  32. David A Levin and Yuval Peres. Markov chains and mixing times. American Mathematical Society, 2009. Google Scholar
  33. Eyal Lubetzky and Allan Sly. Critical Ising on the square lattice mixes in polynomial time. Communications in Mathematical Physics, 313(3):815-836, 2012. Google Scholar
  34. Marc Mézard. Mean-field message-passing equations in the Hopfield model and its generalizations. Physical Review E, 95(2):022117, 2017. Google Scholar
  35. Marc Mezard and Andrea Montanari. Information, physics, and computation. Oxford University Press, 2009. Google Scholar
  36. Marc Mézard and Giorgio Parisi. The Bethe lattice spin glass revisited. The European Physical Journal B-Condensed Matter and Complex Systems, 20(2):217-233, 2001. Google Scholar
  37. Marc Mézard and Giorgio Parisi. The cavity method at zero temperature. Journal of Statistical Physics, 111(1):1-34, 2003. Google Scholar
  38. Tom Richardson and Ruediger Urbanke. Modern coding theory. Cambridge University Press, 2008. Google Scholar
  39. Nicholas Ruozzi. The bethe partition function of log-supermodular graphical models. Advances in Neural Information Processing Systems, 25, 2012. Google Scholar
  40. Allan Sly. Computational transition at the uniqueness threshold. In 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 287-296, 2010. Google Scholar
  41. Allan Sly and Nike Sun. The computational hardness of counting in two-spin models on d-regular graphs. In 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 361-369, 2012. Google Scholar
  42. Mario Ullrich. Swendsen-Wang is faster than single-bond dynamics. SIAM Journal on Discrete Mathematics, 28(1):37-48, 2014. Google Scholar
  43. Pascal O Vontobel. Counting in graph covers: A combinatorial characterization of the Bethe entropy function. IEEE Transactions on Information Theory, 59(9):6018-6048, 2013. Google Scholar
  44. Jonathan S Yedidia, William T Freeman, and Yair Weiss. Understanding belief propagation and its generalizations. Exploring artificial intelligence in the new millennium, 8:239-269, 2003. 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