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

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.

No reviews yet.

No comments yet.