A Little Statistical Mechanics for the Graph Theorist

Abstract

In this survey, we give a friendly introduction from a graph theory perspective to the q-state Potts model, an important statistical mechanics tool for analyzing complex systems in which nearest neighbor interactions determine the aggregate behavior of the system. We present the surprising equivalence of the Potts model partition function and one of the most renowned graph invariants, the Tutte polynomial, a relationship that has resulted in a remarkable synergy between the two fields of study. We highlight some of these interconnections, such as computational complexity results that have alternated between the two fields. The Potts model captures the effect of temperature on the system and plays an important role in the study of thermodynamic phase transitions. We discuss the equivalence of the chromatic polynomial and the zero-temperature antiferromagnetic partition function, and how this has led to the study of the complex zeros of these functions. We also briefly describe Monte Carlo simulations commonly used for Potts model analysis of complex systems. The Potts model has applications as widely varied as magnetism, tumor migration, foam behaviors, and social demographics, and we provide a sampling of these that also demonstrates some variations of the Potts model. We conclude with some current areas of investigation that emphasize graph theoretic approaches. This paper is an elementary general audience survey, intended to popularize the area and provide an accessible first point of entry for further exploration.

30 pages, 3 figures

References in corpus (15)

• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• Inapproximability of the Tutte polynomial
• Potts-like model for ghetto formation in multi-cultural societies
• Complex zero-free regions at large |q| for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights
• Phase diagram of the chromatic polynomial on a torus
• The Brown-Colbourn conjecture on zeros of reliability polynomials is false
• New critical frontiers for the Potts and percolation models
• Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. IV. Chromatic polynomial with cyclic boundary conditions
• Critical speeding-up in a local dynamics for the random-cluster model
• Dynamic critical behavior of the Chayes-Machta-Swendsen-Wang algorithm
• Complex-temperature phase diagram of Potts and RSOS models
• Viscous instabilities in flowing foams: A Cellular Potts Model approach
• Planar triangulations with real chromatic roots arbitrarily close to four
• Partition Function Zeros of a Restricted Potts Model on Lattice Strips and Effects of Boundary Conditions
• Regions without complex zeros for chromatic polynomials on graphs with bounded degree

Cited by in corpus (18)

• On the uniqueness of Gibbs measure in the Potts model on a Cayley tree with external field
• $q$-Plane Zeros of the Potts Partition Function on Diamond Hierarchical Graphs
• Gibbs measures of Potts model on Cayley trees: a survey and applications
• The Tutte-Potts connection in the presence of an external magnetic field
• From Network Reliability to the Ising Model: A Parallel Scheme for Estimating the Joint Density of States
• Graph polynomials and their applications II: Interrelations and interpretations
• Functional Relations on Anisotropic Potts Models: from Biggs Formula to the Tetrahedron Equation
• Some Exact Results on the Potts Model Partition Function in a Magnetic Field
• A motivic approach to phase transitions in Potts models
• Exact Results on Potts Model Partition Functions in a Generalized External Field and Weighted-Set Graph Colorings
• Phase diagrams of lattice models on Cayley tree and chandelier network: a review
• Asymptotic Behavior of Acyclic and Cyclic Orientations of Directed Lattice Graphs
• On the Potts model partition function in an external field
• Asymptotic Behavior of Spanning Forests and Connected Spanning Subgraphs on Two-Dimensional Lattices
• A note on recognizing an old friend in a new place: list coloring and the zero-temperature Potts model
• Potts Partition Function Zeros and Ground State Entropy on Hanoi Graphs
• The birth of the contradictory component in random 2-SAT
• Exact Potts/Tutte Polynomials for Hammock Chain Graphs