Growth Rates V

$\newcommand{\mcsigned}{\mathcal{G}^{\mathrm{sg}}}
\newcommand{\mcevencycle}{\mathcal{G}^{\mathrm{ec}}}
\newcommand{\mcfree}{\mathcal{G}^{\mathrm{tr}}}$
Hi everyone, happy new year and sorry for my recent absence/lateness!

Today I am going to say some things about growth rates of minor-closed classes, but in more concrete cases that I’ve been writing about previously. To recap on a definition that has come up many times on this blog, the growth rate function of a minor-closed class of matroids is the definition capturing the answer to a question that Joseph Kung called the ‘primary concern’ of extremal matroid theory: given a minor-closed class $\mathcal{M}$ of matroids, what is the maximum number of elements that a simple rank-$r$ matroid in $\mathcal{M}$ can have? For each nonnegative integer $n$, the growth rate function for $\mathcal{M}$ at $n$ is defined as follows:

$h_{\mathcal{M}}(n) = \max\{|M|: M \in \mathcal{M} \text{ simple}, r(M) \le n\}$.

For instance, for the class $\mathcal{G}$ is the class of graphic matroids we have $h_{\mathcal{G}}(n) = \binom{n+1}{2}$. In fact, the growth rate theorem [GKW09] says that every minor-closed class of matroids with finite growth rate function either has growth rate function in $O(n)$, or contains the graphic matroids (and therefore has growth rate function at least $\binom{n+1}{2}$ for all $n$). Thus, the graphic matroids have the smallest possible growth rate function that is not just linear in $n$.

There are other classes of matroids with growth rate function exactly $\binom{n+1}{2}$ for all $n$, or for all but a few $n$. They necessarily contain the graphic matroids, but can be strictly larger. Several were mentioned in a post by Irene last year; they include the regular matroids, and the class $\mathrm{Ex}(\mathrm{AG}(3,2))$ of binary matroids with no $\mathrm{AG}(3,2)$-minor. The former result was shown by Heller [H57] and the latter by Kung et al [KMPR13]. Given this (and Irene asked a question along these lines in her post), it is natural to ask for a characterisation of exactly which classes of matroids grow like the graphic ones:

Problem 1: Characterise the minor-closed classes of matroids $\mathcal{M}$ that satisfy $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all but finitely many $n$.

or, more concretely, we could ask to characterise the minors whose exclusion gives such a class:

Problem 2: Let $\mathcal{O}$ be a finite set of simple matroids and let $\mathcal{M} = \mathrm{Ex}(\mathcal{O})$ be the class of matroids with no minor in $\mathcal{O}$. Characterise when $\mathcal{M}$ satisfies $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all but finitely many $n$.

Nice Classes

This post will answer both these questions. Before I state the theorem that does this, I’ll give three examples of minor-closed classes that do grow faster than the graphic matroids.

  • The class $\mcevencycle$ of even cycle matroids having a signed graph representation with a blocking pair (that is, a pair of vertices through which all negative cycles pass). This class contains only binary matroids and has growth rate function $\binom{n+2}{3}-3$.
  • The class $\mcsigned$ of signed-graphic matroids having a signed graph representation with a vertex that is contained in every nonloop negative cycle. This class contains matroids representable over every field of odd order, and has growth rate function $\binom{n+2}{2}-2$
  • The class $\mcfree$ that is the union of the class of graphic matroids and the class of truncations of graphic matroids. There is no finite field over which every matroid in this class is representable, and it has growth rate function $\binom{n+2}{2}$.

The superscripts stand for ‘even cycle’, ‘signed graphic’ and ‘truncation’ respectively.  These are three ‘nice’ classes of matroids that are a bit bigger than the graphic matroids, all arising from well-known classes and constructions. The following theorem resolves Problem 1, and will also be enough to resolve 2.

Theorem 1 [GN14]: Let $\mathcal{M}$ be a minor-closed class of matroids with growth rate function in $\Theta(n^2)$. Either

  • $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all sufficiently large $n$, or
  • $\mathcal{M}$ contains one of $\mcevencycle$, $\mcsigned$, or $\mcfree$.

Note that this ‘or’ is really an ‘exclusive or’, since the latter outcome implies that $h_{\mathcal{M}}(n) \ge \binom{n+2}{2}-3$ for all $n \ge 4$ and therefore that the former outcome does not hold. This theorem gives a very nice answer for problem 1; the classes that grow like the graphic matroids are exactly those that do not contain any of three particular classes that are all too big.

To deal with Problem 2, we just need to understand which minors that $\mathcal{O}$ must contain in order that $\mathrm{Ex}(\mathcal{O})$ does not contain any of $\mcevencycle$, $\mcsigned$ or $\mcfree$. This is just saying that $\mathcal{O}$ should contain a matroid from each of these classes. The classes actually intersect, so a single matroid in $\mathcal{O}$ could serve a dual purpose. For $\mathrm{Ex}(\mathcal{O})$ to be quadratically dense, it is also necessary to have some rank-$2$ uniform matroid in $\mathcal{O}$ and no graphic matroid in $\mathcal{O}$. The answer to Problem 2 is therefore in the following corollary:

Corollary 1: If $\mathcal{O}$ is a finite set of simple matroids and $\mathcal{M} = \mathrm{Ex}(\mathcal{O})$, then the following two statements are equivalent:

  1. $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all sufficiently large $n$.
  2. $\mathcal{M}$ contains a rank-$2$ uniform matroid, contains no graphic matroids, and contains a matroid from each of $\mcevencycle$, $\mcsigned$ and $\mcfree$.

This solves the problem in general. We can also obtain specialisations to particular fields. The binary case (that is, where $U_{2,4} \in \mathcal{O}$) says the following:

Corollary 2: If $\mathcal{O}$ is a finite set of simple matroids and $\mathcal{M}$ is the set of binary matroids with no minor in $\mathcal{O}$, then the following two statements are equivalent:

  1. $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all sufficiently large $n$.
  2. $\mathcal{O}$ contains no graphic matroids, and contains a nongraphic matroid in $\mcevencycle$.

When $\mathcal{O} = \{\mathrm{AG}(3,2)\}$ we get (for large $n$) the aforementioned result of Kung et al. There is also a similar corollary for matroids over any fixed odd-order finite field, where $\mcevencycle$ is replaced by $\mcsigned$.

Future Work

Theorem 1 should just be the beginning of an effort to characterise quadratic growth rate functions completely. It would be really nice to answer the following question:

Problem 3: Which functions in $\Theta(n^2)$ can occur as growth rate functions?

It follows from Theorem 1 that any function strictly between $\binom{n+1}{2}$ and $\binom{n+2}{2}-3$ cannot. In general, a conjecture of Geelen, Gerards and Whittle [GGW14] suggests that all such functions are quadratic polynomials with half-integral leading coefficient. Matroid structure theory in [GGW14] should (with enough work) give the answer for classes over any fixed finite field, but I would love to know what can be done without appeals to structure theory, since we are probably a long way off full structure theorems for general matroids.

[H57] I. Heller, On linear systems with integral valued solutions, Pacific J. Math. 7 (1957), 1351-1364.

[GGW14] J. Geelen, B. Gerards and G. Whittle, The highly connected matroids in minor-closed classes, arXiv:1312.5102.

[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

[GN14] J. Geelen, P. Nelson, Matroids denser than a clique, arXiv:1409.0777

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

 

Leave a Reply

Your email address will not be published. Required fields are marked *