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:
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.
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).
BIRTH OF EQUILIBRIUM DROPLET
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.
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.