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 …

Posted in events | Tagged , , , | Leave a comment

BCC, day 5

My route to the conference passes a stagnant ditch. Today, two families of moorhens were in evidence; a couple with two small chicks, and another group of three older chicks. Blackbirds are also busy foraging on the lawn outside the window at breakfast.

The day began with a really beautiful talk by Gary McGuire, who is (among other things) the person responsible for showing that there are no 16-clue Sudokus. He talked about plane curves over finite fields and the connection with linear recurrent sequences. There was a lot of algebraic geometry just below the surface, and the names of Weil and Serre, Jacobians, and Picard groups were invoked from time to time; but everything was remarkably clear. His computations of zeta-functions of plane curves have revealed some amazing patterns, some of which can be proved. The zeta-function of a plane curve over the field of q elements has the form L(t)/(1−t)(1−qt), and he is interested in when the L-polynomial of one curve divides that of another. If the quotient is a polynomial in tk, then the numbers of points on the two curves are equal over extensions with degree not divisible by k. Since the generating function for the difference between the number of points over an extension of degree n and the “expected” number 1+qn is rational, this series satisfies a linear recurrence, which has stronger properties than are immediately apparent.

After coffee, my freedom was restricted by the fact that I had to chair a session, but the talks in the session were all things I wanted to hear anyway. David Penman counted linear extensions of posets, being interested in the maximum and minimum numbers possible for given numbers of comparabilities in the poset; Joanna Fawcett described locally triangular graphs with a sufficient amount of symmetry; Mark Ellingham was extending Whitney’s results on line graphs to “link graphs”, and needed ideas from topological graph theory to do it; and Anurag Bishnoi presented a remarkably general technique relating putting balls in boxes to geometric problems of Chevalley–Warning type including Jamison’s result on blocking sets in the affine plane.

We had lunch, and then went our separate ways.

Posted in events | Tagged , , | 1 Comment

BCC, day 4

The highlight of the conference for me was the talk this afternoon by Manuel Bodirsky, on Ramsey classes.

No time now to explain all this – get the invited speakers’ volume and read it if you want to know – but let me just say one thing. This is a subject I thought I knew quite well, but Manuel answered one question that had puzzled me.

One of the earliest results about Ramsey classes of relational structures was that the structures in such a class must be rigid (have no non-trivial automorphisms). The usual way this is achieved is to assume that one of the relations is a total order, since finite total orders are rigid. But there are other ways to make structures rigid. For example,

  • a finite C-relation derived from a binary tree has the property that its automorphism group is a 2-group;
  • a tournament has the property that its automorphism group has odd order.

So, if we impose both of these relations, our structures will be rigid. Why cannot Ramsey classes be made this way?

The answer, it turns out, comes from the Kechris–Pestov–Todorcevic theorem, which asserts that a homogeneous structure has automorphism group which is extremely amenable (that is, every continuous action on a compact Hausdorff space has a fixed point) if and only if the amalgamation class of its finite substructures is a Ramsey class. This theorem is usually applied to known Ramsey classes to provide examples of extremely amenable groups. But here we use the KPT theorem the other way round.

Suppose that the age of a countable homogeneous structure M is a Ramsey class. Then the automorphism group of M is extremely amenable. Consider the “logic action” of Aut(M) on the set of all linear orders of the ground set. This is easily seen to be a continuous action on a compact Hausdorff space. So, since the group is extremely amenable by the KPT theorem, it must fix a linear order!

Out of the rest of the day, let me just pick out the talk by Terry Griggs on the combinatorics of the sonnet. A sonnet is a 14-line poem, invented in Italy but taken up by English (and Scottish) poets. Terry wanted to count the number of rhyme schemes possible in a sonnet, using the rules laid down in the Oxford Companion to English Literature. A sonnet is made up of an octave of 8 lines followed by a sestet of 6 lines. Various forms of rhyme scheme were used by Petrarch, Shakespeare, Spenser, and others. The common denominator seems to be that the octave is divided into two quatrains each of which contains two pairs of rhymes (three possibilities for each), while the sestet should have two or three rhymes. We can assume that the sestet splits as 2+2+2 or 3+3, since 2+4 is a specialisation of 2+2+2; so there are 15+10=25 possible rhyme schemes, for a total of 3×3×25 = 225 altogether.

