Slow mixing of Glauber Dynamics for the hard-core model on regular bipartite graphs

2012/06/14 by David Galvin, Galvin, David, Prasad Tetali +1 · 3 citations
Mathematics · Physics and Astronomy · #05C69 #68R10 #68W25 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics #Theoretical and Computational Physics

paper · pdf · doi:10.48550/arxiv.1206.3165

openalex publication_date 2012/06/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let \gS=(V,E) be a finite, d-regular bipartite graph. For any λ>0 let π_λ be the probability measure on the independent sets of \gS in which the set I is chosen with probability proportional to λ^|I| (π_λ is the \em hard-core measure with activity λ on \gS). We study the Glauber dynamics, or single-site update Markov chain, whose stationary distribution is π_λ. We show that when λ is large enough (as a function of d and the expansion of subsets of single-parity of V) then the convergence to stationarity is exponentially slow in |V(\gS)|. In particular, if \gS is the d-dimensional hypercube \0,1\^d we show that for values of λ tending to 0 as d grows, the convergence to stationarity is exponentially slow in the volume of the cube. The proof combines a conductance argument with combinatorial enumeration methods.

Cited by

• Asymptotic enumeration via graph containers and entropy
• Independent sets and colorings of K_t,t,t-free graphs
• MDNS: Masked Diffusion Neural Sampler via Stochastic Optimal Control

Related

• Glauber dynamics for the hard-core model on bounded-degree H-free graphs
• Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets
• On the Mixing Time of Glauber Dynamics for the Hard-core and Related Models on G(n,d/n)
• Sampling 3-colourings of regular bipartite graphs
• Can extra updates delay mixing?