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
- Weiming Feng (ORCID: https://orcid.org/0000-0003-4636-1023)
- Charilaos Efthymiou (ORCID: https://orcid.org/0000-0002-5343-3251)
Institutions
- University of Warwick (GB)
- University of Hong Kong (HK)
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
- University of Warwick
- European Commission
- Engineering and Physical Sciences Research Council
- European Research Council