Hard constraints and the bethe lattice: adventures at the interface of combinatorics and statistical physics

Abstract

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 $\mathrm{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.

Cited by in corpus (11)

• On the average size of independent sets in triangle-free graphs
• The Bipartite Swapping Trick on Graph Homomorphisms
• Nonmonotonicity of phase transitions in a loss network with controls
• Containment: A Variation of Cops and Robbers
• Warmth and mobility of random graphs
• H-colouring bipartite graphs
• On four state Hard Core Models on the Cayley Tree
• A threshold phenomenon for random independent sets in the discrete hypercube
• The multi-state hard core model on a regular tree
• Relating counting complexity to non-uniform probability measures
• The average size of independent sets of graphs