This section gives highlights of my recent research. I assume that the reader is familiar with standard terminology in matroid theory such as representation, minors, duality, and connectivity. Introductions to matroid theory can be found on Wikipedia or in the following survey paper by James Oxley.
This section is arranged by topic:
- Matroid Minors Project (this page)
- Rota's Conjecture
- Inequivalent representations of matroids
- Growth rates of minor-closed classes
- Extremal matroid theory
Matroid Minors Project
At a graph theory meeting in Oberwolfach, Germany, in 1999, Paul Seymour and Neil Robertson proposed ideas for extending their Graph Minors Project from graphs to matroids representable over a given finite field. The Graph Minors machinery is very powerful and has had a huge influence in graph theory and in theoretical computer science. It was clear that the extension of these ideas to matroid theory had enormous potential, so Bert Gerards Geoff Whittle and I leapt at the challenge, and have been beavering away in this direction ever since.
In 2011, we had managed to complete the main steps in our Matroid Minors project. In particular, we have extended the Well-Quasi-Ordering Theorem for graphs to matroids.
WQO Theorem. For each finite field $\bF$ and each infinite set of $\bF$-representable matroids, there are two matroids in the set such that one is isomorphic to a minor of the other.
Note that, the set of all matroids is not well-quasi-ordered since, for example, projective planes over distinct prime fields are incomparable.
The WQO Theorem can be reformulated as:
- For each finite field $\bF$ and each minor-closed class $\cM$ of $\bF$-representable matroids, there are, up to isomorphism, only finitely many $\bF$-representable excluded minors for the class $\cM$.
- There are only countably many minor-closed classes of $\bF$-representable matroids.
Almost all of the work in the Matroid Minors Project was in understanding the structure of the matroids in a minor-closed class over a given finite field. The Matroid Minors Structure Theorem describes that structure and is the workhorse of the whole project. The gist of the theorem is that, if $\cM$ is a minor-closed class of matroids representable over a given finite field $\bF$, then the members of $\bF$ can be constructed, in a specified way from:
- matroids represented over proper subfields of $\bF$, and
- frame matroids (these are matroids that can be represented by a matrix with at most two non-zero entries in each column).
Note that, one can encode a frame matroid by an edge-labelled graph. So, using the Matroid Minors Structure Theorem, one can reduce problems on minor closed classes of $\bF$-representable matroids to similar problems over subfields and to problems on labelled graphs.
The Graph Minors Project was written up as a series of 23 papers totalling more than 600 pages in length. We are currently immersed in the writing of our Matroid Minors Project, and expect that the writing will take several years.
We expect that the Matroid Minors Structure Theorem will have a number of applications, so there is still a lot of work to do. In particular, we intend to write up a constructive version of the result for algorithmic applications. Due to our writing backlog, it will be some time before we get to this.