Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs

Let ∑ = (V,E) be a finite, d‐regular bipartite graph. For any λ > 0 let π_λ be the probability measure on the independent sets of ∑ in which the set I is chosen with probability proportional to λ^|I| (π_λ is the hard‐core measure with activity λ on ∑). 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(∑)|. In particular, if ∑ 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. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006