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.