The Aitken lectures

Last Friday and this Monday we were visited by Geoff Whittle, the 2011 Aitken lecturer, sponsored by the London Mathematical Society.

It was good for me to go some small way towards repaying Geoff’s hospitality when I was in Wellington in 2008 as the Forder Lecturer. It was also good that the seminar organiser for the Pure Maths seminar on Monday was a member of the London Mathematical Society council.

As the first Aitken lecture tour, there was an element of setting precedents about the trip. One obvious precedent is that, unlike the Forder lecturer, the Aitken lecturer doesn’t have to visit every university town in the country. Geoff went to the contrasting cities of St Andrews, Manchester, Cambridge, London and Oxford. Another precedent was that he offered just two lectures, unlike the half-dozen or so I had offered the New Zealanders.

The two talks were on very different aspect of representable matroids.

On Friday we heard about the positive result that Geoff, with his collaborators Bert Gerards and Jim Geelen, have recently obtained: an extension of the justly celebrated results of Robertson and Seymour from graphs to binary matroids.

Since all matroids in the talk were representable, almost always over the binary field GF(2), no formal definition of a matroid was necessary. Instead, the understanding was:

• A matroid is the configuration formed by a finite family of vectors in a vector space, which can be represented as the columns of a matrix.
• A matroid property is one which is invariant under row operations on the matrix, and hence expressible in terms of linear independence or dependence of sets of columns.
• A mathematical structure is specified by its substructures. The substructures of a matroid are its minors, those matroids obtained by repeated deletion and contraction. Here deletion of a column simply means throwing it away; and contraction is projection from a vector onto a hyperplane not containing it, or in practical terms, apply row operations so that the corresponding column has first entry 1 and other entries 0, and then delete that column and the first row.

Thus, matroid representations are a branch of linear algebra. We were treated to a comparison between teaching elementary linear algebra to a big first-year class to the task of Sisyphus, condemned to push the stone up the hill every day, only for it to roll back down during the night.

The main theorem of GGW asserts:

The class of binary matroids (those representable over GF(2)) is well-quasi-ordered under the minor relation; that is, there exists no infinite collection of mutually incomparable binary matroids.

Binary matroids generalise graphs. Given a graph, the incidence matrix (with rows indexed by vertices and columns by edges, and (v,e) entry 1 if v lies on e, 0 otherwise), represents the cycle matroid of the graph. For graphs, deletion and contraction of edges mean exactly what you think they mean: deletion involves throwing away an edge, contraction involves shrinking it to a single vertex. Neil Robertson and Paul Seymour proved the conjecture of Wagner according to which graphs are well-quasi-ordered by the minor relation: this theorem is thus generalised by the GGW theorem.

Geoff was at pains to stress the constructive aspect of the theorem. If a class of structures has infinite antichains (sets of pairwise incomparable elements), then the recognition property for some minor-closed classes would be recursively unsolvable. For there would be uncountably many minor-closed classes (forbidding any subset of the antichain), but only countably many recognition algorithms. By contrast, for both graphs and binary matroids, the recognition problem for minor-closed classes is polynomial.

We were also given an outline proof of the theorem, both for graphs and for binary matroids. I enjoyed this, perhaps especially the quick proof that every planar graph is a minor of a sufficiently large grid. Take a sheet of paper ruled with a fine-mesh grid. Draw the planar graph on it with a highlighter pen. The part of the grid covered by ink from the highlighter can obviously be contracted to give the planar graph.

Geoff and his collaborators spent the last thirteen years proving this major theorem. Bravely, they are not rushing into print with it, but are hoping they can overcome the remaining obstacles to proving the result for matroids representable over any given finite field.

On Monday, he talked about representability over infinite fields, where, as he said, everything that works over finite fields either “turns to custard” or becomes much more difficult. While there are only finitely many excluded minors for representability over GF(2), GF(3) or GF(4) (and Rota conjectured that this is so for any finite field), a theorem of Geoff with Dillon Mayhew and Mike Newman asserts that there are so many excluded minors for real representability that every real-representable matroid is a minor of an excluded minor.

When Whitney first wrote down the axioms for a matroid (there are four axioms, in the “rank function” formulation), it is clear that he was really trying to axiomatise matroids over the real numbers, and was looking for a “fifth axiom” which would characterise real matroids. Peter Vamos later wrote a paper entitled “The missing axiom of matroid theory is lost forever”, in which he showed that no finite set of first-order axioms could be added to Whitney’s four to characterise real matroids. However, as Geoff pointed out to us, this is a misunderstanding which has been exacerbated by the rather dramatic title of Vamos’ paper.

Whitney’s axioms are second-order, that is, they involve quantification over subsets of the domain. As Geoff pointed out, Tutte’s excluded minor theorem gives a “fifth axiom” for binary matroids which, like the other four, is second-order; no finite number of first-order axioms suffice even for the relatively tame class of binary matroids, and there is no reason why they should. Now deciding whether we can add a second-order axiom for real matroids would be an achievement; the expectation would be that no such axiom exists.

There are some interesting, but seemingly untouchable, questions about how to define a random real-representable matroid and what such an object should look like.

This work has philosophical connections, related to Kant’s concept of the “synthetic a priori“, which I have described elsewhere.

Job done, he is now on the way home.