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

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 dd fugacity λ <(d−1)d+1, the mixing time of Glauber dynamics is n1+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.