### DIMACS/DIMATIA Workshop on Graphs, Morphisms and Statistical Physics

#### March 19-21, 2001

DIMACS Center, Rutgers University, Piscataway, New Jersey

**Organizers:**
**Jarik Nesetril**, DIMATIA, nesetril@kam-enterprise.ms.mff.cuni.cz
**Peter Winkler**, Bell Labs, pw@lucent.com

The intersection of combinatorics and statistical physics has been
a area of great activity over the past few years, fertilized by an
exchange not only of techniques but of objectives. Spurred by
computing theorists interested in approximation algorithms,
statistical physicists and discrete mathematicians have overcome
language problems and found a wealth of common ground in probabilistic
combinatorics.
Close connections between percolation and random graphs, between
graph morphisms and hard-constraint models, and between slow mixing
and phase transition, have led to new results and new perspectives.
The workshop will be especially directed toward the use of these
connections in understanding typical, as opposed to extremal, behavior
of combinatorial phenomena such as graph coloring and homomorphisms.

Any "nearest neighbor" system of statistical physics can be
interpreted as a space of graph morphisms---for example, morphisms
to the two-node graph with one edge and one loop correspond to the
"hard-core lattice gas model" and to random independent sets. Given
the set of morphisms from a (possibly infinite) graph G to a graph H,
when do we see long range order? When does changing the morphism
site by site (heat bath) yield rapid mixing, or even eventual mixing?
The special case of proper colorings (corresponding to the anti-
ferromagnetic Potts model at 0 temperature) is especially interesting
to graph theorists but more general notions of graph colorings may
also yield some intriguing new questions.

Some of the topics we expect to see: percolation; random colorings;
homomorphisms from and to a fixed graph; mixing; combinatorial phase
transitions; threshold phenomena and scaling windows. But the workshop
is by no means limited to these and we expect many new ideas.

Next: Call for Participation

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on January 24, 2001.