Growth Rates I

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

One thought on “Growth Rates I”

1. Thanks Peter, an excellent first contribution to the blog! I’m looking forward to the next part in this series.

This site uses Akismet to reduce spam. Learn how your comment data is processed.