Terry then looked at one of his favourite poets, John Clare, who actually broke the rules quite dramatically.

I once constructed a Petrarchian sonnet, out of first lines of sonnets by more famous poets, which you can find here.

Then Terry looked at the specialisation of 2+2+2 to 2+4, and considered the graph whose vertices are the patterns of either shape, joined if the second is a specialisation of the first. This bipartite graph is Tutte’s 8-cage, otherwise known as the generalized quadrangle of order 2, which is related to the outer automorphism of S6.

Then he generalised this pattern to see whether the graph obtained similarly from rhyme schemes with n rhymes each occurring r times, and the specialisation when two of the rhymes are equal, can be regular. Regularity is equivalent to the diophantine equation

n(n−1) = (2r)!/(r!)2.

Terry remarked that this equation has three known solutions apart from the trivial n = 2, r = 1: there is one with n = 3, r = 2 (corresponding to Tutte’s cage); one with n = 5, r = 3; and one with n = 221, r = 9. The graph corresponding to the last solution has rather a large number of vertices and has not been investigated.

Terry ended by remarking that the finiteness of the set of solutions of the diophantine equation might follow from a proof of the ABC conjecture, though this has not been demonstrated, and Terry is reluctant to try until the status of the conjecture becomes clearer. (This is one of the really big open problems in number theory, implying among other things Fermat’s last theorem.)

We had a second problem session, followed by an enjoyable dinner.

Posted in events | Tagged , , , , , , , , , | Leave a comment

BCC, day 3

Further to my comment about non-communication betweem group theory and combinatorics yesterday, the table labelled “Maths” at breakfast this morning was for group theorists, while combinatorialists were somewhere else …

The format of this BCC is a little different from usual. We finish at lunchtime on Friday instead of continuing in the afternoon. This means that an extra slot has to be found for one of the nine plenary speakers, who might otherwise have spoken on Friday afternoon. The solution was to have no contributed talks on Wednesday morning, but instead to have two plenaries and then an early lunch before the outing to Warwick castle.

The two talks this morning went together remarkably well. First, Nik Ruškuc (my boss for the next 23 days) talked about well quasi-orders in combinatorics, starting with Higman’s theorem. He showed us some brief extracts from Higman’s paper, including the statement that in the author’s opinion it was the range of applications rather than the depth of the proofs that made the topic interesting. Nik took us through various kinds of structure (words, permutations, trees, graphs, posets) and various notions of inclusion (subword/subgraph, induced subgraph, minor), describing when the WQO property is true and a sketch of what it buys you if it does hold. For a small example, words over a finite alphabet are well-quasi-ordered by the (not necessarily contiguous) subword relation; a consequence is that any ideal is a regular language (so that there is a finite automaton which recognises it) and hence the generating function for the ideal is a rational function. It would be very interesting if anything like this could be said for other instances of WQO.

He was followed by Sergey Norin, talking about a very specific example of a WQO class, graphs ordered by the minor relation (this, of course, is the content of the famous theorem of Robertson and Seymour). For this class, the results are more detailed, and there is much new material. Much effort has gone into Hadwiger’s conjecture, according to which a graph not having the complete graph on t+1 vertices as a minor can be coloured with t colours. It is known that a proper minor-closed class of graphs has the property that the number of edges of a graph in the class is bounded by a linear function of the number of vertices; so the graph has an invariant d, the “density”, which is the lim sup of the ratio of edges to vertices over the class. The set of densities of proper minor-closed classes is closed, well-ordered (and hence nowhere dense), and is contained in the set of rational numbers (the last fact a very recent theorem of Kapadia and Norin). On this last result, he posed a fascinating question: can the rationality of densities be proved in Peano arithmetic? (This is non-trivial if, as seems reasonable to me, the Robertson–Seymour theorem cannot.)

I skipped the excursion, and spent several hours without completely getting up to date with my email (I fell very far behind when my computer was down); then we had a committee meeting, which finished in time to have a drink with the group theorists before bedtime.

Posted in events | Tagged , , | Leave a comment

BCC, day 2

