Problem of the Week
Hilton Memorial Lecture
The Tutte polynomial of graph theory is equivalent to the q-state Potts-model partition function of statistical mechanics (when temperature and q are viewed as independent variables). Recent work (by, among many others, Sokal, who has done much to popularize the approach) has used a multivariable extension of the Potts-model partition function, physically corresponding to allowing interaction energies to vary. The Tutte polynomial was fully generalized, with independent parameters for each edge, by Zaslavsky and, from a different point of view, Bollobas and Riordan; their generalizations require care due to relations arising from three special small graphs.
In 1987, Jaeger introduced transition polynomials of 4-regular graphs to unify polynomials given by vertex reconfigurations very similar to the skein relations of knot theory. Transition polynomials include the Martin polynomial of a graph (restricted to 4-regular graphs), the Kauffman bracket of knot diagrams, and, for planar graphs via their medial graphs, the Penrose and classical Tutte polynomials.
I will discuss a generalized transition polynomial (developed jointly with Sarmiento) that extends the transition polynomial of Jaeger to arbitrary Eulerian graphs, and introduces pair weights that function analogously to the edge parameters in the generalized Tutte polynomial.
The generalized transition polynomial and the generalized Tutte polynomial (and hence the Potts-model partition function) are related for planar graphs in much the same way as are Jaeger's transition polynomial and the classic Tutte polynomial. Moreover, the generalized transition polynomials are Hopf algebra maps, so the comultiplication and antipode give recursive identities for generalized transition polynomials. A number of combinatorial identities arise from this and the relations among these polynomials. Because of the medial graph construction relating these polynomials, the identities are relevant to the self-dual lattices that are the 'natural' underlying graphs of statistical mechanics.