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

Original · EN

The growthratefunction for a nonempty minor-closed class of matroids M is the function hₘ(n) whose value at an integer n ≥ 0 is defined to be the maximum number of elements in a simple matroid in M of rank at most n. Geelen, Kabell, Kung and Whittle showed that, whenever hₘ(2) is finite, the function hₘ 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 ≤ q²ᵏ-1q-1 such that hₘ(n) = qⁿ⁺ᵏ-1q-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 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.