There was a London Mathematical Society regional meeting in the University of Warwick today, to be followed by a workshop on finite simple groups to celebrate the birthday of Richard Lyons, one of the pioneers and heroes of the Classification.

Unfortunately, there had been almost no communication between the group theorists and the combinatorialists.

As a result, we had the ludicrous situation this afternoon that, while Tomasz Łuczak was talking, on the ground floor of the Mathematics building, about “Randomly generated groups”, Robert Guralnick was talking, on the third floor of the same building, about “Applications of the classification of finite simple groups”, followed by Colva Roney-Dougal on “Generation of finite groups”.

I sneaked away from the BCC to hear Colva’s talk; indeed part of what she was talking about was joint work we have done recently, which I will write about here at some point.

Other things that went on included the following.

Stefanie Gerke, in her talk, mentioned a fact which sociologists of science might like to consider. The high-status journal Nature published a paper in which an incorrect result was proved by a heuristic argument and checked by extensive simulation (but all the simulations they chose had a special feature). Do you think that Nature would feel any obligation to publish a mathematical proof of the correct result?

Interesting fact of the day: it is known that an automorphism of a group of order n must have order smaller than n. This turns out to be false for quasigroups; Ian Wanless announced that the smallest counterexample has order 7034, a remarkable fact I think. He conjectures that the order of the largest automorphism of a quasigroup of order n is not bounded by a linear function of n.

The day ended with the conference business meeting, where we narrowly avoided having what might have been the first contested election in the history of the BCC. In the evening we had the Conference concert.

Posted in events | Tagged , , , , , , , , | Leave a comment

BCC, day 1

So here I am on the campus of the University of Warwick, at the end of the first day of the 25th British Combinatorial Conference.

Two things struck me right away. First, I really do feel that this is my extended family; I have so many good friends here. And on the other hand, it is a conference at which I never really feel off duty. As well as my constitutional jobs of chairing the conference business meeting and (if they re-elect me) the committee meeting, I have by tradition the job of running the problem sessions (we are having two at this meeting), doing a turn at the conference concert, making a speech at the dinner (if I don’t succeed in avoiding this), and various announcements.

Anyway, today I only had my talk, the first problem session, and a short announcement. Oh, and there was a piece of business which the committee had collectively forgotten; a completely unrelated remark at the reception threw a switch in my brain, and I had to go around the reception sorting it out.

Apart from all that, a very good collection of talks. Since I am rather busy, I will be brief, and simply report a small gem from Gil Kalai’s talk.

This concerns Buffon’s needle: if we throw a needle of unit length randomly onto a floor with parallel lines one unit apart, what is the probability that the needle crosses a line? Here is the solution, as Gil described it.

  • First, we can replace “probability it crosses a line” by “expected number of lines crossed”, since the probability of crossing a number of lines different from 0 or 1 is zero.
  • Next, we replace “Buffon’s needle” by “Buffon’s noodle”, a wiggly (but smooth) line of length l. (For technical reasons it is better to replace it first by a polygonal arc, and then extend the results to smooth curves by a limiting process.)
  • By concatenating two noodles of lengths l1 and l2, and using the linearity of expectation, we see that the expected number of lines crossed is a linear function of the length, say cl for some constant c; our job is to find c.
  • Now consider the case where the noodle is a circle of diameter 1 (and so length π). The expected number of lines crossed in this case is clearly 2; so the constant c is equal to 2/π.
  • So in the original needle problem, the answer is 2/π.

A final remark. When I arrived at my accommodation, I was given a leaflet about connecting to Warwick guest wi-fi, which implied that without a mobile phone it was impossible to connect. The fact that you are reading this now might suggest that I have succumbed and got a phone; but in fact the answer is simpler, they have eduroam, which works perfectly (although, after my computer went down, eduroam was the very last thing I managed to restore). So I am still a dinosaur!

Posted in events | Tagged , | Leave a comment

An LMS meeting

Last Friday I went to the London Mathematical Society general meeting, at the BMA building in Tavistock Square. On a beautiful warm day I walked along the Regents Canal to Islington and then down through back streets past the former end of the New River, to the cool and impressive BMA building.

