Chromatic Polynomials, Potts Models and All That
arXiv:cond-mat/9910503 · doi:10.1016/S0378-4371(99)00519-1
Abstract
The q-state Potts model can be defined on an arbitrary finite graph, and its partition function encodes much important information about that graph, including its chromatic polynomial, flow polynomial and reliability polynomial. The complex zeros of the Potts partition function are of interest both to statistical mechanicians and to combinatorists. I give a pedagogical introduction to all these problems, and then sketch two recent results: (a) Construction of a countable family of planar graphs whose chromatic zeros are dense in the whole complex q-plane except possibly for the disc |q-1| < 1. (b) Proof of a universal upper bound on the q-plane zeros of the chromatic polynomial (or antiferromagnetic Potts-model partition function) in terms of the graph's maximum degree.
10 pages (LaTeX). 3 style files included (eqsection.sty, indent.sty, subeqnarray.sty)
References in corpus (1)
Cited by in corpus (19)
- A Little Statistical Mechanics for the Graph Theorist
- On the chromatic roots of generalized theta graphs
- First-Order Phase Transition in Potts Models with finite-range interactions
- Graph polynomials and their applications II: Interrelations and interpretations
- Low-temperature universal dynamics of the bidimensional Potts model in the large q limit
- Yang-Lee zeros and the critical behavior of the infinite-range two- and three-state Potts models
- The phase diagram for the bisected-hexagonal-lattice five-state Potts antiferromagnet
- Planar triangulations with real chromatic roots arbitrarily close to four
- Anomalous scaling and Lee-Yang zeroes in Self-Organized Criticality
- Complex-q zeros of the partition function of the Potts model with long-range interactions
- Metastability in the Potts model: exact results in the large q limit
- Chromatic polynomials of random graphs
- Chaotic size dependence in the Ising model with random boundary conditions
- Counting Complex Disordered States by Efficient Pattern Matching: Chromatic Polynomials and Potts Partition Functions
- Approximating the Chromatic Polynomial
- Sampling 3-colourings of regular bipartite graphs
- A set of chromatic roots which is dense in the complex plane and closed under multiplication by positive integers
- On the Reliability Roots of Simplicial Complexes and Matroids
- Relating counting complexity to non-uniform probability measures