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 g raph H. Two homomorphisms are deemed to be adjacent if they differ on a sin gle site of G. We investigate what appears to be a fundamental dichotomy of constraint graphs, by giving various characterizations of a class of graph s that we call dismanatlable. For instance. H is dismantlable if and only i f, for every G, any two homomorphisms from G to H which differ at only fini tely many sites are joined by a path in Hom(G, H). If H is dismantlable, th en, 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 t he other hand, if H is nor dismantlable (and not too trivial), then there i s some r such that, whatever the assignment of activities on H. there are u ncountably many Gibbs measures on Hom(T-r, H), where T-r is the (r + 1)-reg ular tree. (C) 2000 Academic Press.