Graphs, Morphisms, and Statistical Physics: DIMACS Workshop Graphs, Morphisms and Statistical Physics, March 19-21, 2001, DIMACS Center

Front Cover
Jaroslav Nešetřil, Peter Winkler
American Mathematical Soc. - Science - 193 pages
0 Reviews
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.
  

What people are saying - Write a review

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

Selected pages

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
Copyright

Common terms and phrases

Popular passages

Page 85 - P. Hell, J. Nesetfil, and X. Zhu, Duality and polynomial testing of tree homomorphisms, Trans. Amer. Math. Soc.
Page 84 - T. Feder, P. Hell, and J. Huang, List homomorphisms and circular arc graphs, Combinatorica, 19 (1999), 487-505.

Bibliographic information