We have just had, as usual, a set of very fine lectures at the British Combinatorial Conference at Royal Holloway. I’ve said a bit about the lectures by Doron Zeilberger and Einar Steingrímsson. I can’t discuss them all, but I will say something about this morning’s lecture by Geoff Whittle, mainly just to record a throwaway remark he made right at the end (and also because it is very nice mathematics).
For the last fourteen years, he, with Jim Geelen and Bert Gerards (henceforward GGW), have been working on an extension of the Robertson–Seymour (RS) Graph Minors theorem. A minor of a graph is obtained by a sequence of operations each of which is the deletion or contraction of an edge or (or throwing away isolated vertices). The headline result of RS is that the ordering of finite graphs by the minor relation is a well-quasi-order (that is, there are no infinite antichains). Geoff gave us a very clear overview of this theorem. It depends on a structure theorem for proper minor-closed graph classes. A graph in such a class is obtained by glueing together, in a treelike fashion, graphs which are “bounded distortions” of planar graphs. There are three allowable kinds of distortion:
- we can add a few handles or crosscaps (that is, allow other surfaces);
- we can add a few “apex vertices” outside the plane, joined to arbitrary subsets of the other vertices;
- we can add a few “vortices of bounded width” (whatever they are).
Here the precise meaning of “a few”, “bounded”, and the glueing mechanism depends on the particular class.
Geoff made it very clear that the really important result is the structure theorem, not the WQO result.
GGW have proved the analogous result for minor-closed families of matroids representable over any fixed finite field. A matroid representable over F can be thought of as a matrix over F, up to row operations; the structure is carried by an index set for the columns and consists of the family of sets of indices of linearly independent sets of columns. We can think of this as a set of points in the projective space over F. Deletion means simply throwing away a column; contraction (of a non-zero column) involves transforming it to have 1 in the first row and 0 elsewhere, by row operations, and then deleting it together with the first column. (Geometrically this corresponds to projecting the remaining points from the given point onto a disjoint hyperplane.
The sense in which this is now a theorem was described by Geoff as follows. GGW have spent the last fourteen years struggling through swamps, over ravines, and across mountains and deserts, and have now reached the land of milk and honey. But their next job is to build a road so that all of us can go there (that is, to write it up), and they expect this to take several more years.
They were unable to apply results from RS directly, but had to adapt the arguments there (with some difficulty). The minor-closed classes of matroids naturaly fall into several levels, determined by the growth of the function giving the size of the largest matroid of given rank in this class (this function is linear, quadratic or exponential).
Geoff described in some detail the structure of the important bottom level. It is similar to the corresponding structure theorem in RS, except that graphs have to be replaced by “Dowling matroids”, graphs with their edges labelled by group elements from the multiplicative group of the field.
If you want to learn more (and you probably should), read the nice article in the current Surveys in Combinatorics volume.
As I have mentioned before, Geoff began life as a philosopher, and is always prepared to step back and think about what he is doing. He ended with the following speculation.
Let us imagine that, at some time in the future, their increasing complexity causes computers to become conscious. (This is a big fish to swallow, but never mind.) Since computers think in binary, we would expect them to open their eyes into a binary world rather than the real world. After some time, they will invent matroid theory, and will begin to wonder about minor-closed classes of binary matroids. The nature of the structure theorem means that, in order to solve this, they will have to discover for themselves the topology of surfaces!