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
- Inequivalent representations of matroids (this page)
- Growth rates of minor-closed classes
- Extremal matroid theory
Inequivalent representations of matroids
Given a representation $A$ of a matroid $M$, we can obtain other representations of $M$ by applying row operations and column scaling to $A$; such representations are said to be projectively equivalent to $A$.
There exist matroids with arbitrarily many projectively inequivalent representations over any field with at least four elements, however, the situation improves with increased connectivity. For example, Kahn proved that $3$-connected matroids have at most two inequivalent representations over GF$(4)$ and Oxley, Vertigan, and Whittle proved that they have at most six inequivalent representations over GF$(5)$. Oxley, Vertigan, and Whittle also gave examples showing that $3$-connectivity is not sufficient to bound the number of inequivalent representations over any larger field.
The next development came as quite a surprise to us; a dichotomy between prime fields and non-prime fields emerged. Examples that I found with Gerards and Whittle show that, for each integer $k$ there is a finite field $\bF$ (of non-prime order) such that $k$ connected matroids can have arbitrarily many inequivalent representations over $\bF$. Whereas, for fields of prime order, I proved the following remarkable result with Geoff Whittle.
Theorem 1. For each field $\bF$ of prime order there exists an integer $c$ such that each $4$-connected matroid has at most $c$ inequivalent representations over $\bF$.
The proof of Theorem 1 is long (the paper is 175 pages); it introduces an intermediate notion, $k$-coherence, between $3$-connectivity and $4$-connectivity which turns out to be much easier to work with than $4$-connectivity. The complexity of this proof did not bode well for non-prime fields, but, in joint work with Bert Gerards, Tony Huynh, and Stefan van Zwam, we were able to prove the following result.
Theorem 2. For each finite field $\bF$ there exist an integers $c$ and $k$ such that each $k$-connected matroid has at most $c$ inequivalent representations over $\bF$.
This result played a significant role in the proof of Rota's Conjecture. The proof of Theorem 2 introduced an exciting new technique for generating $k$-connected matroids that is analogous to Tutte's Wheels and Whirls Theorem.
While Theorems 1 and 2 say a lot about inequivalent representations, there is still at lot of scope for interesting work in this area. For example, we are still some way off from solving the following:
Conjecture. For each finite field $\bF$ there exists a polynomial-time algorithm that, given two matrices $A_1$ and $A_2$ over $\bF$ whose columns are indexed by a common set $E$, determines whether $M(A_1)=M(A_2)$.
To prove this conjecture one would likely require the constructive version of the Matroid Minors Structure Theorem.