Gibbs Measures and Dismantlable Graphs

✍ Scribed by Graham R. Brightwell; Peter Winkler

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 272 KB
• Volume: 78
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1999.1935

✦ Synopsis

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(T r , H), where T r is the (r+1)-regular tree.