**DIMACS - Series in Discrete Mathematics and Theoretical Computer Science**

Volume: 63;
2004;
193 pp;
Hardcover

MSC: Primary 05; 60; 68; 82;

Print ISBN: 978-0-8218-3551-7

Product Code: DIMACS/63

List Price: $92.00

Individual Member Price: $73.60

**Electronic ISBN: 978-1-4704-4021-3
Product Code: DIMACS/63.E**

List Price: $92.00

Individual Member Price: $73.60

# Graphs, Morphisms and Statistical Physics

Share this page *Edited by *
*J. Nešetřil; P. Winkler*

A co-publication of the AMS and DIMACS

The 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.

Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published with the Association for Computer Machinery (ACM).

#### Table of Contents

# Table of Contents

## Graphs, Morphisms and Statistical Physics

- Cover Cover11
- Title page iii4
- Contents v6
- Foreword vii8
- Preface ix10
- Frontispiece xi12
- List of delivered talks xiii14
- List of participants xv16
- Efficient local search near phase transitions in combinatorial optimization 122
- On the sampling problem for 𝐻-colorings on the hypercubic lattice 1334
- Graph homomorphisms and long range action 2950
- Random walks and graph homomorphisms 4970
- Recent results on parameterized 𝐻-colorings 6586
- Rapidly mixing Markov chains for dismantleable constraint graphs 87108
- On weighted graph homomorphisms 97118
- Counting list homomorphisms for graphs with bounded degrees 105126
- On the satisfiability of random 𝑘-horn formulae 113134
- The exchange interaction, spin hamiltonians, and the symmetric group 137158
- A discrete non-Pfaffian approach to the Ising problem 145166
- Survey: Information flow on trees 155176
- Chromatic numbers of products of tournaments: Fractional aspects of Hedetniemi’s conjecture 171192
- Perfect graphs for generalized colouring-circular perfect graphs 177198
- Back Cover Back Cover1218

#### Readership

Graduate students and research mathematicians interested in probabilistic graph theory and its applications.