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

Abstract

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.

LaTex2e, 54 pages. Invited survey paper, to be presented at the 2005 British Combinatorial Conference

References in corpus (4)

• Uniform random spanning trees
• Dimensional Reduction and Crossover to Mean-Field Behavior for Branched Polymers
• Dimensional Reduction for Directed Branched Polymers
• Rank three matroids are Rayleigh

Cited by in corpus (108)

• Topological Graph Polynomials in Colored Group Field Theory
• Approximating the partition function of the ferromagnetic Potts model
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Renormalization: an advanced overview
• Trading inverses for an irrep in the Solovay-Kitaev theorem
• The multivariate signed Bollobas-Riordan polynomial
• A Little Statistical Mechanics for the Graph Theorist
• The Lee-Yang and Pólya-Schur Programs. II. Theory of Stable Polynomials and Applications
• Factor models on locally tree-like graphs
• Generalization of the Bollobás-Riordan polynomial for tensor graphs
• Knot invariants and the Bollobas-Riordan polynomial of embedded graphs
• Interlace Polynomials for Multimatroids and Delta-Matroids
• 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
• Quantum algorithms for classical lattice models
• Critical manifold of the kagome-lattice Potts model
• Grassmann Integral Representation for Spanning Hyperforests
• Inapproximability of the Tutte polynomial of a planar graph
• Tree formulas, mean first passage times and Kemeny's constant of a Markov chain
• Unsigned state models for the Jones polynomial
• A new Kempe invariant and the (non)-ergodicity of the Wang-Swendsen-Kotecky algorithm
• Rectangular amplitudes, conformal blocks, and applications to loop models
• Multiple and inverse topplings in the Abelian Sandpile Model
• On the non-ergodicity of the Swendsen-Wang-Kotecky algorithm on the kagome lattice
• Explicit characterization of the identity configuration in an Abelian Sandpile Model
• Completeness of classical spin models and universal quantum computation
• Binary matroids and local complementation
• Complete monotonicity for inverse powers of some combinatorially defined polynomials
• Extremes of the internal energy of the Potts model on cubic graphs
• Expansions for the Bollobas-Riordan polynomial of separable ribbon graphs
• Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials
• The Ground State Energy of The Massless Spin-Boson Model
• $G$-Tutte polynomials and abelian Lie group arrangements
• Cumulants of the q-semicircular law, Tutte polynomials, and heaps
• Some combinatorial aspects of quantum field theory
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. VI. Square lattice with special boundary conditions
• Correlation decay and partition function zeros: Algorithms and phase transitions
• High-temperature series expansions for the $q$-state Potts model on a hypercubic lattice and critical properties of percolation
• Computing the Tutte Polynomial of Lattice Path Matroids Using Determinantal Circuits
• Functional Relations on Anisotropic Potts Models: from Biggs Formula to the Tetrahedron Equation
• Exact solutions for the two- and all-terminal reliabilities of a simple ladder network
• Exponential Time Complexity of Weighted Counting of Independent Sets
• A motivic approach to phase transitions in Potts models
• What is the probability of connecting two points ?
• Beyond Log-Supermodularity: Lower Bounds and the Bethe Partition Function
• Arrow ribbon graphs
• Central limit theorems, Lee-Yang zeros, and graph-counting polynomials
• Hyperbolicity and stable polynomials in combinatorics and probability
• Linear bound in terms of maxmaxflow for the chromatic roots of series-parallel graphs
• Ported Tutte Functions of Extensors and Oriented Matroids
• The Exponential Time Complexity of Computing the Probability That a Graph is Connected
• Spanning Forests on Random Planar Lattices
• Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs
• Some variants of the exponential formula, with application to the multivariate Tutte polynomial (alias Potts model)
• Spin Glass Models of Syntax and Language Evolution
• Exact solutions for the two- and all-terminal reliabilities of the Brecht-Colbourn ladder and the generalized fan
• Using graphs to find the best block designs
• Quantum computation and the evaluation of tensor networks
• Fourientation activities and the Tutte polynomial
• Geometric representations of linear codes
• Hyperforests on the Complete Hypergraph by Grassmann Integral Representation
• Negatively correlated random variables and Mason's conjecture
• On the Potts model partition function in an external field
• Tetromino tilings and the Tutte polynomial
• A most general edge elimination graph polynomial
• On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
• A Most General Edge Elimination Polynomial - Thickening of Edges
• Properties of the corolla polynomial of a 3-regular graph
• Topological Tutte Polynomial
• Answering Two OPAC Problems Involving Banff Quivers
• Fast Super-Paramagnetic Clustering
• Postnikov-Shapiro Algebras, Graphical Matroids and their generalizations
• Parallel family trees for transfer matrices in the Potts model
• Graph Polynomials: From Recursive Definitions To Subset Expansion Formulas
• A note on recognizing an old friend in a new place: list coloring and the zero-temperature Potts model
• Proving properties of the edge elimination polynomial using equivalent graph polynomials
• Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs
• Generalized duality for graphs on surfaces and the signed Bollobas-Riordan polynomial
• On the Activities and Partitions of the Vertex Subsets of Graphs
• Negative dependence and the geometry of polynomials
• Recipe theorems for polynomial invariants on ribbon graphs with half-edges
• Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite $\Delta$-regular tree for large $\Delta$
• Density of Zeros of the Tutte Polynomial
• Multi-core computation of transfer matrices for strip lattices in the Potts model
• The covered components polynomial: A new representation of the edge elimination polynomial
• How proofs are prepared at Camelot
• Oblique projections on metric spaces
• A multidimensional generalization of Symanzik polynomials
• The blowup-polynomial of a metric space: connections to stable polynomials, graphs and their distance spectra
• Galois groups of multivariate Tutte polynomials
• From spanning forests to edge subsets
• Abstract matrix-tree theorem
• On sequences of polynomials arising from graph invariants
• Computing the Tutte polynomial in vertex-exponential time
• Spanning forests on the Sierpinski gasket
• Potts models with magnetic field: arithmetic, geometry, and computation
• Around matrix-tree theorem
• Renormalization group-like proof of the universality of the Tutte polynomial for matroids
• On Multivariate Chromatic Polynomials of Hypergraphs and Hyperedge Elimination
• Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
• Torus orbits on homogeneous varieties and Kac polynomials of quivers
• Combinatorics and geometry of power ideals
• Convolution-multiplication identities for Tutte polynomials of matroids
• Multivariate blowup-polynomials of graphs
• Edge colouring models for the Tutte polynomial and related graph invariants
• More on Algebraic Structure of the Complete Partition Function for the $Z_n$ - Potts Model, Part 1
• System/environment duality of nonequilibrium observables
• Abstract matrix-tree theorem and Bernardi polynomial