Princeton Discrete Math Seminar


Constraint Graphs and Phase Transitions, Part I


Peter Winkler
Bell Laboratories


Fine Hall 224
Princeton University


2:30 - 3:30 pm
Wednesday, November 6, 1996

A `hard constraint' model in statistical mechanics is a system whose global behavior is determined by forbidding certain local configurations. Such a system is described graph-theoretically as a space of random homomorphisms from a large graph G to a fixed constraint graph H. It turns out that the qualitative behavior of such a system depends on certain properties of the constraint graph. In these two talks we present a graph-theorist's introduction to this model, including recent results with Graham Brightwell of the London School of Economics. No knowledge of physics will be assumed, and we will present many more pictures than proofs.

Part I: A Point Process and a Pursuit Game

We define the notion of a Gibbs measure for random homomorphisms and describe one famous example, the `hard-core gas model', a.k.a. random independent sets in a graph. We then connect the Gibbs measures with stationary distributions of a Markov process, and with cop-win and robber-win graphs.

Part II: Fertile Graphs and Branching Random Walks

Here we concentrate on the case where G is a regular tree, showing that `nice' Gibbs measures correspond to random walks on the constraint graph. Constraint graphs are then classified according to whether there can be a phase transition involving more than one random walk with the same local properties.

Document last modified on November 3, 1996