$\\newcommand{\\cG}{\\mathcal{G}}$\u00a0$\\newcommand{\\cM}{\\mathcal{M}}$\u00a0$\\newcommand{\\elem}{\\varepsilon}$ $\\newcommand{\\con}{\/}$ $\\newcommand{\\del}{\\!\\backslash\\!}$<\/p>\n
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]:<\/p>\n
Theorem 1.\u00a0<\/em><\/strong>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$.<\/em><\/p>\n 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;\u00a0<\/em>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.<\/p>\n 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<\/em> but I’ll call in the\u00a0growth rate function.<\/em>\u00a0We allow $h_{\\cM}(n) = \\infty$ – indeed any class that contains $U_{2,k}$ for all $k$ will satisfy this for all $n \\ge 2$.\u00a0<\/em>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$.<\/p>\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.<\/p>\n Theorem 2.<\/strong>\u00a0\u00a0<\/i>If $\\cM$ is a minor-closed class of matroids, then either<\/p>\n Proof:\u00a0<\/strong>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.<\/p>\n 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.<\/p>\n Growth Rate Theorem.\u00a0<\/strong>If $\\cM$ is a minor-closed class of matroids, then either<\/p>\n 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!<\/p>\n References<\/strong><\/p>\n $\\newcommand{\\cG}{\\mathcal{G}}$\u00a0$\\newcommand{\\cM}{\\mathcal{M}}$\u00a0$\\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 … Continue reading \n
\n
\n