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
- Growth rates of minor-closed classes (this page)
- Extremal matroid theory
Growth rates of minor-closed classes
In this section, minor-closed classes are assumed to be closed under isomorphism as well.
For a minor-closed class $\cM$ of matroids, we let $g_{\cM}(n)$ denote the maximum number of elements of a simple rank-$n$ matroid in $\cM$. For example, for the class $\cM$ of matroids representable over the $q$-element field, $g_{\cM}(n) = \frac{q^n-1}{q-1}$; for the class $\cG$ of graphic matroids, $g_{\cG}(n) = {n+1\choose 2}$; and for the class $\cG^*$ of cographic matroids, $g_{\cG^*}(n) = 3(n-1)$.
I have taken the liberty of calling $g_{\cM}$ the growth-rate function for $\cM$; Kung uses this name for another function. The growth-rate function is not well-defined on all classes, for example, if $\cM$ contains all simple rank-$2$ matroids then $g_{\cM}(2)$ is not well-defined (we could take the convention that it is infinity). Kung proved that the growth-rate function is well defined if and only if $\cM$ omits some simple rank-$2$ matroid.
I proved the following result in a sequence of three papers, the first with Geoff Whittle, the second with Kasper Kabell, and the third with Joseph Kung and Geoff Whittle.
Growth-rate Theorem.
Let $\cM$ be a minor-closed class of
matroids that omits some simple rank-$2$ matroid.
Then either
I find this result quite extraordinary; not only does it show that growth-rate functions are either linear, quadratic, or exponential, but graphic matroids and representable matroids appear out of the air.
We call a class linearly dense , quadratically dense, or base-$q$ exponentially dense according to the outcome of the Growth-rate Theorem.
Exponentially dense classes
Peter Nelson completed his doctoral thesis on exponentially-dense classes. The following result is one of our joint results in his thesis, it determines the "eventual" growth-rate function for the class of matroids with no $U_{2,m+2}$-minor.Theorem 1. Let $m$ be a positive integer, let $q$ be the largest prime-power less than or equal to $m$, and let $\cM$ denote the set of all matroids with no $U_{2,m+2}$-minor. Then $g_{\cM}(n) \le \frac{q^n-1}{q-1}$, for all sufficiently large $n$.
Building on the work in Peter's thesis, he and I now have a thorough understanding of the growth-rate functions for exponentially-dense classes.Theorem 2. For any base-$q$ exponentially-dense class $\cM$ of matroids there exist integers $c$ and $k$ such that, for all sufficiently large $n$, $$ g_{\cM}(n) = \frac{q^{n+k}-1}{q-1} - cq.$$
We are currently writing up the proof of Theorem 2.
Quadratically and linearly dense classes
In the long term, I hope that we will be able to understand the linearly and quadratically dense classes as well as we understand the exponentially dense classes. For linearly dense classes this will particularly difficult since graph theorists do not have a good handle on growth-rates despite having all the power of the Graph Minors Structure Theorem.
For quadratically dense classes, it would be a good start to prove that the growth rate is actually quadratic.
Conjecture. For any quadratically-dense class $\cM$ of matroids there exists a quadratic polynomial $p$ such that $ g_{\cM}(n) = p(n)$ for all sufficiently large $n$.