## DIMACS TR: 97-62

## Graph Homomorphisms and Phase Transitions

### Authors: Graham R. Brightwell and Peter Winkler

**
ABSTRACT
**

We model physical systems with "hard constraints" by the space
Hom*(G,H)* of homomorphisms from a locally finite graph *G*
to a fixed finite constraint graph *H*. For any assignment $\lambda$
of positive real activities to the nodes of *H*, there is at least
one Gibbs measure on Hom*(G,H)*; when *G* is infinite,
there may be more than one.

When *G* is a regular tree, the simple, invariant Gibbs measures on
Hom*(G,H)* correspond to node-weighted branching random walks on
*H*. we show that such walks exist for every *H* and
$\lambda$, and characterize those *H* which, by admitting more than
one such construction, exhibit phase transition behavior.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-62.ps.gz

DIMACS Home Page