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

Let Sigma = (V,E) be a finite, d-regular bipartite graph. For any lambda > 0 let pi(lambda) be the probability measure on the independent sets of Sigma in which the set I is chosen with probability proportional to lambda(vertical bar I vertical bar) (pi(lambda) is the hard-core measure with activity lambda on Sigma). We study the Glauber dynamics, or single-site update Markov chain, whose stationary distribution is pi(lambda). 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 vertical bar V(Sigma)vertical bar. In particular, if E 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. (c) 2005 Wiley Periodicals, Inc.