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.ICALP.2023.54
URN: urn:nbn:de:0030-drops-181064
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18106/
Go to the corresponding LIPIcs Volume Portal

Efthymiou, Charilaos ; Feng, Weiming

On the Mixing Time of Glauber Dynamics for the Hard-Core and Related Models on G(n,d/n)

pdf-format:
LIPIcs-ICALP-2023-54.pdf (0.7 MB)

Abstract

We study the single-site Glauber dynamics for the fugacity λ, Hard-Core model on the random graph G(n, d/n). We show that for the typical instances of the random graph G(n,d/n) and for fugacity λ < {d^d} / {(d-1)^(d+1)}, the mixing time of Glauber dynamics is n^{1 + O(1/log log n)}.
Our result improves on the recent elegant algorithm in [Bezáková, Galanis, Goldberg and Štefankovič; ICALP'22]. The algorithm there is an MCMC-based sampling algorithm, but it is not the Glauber dynamics. Our algorithm here is simpler, as we use the classic Glauber dynamics. Furthermore, the bounds on mixing time we prove are smaller than those in Bezáková et al. paper, hence our algorithm is also faster.
The main challenge in our proof is handling vertices with unbounded degrees. We provide stronger results with regard the spectral independence via branching values and show that the our Gibbs distributions satisfy the approximate tensorisation of the entropy. We conjecture that the bounds we have here are optimal for G(n,d/n).
As corollary of our analysis for the Hard-Core model, we also get bounds on the mixing time of the Glauber dynamics for the Monomer-Dimer model on G(n,d/n). The bounds we get for this model are slightly better than those we have for the Hard-Core model

BibTeX - Entry

@InProceedings{efthymiou_et_al:LIPIcs.ICALP.2023.54,
  author =	{Efthymiou, Charilaos and Feng, Weiming},
  title =	{{On the Mixing Time of Glauber Dynamics for the Hard-Core and Related Models on G(n,d/n)}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{54:1--54:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18106},
  URN =		{urn:nbn:de:0030-drops-181064},
  doi =		{10.4230/LIPIcs.ICALP.2023.54},
  annote =	{Keywords: spin-system, spin-glass, sparse random (hyper)graph, approximate sampling, efficient algorithm}
}

Keywords: spin-system, spin-glass, sparse random (hyper)graph, approximate sampling, efficient algorithm
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

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