## Graphs, Morphisms, and Statistical Physics: DIMACS Workshop Graphs, Morphisms and Statistical Physics, March 19-21, 2001, DIMACS CenterThe intersection of combinatorics and statistical physics has experienced great activity in recent years. This flurry of activity has been fertilized by an exchange not only of techniques, but also of objectives. Computer scientists interested in approximation algorithms have helped statistical physicists and discrete mathematicians overcome language problems. They have found a wealth of common ground in probabilistic combinatorics. Close connections between percolation and random graphs, graph morphisms and hard-constraint models, and slow mixing and phase transition have led to new results and perspectives. These connections can help in understanding typical behavior of combinatorial phenomena such as graph coloring and homomorphisms. Inspired by issues and intriguing new questions surrounding the interplay of combinatorics and statistical physics, a DIMACS/DIMATIA workshop was held at Rutgers University. These proceedings are the outgrowth of that meeting. This volume is intended for graduate students and research mathematicians interested in probabilistic graph theory and its applications. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Efficient Local Search near Phase Transitions in Combinatorial Optimization | 1 |

on the Hypercubic Lattice | 13 |

Graph Homomorphisms and Long Range Action | 29 |

Random Walks and Graph Homomorphisms | 49 |

Recent results on Parameterized HColoring | 65 |

Rapidly mixing Markov chains for dismantleable constraint graphs | 87 |

On weighted graph homomorphisms | 97 |

Counting List Homomorphisms for Graphs with Bounded Degrees | 105 |

On the satisfiability of random kHorn formulae | 113 |

The exchange interaction spin hamiltonians and the symmetric group | 137 |

A Discrete NonPfaffian Approach to the Ising Problem | 145 |

Information flow on trees | 155 |

Fractional aspects of Hedetniemis conjecture | 171 |

Perfect graphs for generalized colouring circular perfect graphs | 177 |

### Common terms and phrases

adjacent algorithm assume bipartite graph Brightwell circular perfect clauses coloring of G coloring problem combinatorial complete bipartite graph complete graph component condition configuration conjecture consider constraint graph contains contours Corollary corresponding counting the number defined denote digraph directed graph dismantlable Dyer edge Editors exists finite formula function G to H Gibbs measures given Glauber dynamics graph G graph homomorphisms H-coloring hamiltonian hence Hom(G HORN-SAT implies independent set induced path input graph irreflexive Ising model label Lemma Let G list coloring list homomorphisms long range action loop Markov chains Math Mathematics mean-field approximation Nesetfil node non-periodic closed walks NP-complete obtained Optimization parameterized partial weighted assignment partition phase transition polynomial Potts models probability proof of Theorem prove random walk reconstruction problem satisfies spin glass stationary distribution statistical physics subset Theorem 2.1 theory tree decomposition treewidth variables vertex of Ax vertices well-linked with respect Winkler