2005/03/25 by Alan D. Sokal · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Advanced Mathematical Theories and Applications #Chromatic polynomial #Combinatorics #Discrete mathematics #Graph #Graphic matroid #Line graph #Mathematical analysis #Mathematics #Matroid #Matroid partitioning #Partition function (quantum field theory) #Phase transition #Physics #Polynomial #Potts model #Quantum mechanics #Spanning tree #Theoretical and Computational Physics #Topological and Geometric Data Analysis #Tutte polynomial #Voltage graph #cond-mat.stat-mech #math-ph #math.CO #math.MP #msc:05B35 #msc:05C99 #msc:82B20 #msc:94C15
paper · pdf · doi:10.1017/cbo9780511734885.009
published as Published in "Surveys in Combinatorics, 2005", edited by Bridget S. Webb (Cambridge University Press, 2005), pp. 173-226 · LaTex2e, 54 pages. Invited survey paper, to be presented at the 2005 British Combinatorial Conference
arxiv created 2005/03/25 · openalex publication_date 2005/07/21 · arxiv updated 2021/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.