The Tutte polynomial

Royal Holloway

The Tutte polynomial is an important 2-variable polynomial associated with a matroid (and in particular, with a graph). I have been at a workshop on “New Directions for the Tutte Polynomial”, organised by Jo Ellis-Monaghan and Iain Moffatt, at Royal Holloway University of London.

It was a very successful workshop, with plenty of “collaboration time” built in; many new directions were described by the participants. I will try to say a bit about some of these.

Slides of talks will shortly be available on the conference website.

Constructions of the Tutte polynomial

There are two standard formulae for the Tutte polynomial, one as a generating function for ranks and cardinalities of subsets, the other (Tutte’s original definition) in terms of “internal and external activity” of bases. Probably its most important property is the recurrence relation for it based on deletion and contraction; this allows us to express any parameter satisfying a deletion-contraction recursion (such as the number of q-colourings of a graph, or the weight enumerator of a code) as a specialisation of the Tutte polynomial.

Here are some of the approaches that participants took.

  • Alex Fink gave two constructions, one involving the geometry of polytopes, the other algebraic geometry, involving a double fibration of a certain flag space. (Stephen Huggett pointed out that this double fibration, in a special case, is at the basis of twistor theory, as developed by Roger Penrose. One one side we have a Grassmannian, which (when comlexified and compactified) becomes Minkowski spacetime; on the other, a product of two projective spaces. A cohomology class on one of these spaces yields (by what is known as the Penrose transform) a solution to field equations such as Maxwell’s in spacetime.)
  • Stephen Huggett described his construction (with Michael Eastwood) of a sequence of manifolds from a graph; using the Leray spectral sequence, the Euler characteristics of these manifolds are evaluations of the chromatic polynomial at positive integers. He described his attempts, not so far successful, to extend this to the Tutte polynomial.
  • Matthias Lenz gave us a construction based on box splines, things which have their roots in approximation theory.
  • Julien Courtiel gave a very general definition of internal and external activity which extends both Tutte’s definition and several others which have been proposed.

Other polynomials

Various generalisations or related polynomials were presented, among them the following.

  • Ribbon graphs are an abstraction of graphs embedded in surfaces: edges are two-dimensional ribbons which may be twisted. The corresponding matroid notation is that of a delta-matroid. Following an introduction by Steve Noble, we heard several talks about these structures and their polynomials. In particular, Hendrik Hoogeboom and Robert Brijder took us from the DNA of ciliates (these organisms have two nuclei: in one of them the genes are in random order and sometimes reversed, in the other they are correctly arranged, and biologists are interested in how this trick is done) to the structure of delta-matroids.
  • Iain Moffatt gave a very general construction of the Tutte polynomial of a combinatorial Hopf algebra. His method has the feature that it explains why three different polynomials for graphs on surfaces have been proposed (the Las Vergnas, Bollobás–Riordan, and the Krushkal polynomials). These arise from three different conventions that could be adopted about contracting a loop; he illustrated by tightening his own belt.
  • Andrew Goodall gave us several instances of sequences (Gn) of graphs, where the number of homomorphisms from a given graph to Gn is the evaluation at n of a suitable graph polynomial. (Choosing the complete graphs gives the usual chromatic polynomial.)
  • I talked about orbit counting versions of the Tutte polynomial, where sometimes one needs two potentially infinite families of variables rather than just two variables. Unlike most other generalisations, there is no deletion-contraction available here, since these operations change the symmetry. (The student magazine, by the way, is called Orbital.)
  • Graham Farr took up another of Tutte’s themes, alternating dimaps, arising from dissections of triangles into triangles. Here there are three notions corresponding to deletion and contraction, and they don’t commute, which makes the theory much harder.
  • Alan Sokal was at the meeting. Although he didn’t give a talk, he encouraged many people to develop multivariate versions of their polynomials. But on the last day, he got more than he bargained for. Jo Ellis-Monaghan defined a new gadget called the V-polynomial, which (regarded as a generalisation of the Tutte polynomial) specialises to the list colouring polynomial, and (regarded as a generalisation of the Potts model partition function) allows arbitrary interactions and arbitrary (variable) external field!

Related topics

We had several talks on related issues.

  • James Oxley reminded us of the critical problem for matroids, in which a lot of very hard conjectures (including Hadwiger’s conjecture and Tutte’s 5-flow and tangential 2-block conjectures) lie hidden. He kept us awake by asking questions, encouraging audience response by rewarding correct answers with granola bars thrown with unerring accuracy.
  • Gordon Royle reported on progress with Steve Noble on the Merino–Welsh conjecture, which relates values of the Tutte polynomial at (0,2), (1,1), and (2,0). Seongmin Ok recorded further progress on this.
  • Joseph Kung introduced us to the G-invariant of a matroid, and the notion of a freedom matroid (homage to George W. Bush). The G-invariant records, for all orderings of the elements of the matroid, the positions where rank increases when the elements are added; in other language, the position of the lexicographically first basis in the ordering.
  • I am sure that this is connected to the topic of trellis decoding, a real-time decoding method assuming that the word received over a communication channel is analog (has real components), and is better than digitising it and decoding digitally. The method uses a directed network called a trellis. In brief, for binary codes, the trellis doubles in size at positions of the lexicographically first basis associated with the code, and halves at positions of the last basis; the tension between pushing the first basis late and the last basis early makes the problem interesting. Is there an analogue of the G-invariant which records both first and last basis? Does the Tutte polynomial encode information about the “average” trellis complexity of a code under all orderings?
  • Dong Fengming told us about zero-free regions for the flow polynomial of certain graphs. (This polynomial is a specialisation of the Tutte polynomial which is in some sense “dual” to the chromatic polynomial, though as I argued in my talk it is really dual to the tension polynomial.)

In conclusion

An extremely successful workshop. Joseph Kung told me that, early in his career, he had been advised not to work on such a minority subject as matroid theory. Hopefully, the subject is so well connected to the rest of mathematics that this couldn’t happen now!

Royal Holloway has a beautiful campus, rich in mature trees of many kinds, and is within walking distance of Windsor Great Park. The weather was mostly kind to us. The bedrooms were comfortable, much less cramped than those at Warwick. Lunch was provided outside the lecture room, except on Monday, when we were “bumped” by a graduation event.

Wi-fi provision was deficient. The conference information promised that eduroam would be available. It was on the wi-fi menu, but nobody I spoke to could connect to it. The conference network had been designed by people who think that the only way anyone accesses the internet is via a web browser; so ssh, Dropbox, and Thundebird were all disabled. So I was effectively out of communication for the entire meeting. To make things worse, I had forgotten to bring the power supply for my notebook, so was restricted to its five-hour battery life. I was glad to find that I didn’t find myself getting twitchy because I couldn’t check my email; it was a welcome break.

But apologies if you were waiting for a response from me …


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s