License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.64
URN: urn:nbn:de:0030-drops-188896
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18889/
Go to the corresponding LIPIcs Volume Portal

Galanis, Andreas ; Goldberg, Leslie Ann ; Smolarova, Paulina

Sampling from the Random Cluster Model on Random Regular Graphs at All Temperatures via Glauber Dynamics

pdf-format:
LIPIcs-APPROX64.pdf (0.6 MB)

Abstract

We consider the performance of Glauber dynamics for the random cluster model with real parameter q > 1 and temperature β > 0. Recent work by Helmuth, Jenssen and Perkins detailed the ordered/disordered transition of the model on random Δ-regular graphs for all sufficiently large q and obtained an efficient sampling algorithm for all temperatures β using cluster expansion methods. Despite this major progress, the performance of natural Markov chains, including Glauber dynamics, is not yet well understood on the random regular graph, partly because of the non-local nature of the model (especially at low temperatures) and partly because of severe bottleneck phenomena that emerge in a window around the ordered/disordered transition.
Nevertheless, it is widely conjectured that the bottleneck phenomena that impede mixing from worst-case starting configurations can be avoided by initialising the chain more judiciously. Our main result establishes this conjecture for all sufficiently large q (with respect to Δ). Specifically, we consider the mixing time of Glauber dynamics initialised from the two extreme configurations, the all-in and all-out, and obtain a pair of fast mixing bounds which cover all temperatures β, including in particular the bottleneck window. Our result is inspired by the recent approach of Gheissari and Sinclair for the Ising model who obtained a similar-flavoured mixing-time bound on the random regular graph for sufficiently low temperatures. To cover all temperatures in the RC model, we refine appropriately the structural results of Helmuth, Jenssen and Perkins about the ordered/disordered transition and show spatial mixing properties "within the phase", which are then related to the evolution of the chain.

BibTeX - Entry

@InProceedings{galanis_et_al:LIPIcs.APPROX/RANDOM.2023.64,
  author =	{Galanis, Andreas and Goldberg, Leslie Ann and Smolarova, Paulina},
  title =	{{Sampling from the Random Cluster Model on Random Regular Graphs at All Temperatures via Glauber Dynamics}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{64:1--64:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18889},
  URN =		{urn:nbn:de:0030-drops-188896},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.64},
  annote =	{Keywords: approximate counting, Glauber dynamics, random cluster model, approximate sampling, random regular graphs}
}

Keywords: approximate counting, Glauber dynamics, random cluster model, approximate sampling, random regular graphs
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Issue Date: 2023
Date of publication: 04.09.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI