New Titles  |  FAQ  |  Keep Informed  |  Review Cart  |  Contact Us Quick Search (Advanced Search ) Browse by Subject General Interest Logic & Foundations Number Theory Algebra & Algebraic Geometry Discrete Math & Combinatorics Analysis Differential Equations Geometry & Topology Probability & Statistics Applications Mathematical Physics Math Education

Graphs, Morphisms and Statistical Physics
Edited by: J. Nešetřil, Charles University, Praha, Czech Republic, and P. Winkler, Bell Labs, Murray Hill, NJ
A co-publication of the AMS and DIMACS.
 SEARCH THIS BOOK:
DIMACS: Series in Discrete Mathematics and Theoretical Computer Science
2004; 193 pp; hardcover
Volume: 63
ISBN-10: 0-8218-3551-3
ISBN-13: 978-0-8218-3551-7
List Price: US$92 Member Price: US$73.60
Order Code: DIMACS/63

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

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

• S. Boettcher -- Efficient local search near phase transitions in combinatorial optimization
• C. Borgs, J. T. Chayes, M. Dyer, and P. Tetali -- On the sampling problem for $$H$$-colorings on the hypercubic lattice
• G. R. Brightwell and P. Winkler -- Graph homomorphisms and long range action
• A. Daneshgar and H. Hajiabolhassan -- Random walks and graph homomorphisms
• J. Díaz, M. Serna, and D. M. Thilikos -- Recent results on parameterized $$H$$-colorings
• M. Dyer, M. Jerrum, and E. Vigoda -- Rapidly mixing Markov chains for dismantleable constraint graphs
• D. Galvin and P. Tetali -- On weighted graph homomorphisms
• P. Hell and J. Nešetřil -- Counting list homomorphisms for graphs with bounded degrees
• G. Istrate -- On the satisfiability of random $$k$$-horn formulae
• J. Katriel -- The exchange interaction, spin hamiltonians, and the symmetric group
• M. Loebl -- A discrete non-Pfaffian approach to the Ising problem
• E. Mossel -- Survey: Information flow on trees
• C. Tardif -- Chromatic numbers of products of tournaments: Fractional aspects of Hedetniemi's conjecture
• X. Zhu -- Perfect graphs for generalized colouring-circular perfect graphs