## 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

### 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 |

### Other editions - View all

Graphs, Morphisms, and Statistical Physics: DIMACS Workshop Graphs ... Jaroslav Nešetřil,Peter Winkler No preview available - 2004 |

### Common terms and phrases

### Popular passages

### References from web pages

Volume 63 "Graphs, Morphisms and Statistical Physics"

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

dimacs.rutgers.edu/ Volumes/ Vol63.html

Research Activity

Martin Dyer's Papers. Preprints. "An approximation trichotomy for Boolean #CSP" Martin Dyer, Leslie Ann Goldberg and Mark Jerrum arxiv:0710.4272v1 [cs. ...

www.comp.leeds.ac.uk/ dyer/ pub.shtml

New Books for 05/14/2004

TITLE: Graphs, morphisms, and statistical physics : DIMACS Workshop Graphs, Morphisms and Statistical Physics, March 19-21, 2001, DIMACS Center / J. ...

cims.nyu.edu/ library/ newbook/ 051404.html

The restrictive <i>H</i>-coloring problem

The restrictive H-coloring problem. Source, Discrete Applied Mathematics archive Volume 145 , Issue 2 (January 2005) table of contents ...

portal.acm.org/ citation.cfm?id=1056120&

Discrete Mathematics : List homomorphisms of graphs with bounded **...**

Quick Search, Title, abstract, keywords, Author, eg js smith. Search tips (Opens new window), Journal/book title, Volume, Issue, Page, Clear all fields ...

linkinghub.elsevier.com/ retrieve/ pii/ S0012365X06005188

Graphs, morphisms, and statistical physics: - / 2004 - Livros

Título Principal, Graphs, morphisms, and statistical physics : DIMACS Workshop Graphs, Morphisms and Statistical Physics, March 19-21, 2001, DIMACS Center ...

volterra.impa.br/ arquivos/ 30000/ 31100/ 105_31141.htm

新書通告

2, Graphs, morphisms, and statistical physics: DIMACS Workshop Graphs, Morphisms and Statistical Physics, March 19-21, 2001, DIMACS Center, J. Nesetril, ...

www.math.sinica.edu.tw/ library/ pre_newbk/ 0504_2.htm

List of Publications

2005. Grad and Classes with Bounded Expansion I. Decompositions [PS file] (J. Nesetril, P. Ossona de Mendez) KAM-DIMATIA Series (2005), no. ...

kam.mff.cuni.cz/ ~nesetril/ src/ biblio.html

Correlation decay and deterministic FPTAS for counting list **...**

Correlation decay and deterministic FPTAS for counting list-colorings of a. graph. David Gamarnik. ∗. Dmitriy Katz. †. Abstract ...

portal.acm.org/ ft_gateway.cfm?id=1283517&

LNCS 3221 - Fixed Parameter Algorithms for Counting and Deciding **...**

Fixed Parameter Algorithms for Counting and. Deciding Bounded Restrictive List H-Colorings. ⋆. (Extended Abstract). Josep Dıaz, Maria Serna, and Dimitrios ...

www.springerlink.com/ index/ r3yhhxt90kmma9ty.pdf