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
- Rota's Conjecture (this page)
- Inequivalent representations of matroids
- Growth rates of minor-closed classes
- Extremal matroid theory
Rota's Conjecture
In his introductory paper on matroid theory in 1935, Hassler Whitney posed the problem of characterizing the representable matroids. This problem is widely open to interpretation since there are many types of characterizations that one might consider and since one can consider representability over a specified or unspecified field. With two notable exceptions, interpretations have typically been met with negative answers. The first exception is the algorithmic problem of determining whether a given matroid is representable over any (unspecified) field, which was proved to be decidable by Vamos in 1971.
The second exception is the following conjecture, posed by Gian-Carlo Rota in 1970, which I proved together with Bert Gerards and Geoff Whittle in early 2013.
Rota's Conjecture. For each finite field $\bF$, there are, up to isomorphism, only finitely many excluded minors for the class of $\bF$-representable matroids.
Stefan van Zwam posted a nice introduction to Rota's Conjecture on the Matroid Union blog. Our work on Rota's Conjecture attracted media attention in Canada, the Netherlands, (in Dutch) and in New Zealand.
The proof of Rota's Conjecture relies on the full Matroid Minors machinery, including the WQO Theorem and the Matroid Minors Structure Theorem. A consequence of having used the WQO Theorem is that we do not have a computable bound on either the size nor the number of excluded minors.
As general and powerful Matroid Minors machinery is, we needed to develop a lot of specialized machinery in order to prove Rota's Conjecture. In fact, when we turned to Rota's Conjecture at the start of 2011, we did not have a concrete strategy in mind. It was not until early 2012, that we came upon the ideas that would eventually work. We developed some of this new machinery with Tony Huynh and Stefan van Zwam; those results involve inequivalent representations of matroids and are discussed in the next section.
The final step in the proof amounted to understanding pairs $(M_1,M_2)$ of $\bF$-representable matroids where $M_2$ is obtained from $M_1$ by relaxing a circuit-hyperplane. In particular, we show that such pairs cannot have arbitrarily high branch-width. The proof of this result uses the Matroid Minors Structure Theorem.