The multivariate Tutte polynomial (alias Potts model) for graphs and matroids

By Alan D. Sokal. BCC, 2005

348 citations recorded by the source corpus.

The multivariate Tutte polynomial (known to physicists as the Potts-model partition function) can be defined on an arbitrary finite graph G, or more generally on an arbitrary matroid M, and encodes much important combinatorial information about the graph (indeed, in the matroid case it encodes the full structure of the matroid). It contains as a special case the familiar two-variable Tutte polynomial -- and therefore also its one-variable specializations such as the chromatic polynomial, the flow polynomial and the reliability polynomial -- but is considerably more flexible. I begin by giving an introduction to all these problems, stressing the advantages of working with the multivariate version. I then discuss some questions concerning the complex zeros of the multivariate Tutte polynomial, along with their physical interpretations in statistical mechanics (in connection with the Yang--Lee approach to phase transitions) and electrical circuit theory. Along the way I mention numerous open problems. This survey is intended to be understandable to mathematicians with no prior knowledge of physics.

Subfields: Computational Theory and Mathematics, Condensed Matter Physics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/35c7206eeb596f5782b3a64cce1aba074e7e6dc5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Condensed Matter Physics

In Statistical and Nonlinear Physics

Citations in the corpus

A Characterization of the Tutte Polynomial via Combinatorial Embeddings (2006, background): “Another problem where the embedding is explicitly given is the study of the Potts model on random lattices in statistical mechanics [1,2,7,10,22].”
Negative dependence and the geometry of polynomials (2007, background): “Using the inclusion-exclusion principle one can show that any such characteristic function may be written as a multi-affine polynomial in X1, . . . , Xn.”
Twisted duality for embedded graphs (2009, background): “The generalization is in the spirit of the extensions of the Tutte polynomial to edge weighted graphs from [88], [8] and [75].”
The multivariate arithmetic Tutte polynomial (2012, background): “This is a bivariate polynomial, such that several geometric, algebraic or combinatorial invariants appear as its specialization, for instance: • the characteristic polynomial of the toric arrangement T (L).”
The Lee-Yang and Pólya-Schur programs. I. Linear operators preserving stability (2008, background): “under linear transformations are central topics in geometric function theory which in recent years has found applications in statistical mechanics, combinatorics, probability theory and matrix theory [6, 8, 10, 11, 12, 13, 53]. For instance, as shown in [6, 13, 33], the Lee-Yang program on phase tra”
Hyperbolicity and stable polynomials in combinatorics and probability (2012, background): “The review paper [Sok05] surveys a number of “hard” results on zerofree regions, meaning results that give good estimates on zero-free regions that depend on specific parameters of the models or graphs from which the polynomial is formed.”