As the President, Terry Lyons, said, the official business of the meeting was pleasant: apart from admitting new members and giving people the opportunity to sign the book, it consisted in the announcement of prizes and honorary memberships. There was a longer list than usual of the latter, to commemorate the sesquicentenary of the society; and an impressive list it was too: Joan Birman, Robert Calderbank, Shafi Goldwasser, Donald Knuth, Robert Langlands, and Maryam Mirzakhani.

I was also delighted that the Hirst Prize was awarded to my colleagues John O’Connor and Edmund Robertson, for their wonderful history of mathematics website.

As usual, the real business was the two lectures; the second was the final performance of this year’s Hardy lecturer, Nalini Joshi, while the warm-up act was a talk by Marta Mazzocco.

Both lecturers spoke about Painlevé equations. These are non-linear second order differential equations, which I don’t know anything about. There are six Painlevé equations, numbered PI to PVI, with varying numbers of parameters from zero to four; I believe that in some sense they cover all cases. But the two talks were concerned to connect the Painlevé equations to things that I do claim to know something about: cluster algebras, and root lattices. Each speaker assumed (I think) that we know a bit about Painlevé equations but less about the other topics, and so spent more time on the things I knew a bit about – not that I minded!

But this means that my account of the lectures is going to be very sketchy.

Marta Mazzocco introduced cluster algebras by way of Pythagoras’ theorem, a2+b2 = c2. Slightly reinterpreted, this says that a rectangle which has one pair of opposite sides a and the other pair b, then the diagonals are c. In this form it generalises to arbitrary cyclic quadrangles: if one pair of opposite sides are a and a‘, and the other pair b and b‘, and the diagonals c and c‘, then aa‘+bb‘ = cc‘ (this is Ptolemy’s Theorem).

Now this equation defines the mutation rule for a cluster algebra. Clusters are triples of numbers; if we use the mutation rule x1x1‘ = x22+x32, we obtain an infinite cluster algebra. If we start with (1,1,1), then all the clusters satisfy the equation x12+x22+x32 = 0. This procedure generates the Markov numbers, the solutions of this equation in natural numbers. (The fact that they are all integral is a consequence of the famous Laurent phenomenon for cluster algebras.)

Now this account disappears into the stratosphere. This example, generating the Markov numbers, is related to the “quantum cohomology” solution to PVI. There is a representation on the punctured Riemann sphere, where the punctures become cusps; the surface can be triangulated by geodesics starting and ending in cusps, and everything can be expressed combinatorially in terms of the orders of the geodesics at each cusp.

Nalini Joshi saw her job as building a bridge between different areas, and illustrated her talk with pictures of the building of an icon of her home town, the Sydney Harbour Bridge.

She started out with the A2 root system, the vertices of a regular hexagon centred at the origin. If we divide it into six triangles, then the reflections in the sides of a fundamental triangle cover the plane with copies of this triangle; we can regard the structure as the root lattice (it is closed under translation) or the corresponding affine root system.

Choose coordinates of a point in the fundamental triangle which are its perpendicular distances from the two sides. These coordinates have constant sum (which can be assumed to be 1). They extend, allowing negative values, to the whole plane; the reflections, translations, and rotations of the fundamental triangle have simple expressions in these coordinates. However, in terms of “Cremona isometries”, something much more complicated occurs. We get a non-linear discrete dynamical system, which is non-autonomous (the time parameter n appears explicitly in the transformation formulae), and is described by a certain discretisation of a Painlevé equation!

All this holds too for other types of root system satisfying the crystallographic condition (not G2 as yet, apparently). There are relations between root systems and the corresponding Painlevé equations, which were worked out by Sakai. The simplest example, in root system terms, is a map from B3 to A2, which is easily described: look at a cube (the B3 system) along a diagonal; what you see is a hexagon (the A2 system).

There is also a duality which I didn’t quite catch, which interchanges large and small, so that the A2 system is replaced by E6. This is related to the McKay correspondence.

There was a lot more too. For example, take functions of four variables which are satisfied by the vertices of a square. Fit these together on the square faces of a cube or hypercube; this leads to an obvious consistency condition, which yields only a few solutions, one related to elliptic curves. They also discovered a case missed by Sakai, involving the root system F4.

That is the limit of what I can say. But I hope that I have communicated some of the pleasure I took from the occasion.

Posted in events | Tagged , , , , , , | Leave a comment