DIMACS/DIMATIA Workshop on Graphs, Morphisms and Statistical Physics

March 19-21, 2001
DIMACS Center, Rutgers University, Piscataway, New Jersey

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.