Department of Mathematics
Mathematics in Science & Society
Spring 1999

In the last couple of years an explosion of work in the intersection of combinatorics and statistical mechanics has contributed lively new ideas to both areas. Of particular interest to combinatorialists are physical systems with hard constraints, such as the hard-core gas model (a.k.a. random independent sets in a graph).

In work with Graham Brightwell of the London School of Economics, we model hard-constraint systems by the space Hom(G,H) of homomorphisms from an infinite graph G to a fixed finite constraint graph H. These spaces become tractable when G is a regular tree (often called a Cayley tree or Bethe lattice), because the simple, invariant Gibbs measures on Hom(G,H) then correspond to node-weighted branching random walks on H.

With this approach we can characterize the constraint graphs H which, by admitting more than one such measure, exhibit phase transitions.