The densest matroids in minor-closed classes with exponential growth rate

Abstract:

The growth rate function for a nonempty minor-closed class of matroids $\mathcal {M}$ is the function $h_{\mathcal {M}}(n)$ whose value at an integer $n \ge 0$ is defined to be the maximum number of elements in a simple matroid in $\mathcal {M}$ of rank at most $n$. Geelen, Kabell, Kung and Whittle showed that, whenever $h_{\mathcal {M}}(2)$ is finite, the function $h_{\mathcal {M}}$ grows linearly, quadratically or exponentially in $n$ (with base equal to a prime power $q$), up to a constant factor.

We prove that in the exponential case, there are nonnegative integers $k$ and $d \le \tfrac {q^{2k}-1} {q-1}$ such that $h_{\mathcal {M}}(n) = \frac {q^{n+k}-1}{q-1} - qd$ for all sufficiently large $n$, and we characterise which matroids attain the growth rate function for large $n$. We also show that if $\mathcal {M}$ is specified in a certain ‘natural’ way (by intersections of classes of matroids representable over different finite fields and/or by excluding a finite set of minors), then the constants $k$ and $d$, as well as the point that ‘sufficiently large’ begins to apply to $n$, can be determined by a finite computation.