EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Metastability of the Potts Ferromagnet on Random Regular Graphs

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

Communications in Mathematical Physics · 2023-07 · 401 (1) · 185-225

DOI: 10.1007/s00220-023-04644-6 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Communications in Mathematical Physics, online erschienen am 09.02.2023. Verfasst von Amin Coja-Oghlan und 5 weiteren Autor:innen. Die Arbeit wurde bisher 12-mal zitiert (Crossref) und nennt 52 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Deutsche Forschungsgemeinschaft, National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 two relevant phases for the q -state Potts model on the d -regular random graph for all integers $$q,d\ge 3$$ 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 (as possible metastable states). 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\ge 5$$ d ≥ 5 . Based on our new structural understanding of the model, our second contribution is to obtain metastability results for two classical Markov chains for the Potts model. We first complement recent fast mixing results for Glauber dynamics by Blanca and Gheissari below the uniqueness threshold, by 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.

Förderung

  • Deutsche Forschungsgemeinschaft
  • National Science Foundation

Zitieren

APA

Coja-Oghlan, A., Galanis, A., Goldberg, L. A., Ravelomanana, J. B., Štefankovič, D., & Vigoda, E. (2023). Metastability of the Potts Ferromagnet on Random Regular Graphs. Communications in Mathematical Physics, 401(1), 185-225. https://doi.org/10.1007/s00220-023-04644-6

Vancouver

Coja-Oghlan A, Galanis A, Goldberg LA, Ravelomanana JB, Štefankovič D, Vigoda E. Metastability of the Potts Ferromagnet on Random Regular Graphs. Communications in Mathematical Physics. 2023;401(1):185-225. doi:10.1007/s00220-023-04644-6

BibTeX
@article{CojaOghlan2023,
  author = {Coja-Oghlan, Amin and Galanis, Andreas and Goldberg, Leslie Ann and Ravelomanana, Jean Bernoulli and Štefankovič, Daniel and Vigoda, Eric},
  title = {Metastability of the Potts Ferromagnet on Random Regular Graphs},
  journal = {Communications in Mathematical Physics},
  year = {2023},
  volume = {401},
  number = {1},
  pages = {185--225},
  doi = {10.1007/s00220-023-04644-6}
}
Kostenlos starten →