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

David Galvin, Prasad Tetali

Published 2012-06-14Version 1

Let $\gS=(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 $\gS$ in which the set $I$ is chosen with probability proportional to $\lambda^{|I|}$ ($\pi_\lambda$ is the {\em hard-core measure with activity $\lambda$ on $\gS$}). We study the Glauber dynamics, or single-site update Markov chain, whose stationary distribution is $\pi_\lambda$. We show that when $\lambda$ 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 $\lambda$ 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.