Personal tools
You are here: Home Events Abstract Archives 2006-2007 Approximating the Tutte polynomial: a status report

Approximating the Tutte polynomial: a status report

Mark Jerrum University of Edinburgh 4pm Tuesday 25th April 2006 Room 2511, JCMB, King's Buildings

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).

Document Actions