DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Sixty Three
TITLE: "Graphs, Morphisms and Statistical Physics"
EDITORS: Jaroslav Nesetril & Peter Winkler

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.


The intersection of combinatorics and statistical physics has been an 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-constaint models, and between slowmixing and phase transition, have led to new results and new perspectives. These connections can help 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 rapod mixing, or even eventual mixing? The special case of proper coloring (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.

Inspired by these issues, and encouraged by Fred Roberts and other colleagues, we organized a "DIMACS/DIMATIA Workshop on Graphs, Morphisms and Statistical Physics" which took place at Rutgers University, March 19-21, 2001. The workshop was attended by 53 scientists from the U.S. and abroad, and the present volume is an outgrowth of this meeting.

Some of the topics we cover here are: percolation, random colorings, homomorphisms from and to a fixed graph, mixing, combinatorial phase transitions, threshold phenomena, scaling windows, and some purely combinatorial aspects of graph coloring.

In addition to the participants we asked several other colleagues whose research complemented the scope of the volume. The volume also contains several contributions which were directly influenced by the fruitful atmosphere of this meeting. We thank all participants for their time and effort which made the success of this meeting possible.

The workshop was a joint activity of DIMACS, New Jersey and DIMATIA, Prague and it was supported by both of these centers. Most of the organization of the volume was done by Robert Samal(DIMATIA-ITI) and without his effort the volume would hardly be possible.

The final stage of preparation of the volume was supported by Institute of Theoretical Computer Science(ITI) at Charles University, Prague (under grant LNOOAO56)


Forward                                                           vii
Preface                                                            ix
Photographs				                           xi
List of delivered talks			                         xiii
List of Participants			                           xv

Efficient Local Search Near Phase Transitions in Combinatorial
	S. Boettcher						    1

On the Sampling Problem for H-Colorings on the Hypercubic Lattice
	C. Borgs, J.T. Chayes, M. Dyer, and P. Tetali		   13

Graph Homomorphisms and Long Range Action
	G.R. Brightwell and P.Winkler				   29

Random Walks and Graph Homomorphisms
	A. Daneshgar and H. Hajiabolhassan			   49

Recent Results on Parameterized H-Colorings
	J. Diaz, M. Serna, and D. M. Thilikos			   65

Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs
	M. Dyer, M. Jerrum, and E. Vigoda			   87

On Weighted Graph Homomorphisms
	D. Galvin and P. Tetali					   97

Counting List Homomorphisms and Graphs with Bounded Degrees
	P. Hell and J. Nesetril					  105

On the Satisfiability of Random k-Horn Formulae
	G. Istrate						  113

The Exchange Interaction, Spin Hamiltonians, and the Symmetric
	J. Katriel						  137

A Discrete Non-Pfaffian Approach to the Ising Problem
	M. Loebl						  145

Survey-Information Flow on Trees
	E. Mossel						  155

Chromatic Numbers of Products of Tournaments-Fractional
Aspects of Hedetniemi's Conjecture
	C. Tardif						  171

Perfect Graphs for Generalized Colouring-Circular Perfect Graphs
	X. Zhu							  177

Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on April 14, 2004.