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

ABSTRACT 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 .

Authors

Institutions

Publication Details

Journal
Random Structures and Algorithms
Published
2026-11-13
DOI
https://doi.org/10.1002/rsa.70109
Primary Topic
Markov Chains and Monte Carlo Methods
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

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

Weiming Feng, Charilaos Efthymiou
2 links
Random Structures and Algorithms
Markov Chains and Monte Carlo Methods
article

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

Weiming Feng, Charilaos Efthymiou
article en

Abstract

ABSTRACT 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 .

Random Structures and AlgorithmsVol. 69(4)
University of Warwick (GB), University of Hong Kong (HK)
University of Warwick, European Commission, Engineering and Physical Sciences Research Council, European Research Council
Markov Chains and Monte Carlo Methods
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon