# Princeton Discrete Math Seminar

## Title:

Constraint Graphs and Phase Transitions, Part I

## Speaker:

- Peter Winkler
- Bell Laboratories

## Place:

- Fine Hall 224
- Princeton University

## Time:

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

Abstract:
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