$\newcommand{\cM}{\mathcal{M}}$

This entry continues on from my last, which concerns the growth rates of matroids in minor-closed classes. A one-line recap of my notation is that, if $\cM$ is a minor-closed class of matroids, then $h_{\cM}(n)$ denotes the ($\mathbb{Z} \cup \{\infty\}$)-valued function whose value at each integer $n$ is the maximum number of elements in a simple matroid in the class of rank at most $n$. Last time I finished with the growth rate theorem of Geelen, Kabell, Kung and Whittle – here it is again.

Growth Rate Theorem
Let $\cM$ be a minor-closed class of matroids. Either

1.  $h_{\cM}(n) \le c_{\cM}n$ for all $n$,
2. $\binom{n+1}{2} \le h_{\cM}(n) \le c_{\cM}n^2$ for all $n$, and $\cM$ contains all graphic matroids,
3. $\frac{q^n-1}{q-1} \le h_{\cM}(n) \le c_{\cM}q^n$ for all $n \ge 2$ and some prime power $q$, and $\cM$ contains all GF$(q)$-representable matroids, or
4. $h_{\cM}(n) = \infty$ for all $n \ge 2$, and $\cM$ contains all simple rank-$2$ matroids.

This is surprising – up to a constant factor, the growth rate function for an arbitrary minor-closed class has just four possible types and, if the class has superlinear growth rate function then the function is `explained’ by the class containing a natural class with which its growth rate function agrees asymptotically. In this entry and the next, we’ll discuss some questions related to this theorem, starting with the scariest.

Structure

Thinking as we did with Mader’s theorem (Theorem 1 in my last entry), the burning question is why growth rate functions are restricted in this way. In the case of graphs, growth rate functions are controlled because of the structure guaranteed by the graph minors structure theorem. For this purpose, we can only really hope to describe classes satisfying outcomes 1-3 of the theorem, so we exclude some rank-$2$ uniform matroid to gain traction, and pose the following question:

Problem 1: Given an integer $n$, find a structural description for minor-closed classes of matroids not containing $U_{2,n}$.

An solution to this problem would yield a theorem that implies the growth rate theorem (and much more) very easily.

This problem is probably extremely difficult in general, but the case where the matroids are representable over a fixed finite field GF($q$) has been solved. As a major part of their work on the recently vanquished Rota’s Conjecture, Geelen, Gerards and Whittle have proved (but unfortunately not quite written yet – see [GGW07]) a structure theorem for the matroids in arbitrary minor-closed class of GF$(q)$-representable matroids. The representable case of the growth rate theorem falls out of their theorem without much effort.

However, the non-representable case has genuine difficulties not arising from representable matroids that make a structure theorem much harder to dream up. Spikes, for example, cause a special type of trouble that doesn’t crop up over finite fields (see [G08] for a discussion). Problem 1 in its full generality is still very much open.

Zooming In

Something that seems more approachable is to ask more exact questions about how growth rate functions behave. It is one thing to know that $h_{\cM}(n)$ is bounded above and below by, say, a quadratic in $n$, but it is another thing to know the asymptotic or exact behaviour of the function itself. In some cases, this is trivial; there are no prizes for working out the answer if $\cM$ is the class of graphic matroids, for example. In some cases, it seems very hard – even the class of graphic matroids with no $M(K_t)$-minor for general $t$ has a growth rate function that is only partially understood (it is a linear function whose gradient is known asymptotically in $t$, but not known for any fixed $t > 9$ (edit: corrected – thanks Jim), see Thomason [T01]).

However, for many specific classes, the problem is interesting and some results are known. Kung, Mayhew, Pivotto and Royle [KMPR13] recently showed that the growth rate function for the binary matroids with no AG$(3,2)$-minor is the same as that of the graphic matroids for all $n \ge 5$. Geelen and I [GN10] showed that, for sufficiently large $n$, the growth rate function for the class of matroids with no $U_{2,\ell+2}$-minor is equal to that of the GF$(q)$-representable matroids, where $q$ is the largest prime power not exceeding $\ell$. We also have shown, (and will write someday) that every minor-closed class $\cM$ whose growth rate function is exponential in $n$ satisfies $h_{\cM}(n) = \frac{q^{n+k}-1}{q-1} – qd$ for all sufficiently large $n$, where $k$ and $d$ are nonnegative integers with $d \le \frac{q^{2k}-1}{q^2-1}$.

Many questions of this sort are still open. Here is one in quite a general form:

Problem 2: Let $\mathfrak{F}$ be a set of fields containing at least one finite field, and $\cM$ be the class of matroids representable over all fields in $\mathfrak{F}$. Determine $h_{\cM}(n)$.

This determination could be asymptotic, exact, or exact for all large $n$. Some cases are easy; if $\mathfrak{F}$ contains GF$(2)$ then it is either the class of binary matroids or regular matroids. If $\mathfrak{F}$ contains GF$(3)$ then the answer will follow from Whittle’s characterisation of ternary matroids [W97]. If all fields in $\mathfrak{F}$ share a common subfield that is not itself in $\mathfrak{F}$, then $\cM$ has exponential growth rate function and the (eventually exact) answer probably follows from our theorem above. If $\mathfrak{F} = \{\mathrm{GF}(4), \mathrm{GF}(5)\}$ then $\cM$ is the class of golden-mean matroids and there is a conjectured answer of Archer [A05] confirmed in some cases by Welsh [W11]. The case where $\mathfrak{F}$ contains $\mathbb{C}$ and one other field GF$(q)$ is very interesting and the extremal examples are probably all Dowling geometries over GF$(q)$. Here is a concrete conjecture to that effect:

Conjecture 1: Let $q$ be a prime power. The class $\cM$ of matroids representable over $\mathbb{C}$ and GF$(q)$ has growth rate function $h_{\cM}(n) = n + (q-1)\binom{n}{2}$ for all sufficiently large $n$.

One could modify this conjecture to the case where $\cM$ is the class of $\mathbb{C}$-representable matroids with no $U_{2,t}$-minor for some integer $t \ge 4$. In this case, the extremal examples are still probably the Dowling geometries, but again not much is known.

Next time, we’ll talk about generalisations of $h_{\cM}(n)$ applying to classes that do contain all simple rank-$2$ matroids. See you then.

References

[A05] S. Archer. Near varieties and extremal matroids, PhD thesis, Victoria University of Wellington, 2005.

[G08] J. Geelen. Some open problems on excluding a uniform matroids. Adv. in Appl. Math. 41(4):628-637, 2008.

[GGW07] J. Geelen, B. Gerards, G. Whittle. Towards a matroid-minor structure theory. In Combinatorics, complexity and chance, vol. 34 of Oxford Lecture Ser. Math. Applic. 72-92. Oxford Univ. Press, Oxford, 2007.

[GN10] J. Geelen, P. Nelson. The number of points in a matroid with no $n$-point line as a minor. J. Combin. Theory Ser. B, 100(6):625-630, 2010

[KMPR13] J. Kung, D. Mayhew, I. Pivotto, G. Royle. Maximum size binary matroids with no AG(3,2)-minor are graphic. arXiv:1304.2448 [math.CO]

[T01] A. Thomason. The extremal function for complete minors. J. Combin. Theory Ser.B 81:318-338, 2001

[W11] M. Welsh. Golden mean and secret sharing matroids. Master’s thesis, Victoria University of Wellington, 2011.

[W97] G. Whittle. On matroids representable over GF(3) and other fields. Trans. Amer. Math. Soc., 349(2):579-603, 1997