On the Sampling Problem for H-colorings on the Hypercubic Lattice

We consider the problem of random H-colorings of rectangular subsets of the hypercubic lattice Zd, with weight i 2 (0;1) for the color i. First, we assume that H is non-trivial in the sense that it is neither the completely looped complete graph nor the complete bipartite graph. We consider quasi-local Markov chains on a periodic box of even side length L, that is, Markov chains that do not change more than a fraction  < 1 of the sites in the box in any single move. For any nite, connected, non-trivial H, we show that there are weights fig such that all quasi-local ergodic Markov chains have slow mixing in the sense that the mixing time is exponential in Ld????1. Under the same conditions, we prove phase coexistence in the sense that there are at least two extremal Gibbs states. We also prove that, for a large subclass of graphs H, one can choose weights fig such that the corresponding Gibbs measure has exponentially fast spatial mixing.