$\newcommand{\elem}{\varepsilon}$
Time for more growth rates. For a matroid $M$ we’ve looked at $\elem(M)$, the number of points in $M$, as a simple density parameter that is bounded as a function of $\ell$ and $r$ whenever we exclude $U_{2,\ell+2}$ as a minor. Then, as a way to talk about density when excluding a uniform minor of larger rank than $2$, we generalised this to $\tau_a(M)$, defined to be the number of rank-$a$ flats required to cover $\elem(M)$, which turned out to be the right notion of density to think about when excluding a rank-$(a+1)$ uniform matroid as a minor. As far as excluding different uniform minors is concerned, $\tau_a$ is the generalisation of $\elem$ that we need. However, there is another natural way to generalise $\elem(M)$ to ‘higher rank’, which is what this post is about.

For a matroid $M$ and a nonnegative integer $k$, we let $W_k(M)$ denote the number of rank-$k$ flats in $M$. This parameter, known as the $k$th Whitney number of the second kind, is clearly of interest when thinking about the lattice of flats of $M$. A 1971 conjecture of Rota [R71] is that the sequence $W_0(M),W_1(M), \dotsc, W_r(M)$ is unimodal; that is, that $W_k(M) \ge \min(W_{k-1}(M),W_{k+1}(M))$ for each $k$. From what I can see in the published literature, this conjecture is still open, although Huh, Katz and Lenz [HK11,L11] have recently used sophisticated algebraic techniques to make real progress on similar conjectures in the representable case. In fact, Mason [M72] conjectured a few strengthenings of this conjecture; the first and weakest is that the sequence of Whitney numbers is log-concave (which is itself stronger than unimodality).

