Gibbs Measures and Dismantlable Graphs

We model physical systems with “hard constraints” by the space Hom(G, H) of homomorphisms from a locally finite graph G to a fixed finite constraint graph H. Two homomorphisms are deemed to be adjacent if they differ on a single site of G. We investigate what appears to be a fundamental dichotomy of constraint graphs, by giving various characterizations of a class of graphs that we call dismantlable. For instance, H is dismantlable if and only if, for every G, any two homomorphisms from G to H which differ at only finitely many sites are joined by a path in Hom(G, H). If H is dismantlable, then, for any G of bounded degree, there is some assignment of activities to the nodes of H for which there is a unique Gibbs measure on Hom(G, H). On the other hand, if H is not dismantlable (and not too trivial), then there is some r such that, whatever the assignment of activities on H, there are uncountably many Gibbs measures on Hom(Tr, H), where Tr is the (r+1)-regular tree.