EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Charilaos Efthymiou, Weiming Feng

Random Structures & Algorithms · 2026-12 · 69 (4)

DOI: 10.1002/rsa.70109 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 13.11.2026. Verfasst von Charilaos Efthymiou und 1 weiteren Autor:innen. Die Arbeit nennt 33 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Engineering and Physical Sciences Research Council, European Research Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this work, we study the mixing time of the single‐site Glauber dynamics for the Hard‐core model on the sparse random graph with fugacity . We show that for the typical instances of and for fugacity , the mixing time of Glauber dynamics is . Our result improves on the work in Bezáková et al. (ACM Transactions on Algorithms, 2024), which proposes an MCMC‐based sampling algorithm for the Hard‐core model on for the same region of the fugacity . Our improvements are twofold. We consider the classic Glauber dynamics, which is simpler than the algorithm in the previous paper. The bounds on mixing time we obtain are asymptotically smaller, hence our algorithm is also faster . The bounds we obtain rely on providing stronger results with regard to the Spectral Independence via the branching value than what was known before. This allows us to establish the approximate tensorisation of the entropy for our Gibbs distributions. As a 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 .

Förderung

  • Engineering and Physical Sciences Research Council
  • European Research Council

Zitieren

APA

Efthymiou, C., & Feng, W. (2026). On the Mixing Time of Glauber Dynamics for the Hard‐Core and Related Models on G(n,d/n). Random Structures & Algorithms, 69(4). https://doi.org/10.1002/rsa.70109

Vancouver

Efthymiou C, Feng W. On the Mixing Time of Glauber Dynamics for the Hard‐Core and Related Models on G(n,d/n). Random Structures & Algorithms. 2026;69(4). doi:10.1002/rsa.70109

BibTeX
@article{Efthymiou2026,
  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)},
  journal = {Random Structures & Algorithms},
  year = {2026},
  volume = {69},
  number = {4},
  doi = {10.1002/rsa.70109}
}
Kostenlos starten →