Strong Spatial Mixing in Homomorphism Spaces

Given a countable graph $\mathcal{G}$ and a finite graph $H$, we consider $Hom(\mathcal{G}, H)$ the set of graph homomorphisms from $\mathcal{G}$ to $H$ and we study Gibbs measures supported on $Hom(\mathcal{G}, H)$. We develop some sufficient and other necessary conditions for the existence of Gibbs specifications on $Hom(\mathcal{G}, H)$ satisfying strong spatial mixing (with exponential decay rate). We relate this with previous work of Brightwell and Winkler, who showed that a graph $H$ has a combinatorial property called dismantlability iff for every $\mathcal{G}$ of bounded degree, there exists a Gibbs specification with unique Gibbs measure. We strengthen their result by showing that such Gibbs specification can be chosen to have weak spatial mixing. In addition, we exhibit a subfamily of graphs $H$ for which there exists Gibbs specifications satisfying strong spatial mixing, but we also show that there exist dismantlable graphs for which no Gibbs specification has strong spatial mixing. Read More: https://epubs.siam.org/doi/10.1137/16M106617