OWL Meeting 2006


Oxford-Warwick-London (OWL) Meeting 2006

You are invited to an afternoon meeting on "Combinatorics, probability and statistical mechanics" to be held at the University of Oxford on Tuesday, 7 February 2006. The schedule is as follows:

2.00 - 3.00: Alan Sokal (NYU and UCL) The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
3.00 - 4.00: Mark Jerrum (Edinburgh) Approximating the Tutte polynomial: a status report
4.00 - 5.00: Tea
5.00 - 6.00: Roman Kotecky (Warwick and Prague) Birth of equilibrium droplet

The first two talks will take place in the Mathematical Institute. The third talk will be nearby in the Department of Statistics. Here are instructions on getting to the Mathematical Institute.

All are welcome, and we can provide some financial support for students to attend. Students wanting to claim support should bring travel receipts.

For further information, please contact Alex Scott.

This event is part of a Oxford-Warwick-London Series supported by the London Mathematical Society and the British Combinatorial Committee. Other meetings in the series are

QMUL OWL meeting on Friday, 12 November 2005
Warwick OWL meeting on Wednesday, 3 May 2006


Mark Jerrum (Edinburgh)

Approximating the Tutte polynomial: a status report

The (classical) Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes much information about G. The number of spanning trees in G, the number of acyclic orientations of G and the partition function of the q-state Potts model are all specialisations of the Tutte polynomial. From a complexity-theoretic point of view, "mapping the Tutte plane" amounts to determining the computational complexity of evaluating T(G;x,y), given G, for each rational pair (x,y). For exact computation, the mapping was done in detail by Jaeger, Vertigan and Welsh. For approximate computation (within specified relative error) much less was known. Some progress has recently been made, but there is still a good deal of terra incognita. The later stages of the talk will touch on joint work with Leslie Goldberg (Warwick).

Roman Kotecky (Warwick and Prague)


Large deviations for Ising model in the phase coexistence region are discussed. The typical behaviour, inside the coexistence region and far from its edge, is governed by droplet configurations. However, a new type of transition is experienced close to the edge of the coexistence. It stems from the competition between droplet contributions and supersaturated phase and leads to an abrupt occurrence of a droplet. Its proof needs a careful evaluation of typical configurations in different regimes. Main results will be explained and some idea of the proofs will be given.

The talk is based on joint papers with Marek Biskup and Lincoln Chayes as well as a recent work with Ostap Hryniv and Dima Ioffe.

Alan Sokal (NYU and UCL)

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

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.