What I’m considering today relates more to previous posts than the above conjectures: bounding $W_k(M)$ above by a function of $\ell$ and $r(M)$ when excluding a $U_{2,\ell+2}$ (when excluding a larger uniform minor it is not hard to argue that no such bound is possible). This has quite a different flavour to the conjecture above; we know that in many ways excluding a uniform minor gives classes whose extremal members resemble projective geometries, so we’d hope that the bounds we get are similar or equal to those we get for geometries. The number of rank-$k$ flats in a geometry PG$(n-1,q)$ is a nice number which we denote ${n \brack k}_q$. More explicitly,
\[ W_k(\mathrm{PG}(n-1,q) = {n \brack k}_q = \frac{(q^n-1)(q^{n-1}-1)\dotsc(q^{n-k+1}-1)}{(q^k-1)(q^{k-1}-1)\dotsc(q-1)}\]
This is known as the Gaussian binomial coefficient for $n,k$ and $q$. We already know by Kung’s theorem that a rank-$r$ matroid with no $U_{2,q+2}$-minor has at most ${r \brack 1}_q = \frac{q^r-1}{q-1}$ rank-$1$ flats. The natural generalisation of this statement was conjectured by Bonin:

Conjecture 1: If $q$ is a prime power and $M$ is a rank-$r$ matroid with no $U_{2,q+2}$-minor, then $W_k(M) \le {r \brack k}_q$ for each integer $k$.

Unfortunately, this conjecture is false – I’ll get to the counterexample in a minute. In [N13] I proved this conjecture whenever $r$ is large compared to $k$ and $q$. In fact, as with our generalisation of Kung’s theorem in our first post, I get the projective geometry bound for excluding an arbitrary rank-$2$ uniform minor, not just one corresponding to a prime power.

Theorem 1: For all integers $\ell \ge 2$ and $k \ge 0$ there is an integer $r_0$ such that, if $M$ is a matroid with no $U_{2,\ell+2}$-minor and $r(M) \ge r_0$, then $W_k(M) \le {r(M) \brack k}_q$, where $q$ is the largest prime power not exceeding $\ell$.

It is good to know this. However, this theorem doesn’t tell us everything. For many reasons, it would be very nice to have a good upper bound on the number of hyperplanes of a matroid with no $U_{2,q+2}$-minor; the above theorem says nothing when $k = r-1$, only when $r$ is huge compared to $k$. One can obtain a crude upper bound on the number of hyperplanes by bounding the number of points and observing that each hyperplane is spanned by $r-1$ points, but this bound, roughly $q^{q^2}$, is likely dramatically wrong.

Conjecture 1 would imply that the correct upper bound for the number of hyperplanes when excluding $U_{2,q+2}$ is $\frac{q^r-1}{q-1}$. I don’t have any good ideas for how to prove this, and in fact this is where the conjecture fails – the next theorem follows from a construction communicated to me by Blokhuis.

Theorem 2: For each prime power $q$ there is a rank-$3$ matroid $M_q$ with no $U_{2,2q}$-minor such that $W_2(M_q) = q^2 + (q+1)\binom{q}{2}$.

For large $q$, this is too many lines for Conjecture 1 to hold! There are issues with the precise numbers, but essentially Conjecture 1 would state that $W_2(M) \le q^2 + q+ 1$ for any matroid $M$ with no $U_{2,q+2}$-minor; this is quadratic in $q$, but $W_2(M_q)$ is cubic in $q$. The factor of $2$ in the length of the line that $W_2(M_q)$ omits is unimportant in the face of this qualitative difference. It is fairly easy to use Theorem 2 to find counterexamples to Conjecture 1 for all $q \ge 128$; Using a variation on the construction and a bit of work for small $q$, Jim and I [GN13] proved the following:

Theorem 3: When $r = 3$ and $k = 2$, Conjecture 1 holds if and only if $q \le 5$. On the other hand, when $q \in \{2,3,4\}$, and $k = 2$, Conjecture 1 holds for all $r$.

The first part of this is unfortunate, as Conjecture 1 is pretty. What I would hope is that the examples in Theorem 2 are a result of rank-$3$ sporadicity of the same sort that makes projective planes so hard to classify for finite geometers. It’s quite possible that Conjecture 1 holds for all $r \ge 4$, but I would settle for the following.

Conjecture 2: For all $q$ there is an integer $r_0$ such that Conjecture 1 holds for $q$, all $k$ and all $r \ge r_0$.

The difference between this statement and that of Theorem 1 is that there is no longer any dependence of $r_0$ on $k$; the above conjecture would give a sensible upper bound on the number of hyperplanes. It would also be very interesting to see what happens in even the smallest concrete rank-$4$ cases for which we don’t already have the answer:

Conjecture 3: Conjecture 1 holds for $r = 4, k = 3$ and $q = 3$.
Conjecture 4: Conjecture 1 holds for $r = 4, k = 2$ and $q = 7$.

Next time, I’ll be back talking about something other than growth rates. See you then!

References
[GN13] J. Geelen, P. Nelson, The number of lines in a matroid with no $U_{2,n}$-minor, arXiv:1306.2387 [math.CO]
[HK11] J. Huh, E. Katz, Log-concavity of characteristic polynomials and the Bergman fan of matroids, arXiv:1104.2519 [math.CO]
[L11] M. Lenz, Matroids and log-concavity, arXiv:1106.2944 [math.CO]
[M72] J. H. Mason, Matroids: unimodal conjectures and Motzkin’s theorem. In Combinatorics (eds. D. J. A. Welsh and D. R. Woodall), pp 207-220 (1972). Institute of Math. and its Applications, Southend-on-Sea. [15.2]
[N13] P. Nelson, The number of rank-$k$ flats in a matroid with no $U_{2,n}$-minor, arXiv:1306.0531 [math.CO].
[R71] G.-C. Rota, Combinatorial theory, old and new. In Proc. Internat. Cong. Math.<> (Nice, 1970), pp. 229-233. Gauthier-Villars, Paris (1971). [6.0,6.5,14.0,15.2].

Too dense to measure? 

I’m back, writing more about growth rates of matroids in minor-closed classes. In the last two posts, I’ve been talking about the growth rate function $h_{\mathcal{M}}$ of a class, which measures the maximum number of elements in a simple rank-$n$ matroid in the class, or (essentially) equivalently the maximum number of points in a rank-$n$ matroid of the class, which is not necessarily required to be simple. In this post I’ll stop using the ‘function’ notation and instead just state things more explicitly for individual matroids.

The reason for this is that I’ll be writing this time about matroids whose growth rate function is infinite, but still seem ‘sparse’ compared to random matroids.  The easiest example of this is the class of bicircular matroids, which are the graph-like matroids obtained by starting from a basis B and freely extending lines spanned by pairs of elements of B any number of times. (Technically we have to close under minors also). These are the same class as the matroids having a real-representation where each column contains at most two nonzero entries and all nonzero entries are algebraically independent.

An easy observation is that a rank-$n$ bicircular matroid can have arbitrarily many points, as you can keep adding new points on any line between a pair of basis elements and stay bicircular. Therefore the class of bicircular matroids contains all simple rank-$2$ matroids and there is no bound on its growth rate function. The reason this seems like a problem, though, isn’t that we’re unhappy with matroids having unbounded numbers of points, it’s that the bicircular matroids seem intuitively quite sparse.

To make this concrete, we can make the easy observation that every rank-$n$ bicircular matroid is the union of at most $\binom{n}{2}$ rank-$2$ sets. This is an unusual property that dramatically separates bicircular matroids from random matroids, and it’s how we’ll talk about the more general notion of density this post is about.

Covering Number

If $M$ is a matroid (of rank at least $a$) and $a$ is a positive integer, then $\tau_a(M)$ will denote the minimum size of a collection of rank-$a$ sets with union $E(M)$. We call this the $a$-covering number of $M$. It is not too hard to see that if $M \cong \mathrm{PG}(n-1,q)$ then $\tau_a(M)$ is roughly $\frac{q^r-1}{q^a-1}$ and that if $M \cong M(K_n)$ then $\tau_a(M)$ is roughly $\binom{n+1}{2}/\binom{a+1}{2}$, so $\tau_a$ behaves pretty similarly to counting points for nice matroids like cliques and projective geometries. However, unlike the ‘number of points’ parameter, covering number enables us to say the bicircular matroids are only quadratically dense; if $M$ is a rank-$n$ bicircular matroid then $\tau_2(M) \le \binom{n}{2}$. This seems to do much better justice to their structure.

Given an $a$, it is still easy to construct fixed-rank matroids for which $\tau_a$ is arbitrarily large. The easiest construction is just the uniform matroid $U_{a+1,b}$. In covering such a matroid with rank-$a$ sets there isn’t anything clever you can do; all the rank-$a$ sets have just $a$ elements and in the end you need $\tau_a(U_{a+1,b}) = \left\lceil\frac{b}{a}\right\rceil$ sets to do the job. However, there is a beautiful partial converse to this statement due to Geelen and Kabell [gk09], who also introduced the parameter.

Theorem 1: If $r \ge a$ and $M$ is a rank-$r$ matroid with no $U_{a+1,b}$-minor then $\tau_a(M) \le \binom{b-1}{a}^{r-a}$.

Just like Kung’s theorem did for counting points  (see my first entry), this result provides a perfect description of which minor-closed classes have the property that $\tau_a$ is bounded above by a function of rank; they are exactly those that do not contain all rank-$(a+1)$ uniform matroids. Jim Geelen conjectured much more than this, though, in his excellent paper [g08] on excluding a uniform matroid as a minor. He postulated that the growth rate theorem almost survives the generalisation to $\tau_a$ unchanged:

Conjecture 1: If $a$ is an integer and $\mathcal{M}$ is a minor-closed class of matroids, then either

1. $\tau_a(M) \le c r(M)$ for all $M \in \mathcal{M}$;
2. $\tau_a(M) \le c r(M)^2$ for all $M \in \mathcal{M}$ and $\mathcal{M}$ contains all bicircular matroids or all graphic matroids;
3. there is a prime power $q$ so that $\tau_a(M) \le c q^{r(M)}$ for all $M \in \mathcal{M}$, and $\mathcal{M}$ contains all GF$(q)$-representable matroids; or
4. $\mathcal{M}$ contains all rank-$(a+1)$ uniform matroids.

This conjecture, which is very probably true, is quite striking; it would tell us that  $\tau_a$-density is ‘controlled’ by geometry- or graph-like matroids in any minor-closed class for which it is not a useless measure of density. The only classes left to worry about would be the ones that contain all uniform matroids of every rank, and those are much easier than the bicircular matroids to dismiss as truly ‘wild’ or ‘infinitely dense’ classes.

Jim and I made some progress [gn12,n13] towards Conjecture 1, proving the following:

Theorem 2: Let $a$ be an integer and $\mathcal{M}$ be a minor-closed class of matroids. Either

1. $\tau_a(M) \le r(M)^c$ for all $M \in \mathcal{M}$;
2. there is a prime power $q$ so that $\tau_a(M) \le c q^{r(M)}$ for all $M \in \mathcal{M}$, and $\mathcal{M}$ contains all GF$(q)$-representable matroids; or
3. $\mathcal{M}$ contains all rank-$(a+1)$ uniform matroids.

This separates the ‘exponential’ classes from the polynomial ones. We’d really like to know more, though; the quadratic and linear part of the conjecture seems quite a lot harder.

In the meantime, it would still be great to understand the parameter $\tau_a$ in more specific settings. Here is a very concrete problem:

Problem 1: Let $M$ be a rank-$r$ $\mathbb{R}$-representable matroid with no $U_{3,6}$-minor. Find an upper bound on $\tau_2(M)$ in terms of $r$.

Theorem 1 gives an upper bound of $10^{r-2}$ and, since projective geometries are not real-representable, Theorem 2 gives $\tau_2(M) \le r^c$ for some constant $c$, but neither of these are particularly satisfactory. If Conjecture 1 holds then the answer should be quadratic in $r$, but it would be nice for it to be a quadratic with reasonable coefficients.

I also believe that, despite the non-committal constants in Theorem 2, the way that $\tau_a$ behaves in exponentially dense classes is somewhat reasonable. There are some issues when computing $\tau_a(\mathrm{PG}(r-1,q)$ when the geometry doesn’t partition neatly into nice rank-$a$ flats (the answer still turns out to be equal to the obvious lower bound), but modulo a small multiplicative factor, something like the following should be true, and possibly quite approachable by the same kind of techniques that were used in the setting of excluding a rank-$2$ minor:

Conjecture 2: If $\epsilon > 0$ and $M$ is a matroid with no $U_{a+1,b}$-minor and of sufficiently large rank, then $\tau_a(M) \le (1 + \epsilon)\tau_a(\mathrm{PG}(r(M)-1,q))$, where $q$ is the largest prime power so that $U_{a+1,b}$-is GF$(q)$-representable.

In other words, the matroids with no $U_{a+1,b}$-minor should be asymptotically no denser than the projective geometries with no $U_{a+1,b}$-minor.

See you next time!

References

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

[gk09] J. Geelen, K. Kabell, the Erdos-Posa property for matroid circuits. J Combin. Theory Ser. B, 99(2):407-419, 2009.

[gn12] J. Geelen, P. Nelson, Projective geometries in exponentially dense matroids. I,  arXiv:1209.1496 [math.CO]

[n13] P. Nelson, Projective geometries in exponentially dense matroids. II, arXiv:1306.0244 [math.CO]

$\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

$\newcommand{\cG}{\mathcal{G}}$ $\newcommand{\cM}{\mathcal{M}}$ $\newcommand{\elem}{\varepsilon}$ $\newcommand{\con}{/}$ $\newcommand{\del}{\!\backslash\!}$

I’m going to give what is hopefully a less frenetically paced exposition of what many readers have probably seen me talk about more that once – the growth rates of matroids in minor-closed classes. I’ll try to cover things from the ground up in order to motivate the subject, as well as provide some short proofs. The traditional starting point, from which I won’t deviate, is a theorem of Mader [Mader67]:

Theorem 1. If $\mathcal{G}$ is a proper minor-closed class of graphs, then $|E(G)| \le c_{\mathcal{G}}|V(G)|$ for each simple graph $G$ in $\cG$.

Here, `proper’ means that $\cG$ isn’t the class of all graphs, and $c_{\mathcal{G}}$ is a positive real constant depending only on $\cG$. Note that this theorem fails if we allow $\mathcal{G}$ to be the class of all graphs; the complete graph $K_t$ has $\binom{t}{2}$ edges and $t$ vertices, and the ratio $\binom{t}{2}$ is not bounded above by any linear function of $t$. With this fact in mind, what is interesting is the dichotomy; either $\cG$ is the class of all graphs and the densest simple graphs in $\mathcal{G}$ (the cliques) have a number of edges that is quadratic in their number of vertices, or $\mathcal{G}$ is not the class of all graphs and this bound is linear. This is not just a curiosity – we know now that it reflects the structure proved by Robertson and Seymour in the graph minors structure theorem – the graphs in a proper minor-closed class are at most linearly dense because they are `almost’ embeddable on a fixed surface. Of course we didn’t know this in 1967, so it presented a question rather than a corroboration.

Moving on to matroids, we first define some convenient notation. For a matroid $M$, we write $\elem(M)$ for $|\mathrm{si}(M)|$ (equivalently the number of rank-$1$ flats of $M$); this stops us having to awkwardly talk about simple matroids all the time. For a minor-closed class $\cM$, we use $h_{\cM}(n)$ to denote the function whose value at an integer $n$ is the maximum of $\elem(M)$ over all matroids $M \in \cM$ whose rank is at most $n$. Some people call this the size function but I’ll call in the growth rate function. We allow $h_{\cM}(n) = \infty$ – indeed any class that contains $U_{2,k}$ for all $k$ will satisfy this for all $n \ge 2$. In the interesting cases this function is monotonely increasing without bound. For example, for the class $\cM$ of graphic matroids has growth rate function $h_{\cM}(n) = \binom{n+1}{2}$, and by Theorem 1 above, all of its proper subclasses have growth rate function at most linear in $n$.

The next few theorems will combine to divide minor-closed classes of matroids into four types, just as Theorem 1 divides classes of graphs into two. These theorems all concern `dichotomies’ in growth rate functions. The first, due to Kung [Kung91] distinguishes classes with finite growth rate functions from those with infinite growth rate function. We’ll even prove it, since the proof is so nice.

Theorem 2.  If $\cM$ is a minor-closed class of matroids, then either

• $h_{\cM}(n) = \infty$ for all $n \ge 2$, or
• there is some $\ell \ge 2$ such that $U_{2,\ell+2} \notin \cM$ and $h_{\cM}(n) \le \frac{\ell^n-1}{\ell-1}$ for all $n$.

Proof: If $U_{2,\ell+2} \in \cM$ for all $\ell \ge 2$ then the first outcome holds, so we may assume that $U_{2,\ell+2} \notin \cM$ for some $\ell \ge 2$, and will show that $\elem(M) \le \frac{\ell^r-1}{\ell-1}$ for each integer $r$. Let $M \in \cM$ be a rank-$r$ matroid and $e$ be a nonloop of $M$. Inductively we may assume that $\elem(M \con e) \le \frac{\ell^{r-1}-1}{\ell-1}$, and we know $M$ has $\elem(M \con e)$ lines containing $e$. Since $M$ has no $U_{2,\ell+2}$-minor, each of these lines has at most $\ell$ points other than $e$, so $\elem(M) \le \ell \elem(M \con e) + 1 \le \ell\frac{\ell^{r-1}-1}{\ell-1}+ 1 \le \frac{\ell^r-1}{\ell-1}$, as required.

This theorem tells us that there is no minor-closed class with finite growth rate function greater than exponential in $n$, and cleanly divides growth rate functions into the infinite and the finite. In fact, there is much more to the story than this; we’ll finish by stating the theorem that will be the focus of my next post. This theorem was conjectured by Kung [Kung91] and stated in [GKW09] as a consequence of various theorems of Geelen, Kabell, Kung and Whittle.

Growth Rate Theorem. If $\cM$ is a minor-closed class of matroids, then either

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

Again $c_{\cM}$ is always a real constant depending only on $\cM$. In other words, up to a constant, there are just four possible qualitative behaviours for growth rate functions: linear, quadratic, exponential and infinite. This is dramatic behaviour and deserves more consideration. See you next time!

References

• [GKW09] J. Geelen, J. P. S. Kung, and G. Whittle. Growth rates of minor-closed classes of matroids. J. Combin. Theory Ser. B, 99(2):420–427, 2009.
• [Kung91] J. P. S. Kung. Extremal matroid theory. In Graph structure theory (Seattle, WA, 1991), volume 147 of Contemp. Math., pages 21–61. Amer. Math. Soc., Providence, RI, 1993.
• [Mader67] W. Mader. Homomorphieeigenschaften und mittlere kantendichte von graphen. Mathematische Annalen, 174:265–268, 1967. 10.1007/BF01364272.