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 Optimization 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 Group 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 of Volumes
DIMACS Homepage