2003/04/28 by Graham R. Brightwell, Peter Winkler
Mathematics · Physics and Astronomy · #math.CO #math-ph #math.MP #msc:82B20 #msc:68R10
published as Proceedings of the ICM, Beijing 2002, vol. 3, 605--624
arxiv created 2003/04/28 · arxiv updated 2009/11/30
Statistical physics models with hard constraints, such as the discrete hard-core gas model (random independent sets in a graph), are inherently combinatorial and present the discrete mathematician with a relatively comfortable setting for the study of phase transition. In this paper we survey recent work (concentrating on joint work of the authors) in which hard-constraint systems are modeled by the space \hom(G,H) of homomorphisms from an infinite graph G to a fixed finite constraint graph H. These spaces become sufficiently tractable when G is a regular tree (often called a Cayley tree or Bethe lattice) to permit characterization of the constraint graphs H which admit multiple invariant Gibbs measures. Applications to a physics problem (multiple critical points for symmetry-breaking) and a combinatorics problem (random coloring), as well as some new combinatorial notions, will be presented.