# Growth Rates VI

$\newcommand{\PG}{\text{PG}}$

Denser than a Geometry

Hello everyone. In my last post, I discussed an unavoidable minor theorem for large matroids of density greater than $\binom{n+1}{2}$, which as a consequence characterised exactly the minor-closed classes of matroids that grow like the the graphic matroids. Today I’ll write about the exponential analogue of this problem; this appears in a paper of mine  available on the arXiv, and I will also be speaking on this topic at the matroid session of the upcoming CanaDAM conference in Saskatchewan.

I’ll first state a nice theorem of Kung, specialized to prime powers:

Theorem: If $q$ is a prime power, and $M$ is a simple rank-$n$ matroid with $|M| > \frac{q^n-1}{q-1}$, then $M$ has a $U_{2,q+2}$-minor.

This is certainly an important theorem – it says that if $M$ has too many elements to be a projective geometry over GF$(q)$, then $M$ has a rank-$2$ minor with the same property. However, if $n$ is large then this is somewhat unsatisfying, as the $U_{2,q+2}$-minor has constant size, and does not really ‘explain’ why $M$ is so dense. We would like a similar theorem that, instead of finding a $U_{2,q+2}$-minor, finds an unavoidable minor whose size grows with $n$.

What should such a minor be? That is, what are the large matroids that are ‘canonically’ denser than a projective geometry over GF$(q)$?

The first example is easy; rank-$2$ matroids can contain arbitrarily many elements, so the uniform matroid $U_{2,t}$ for some large $t$ must appear as an outcome. The direct sum of $U_{2,q^n}$ and $U_{n-2,n-2}$, for example, is a rank-$n$ matroid with more elements than $\PG(n-1,q)$, and essentially no more interesting structure.

Another matroid denser than $\PG(n-1,q)$ is simply a projective geometry $\PG(t-1,q’)$ over finite field GF$(q’)$.with $q’ > q$. This is our second outcome.

The next two outcomes are more interesting. An obvious way to construct a matroid denser than $\PG(n-1,q)$ is to perform a single-element extension. By modularity, every extension of $\PG(n-1,q)$ consists of adding a point freely to some flat $F$. The smallest simple case is where $F$ is a line: we write $\PG^{\mathrm{line}}(n-1,q)$ for the matroid formed by adding a point freely to a line of $\PG(n-1,q)$. The ‘largest’ case is when $F$ is the entire ground set, so the extension is free. We write $\PG^{\mathrm{free}}(n-1,q)$ for this matroid. The matroids $\PG^{\mathrm{line}}(m-1,q)$ and $\PG^{\mathrm{free}}(n-1,q)$ coincide for $n = m = 2$, but are not minors of eachother for any $m,n \ge 3$; they will thus occur as separate outcomes in our theorem. On the other hand, it is not hard to show that any simple extension of $\PG(2n-1,q)$ has one of $\PG^{\mathrm{line}}(n-1,q)$ or $\PG^{\mathrm{free}}(n-1,q)$ as a minor; thus, no further single-element extensions are needed as outcomes. Here is the theorem.

Theorem 1 : For every prime power $q$ and all $t \ge 3$, there exists $n \in \mathbb{Z}$ so that, if $M$ is a simple matroid with rank at least $n$ and $|M| > \frac{q^{r(M)}-1}{q-1}$, then $M$ has a minor isomorphic to one of the following:

•  $U_{2,t}$,
• $\PG(t-1,q’)$ for some $q’ > q$,
• $\PG^{\mathrm{free}}(t-1,q)$, or
• $\PG^{\mathrm{line}}(t-1,q)$.

Like in the quadratic case, we can apply this theorem to identify minor-closed classes that grow no faster than the GF$(q)$-representable matroids. For instance, if $q’$ is the next prime power after $q$, and $\ell$ is an integer so that $q \le \ell < q’$, then, for $t = \ell+2$, all four of the above minors can be shown to contain a $U_{2,\ell}$-minor. We thus have the following:

Corollary 1: Let $q$ and $q’$ be consecutive prime powers and $\ell$ be an integer so that $q \le \ell < q’$. If $M$ is a simple matroid with sufficiently large rank and no $U_{2, \ell+2}$-minor, then $|M| \le \frac{q^{r(M)}-1}{q-1}$.

Spikes and Swirls

Let $X = \{x_1,\dotsc,x_t\}$ and $Y = \{y_1, \dotsc, y_t\}$ be disjoint $t$-element sets. A rank-$t$ free spike is the matroid $\Lambda_t$ with ground set $X \cup Y$ whose non-spanning circuits are exactly the four-element sets of the form $\{x_i,x_j,y_i,y_j\}$ for $i \ne j$. The rank-$t$ free swirl is the matroid $\Delta_t$ with ground set $X \cup Y$ whose non-spanning circuits are exactly the four-element sets $\{x_i,x_{i+1},y_i,y_{i+1}\}$, where addition is modulo $t$.  Both free spikes and free swirls arise as pathologies in matroid representation theory.

Let $q \ge 3$ be a prime power and let $t \ge 3$. One can show (see ) that

• $\Lambda_t$ is GF$(q)$-representable if and only if $q$ is non-prime or $t \le q-2$.
• $\Delta_t$ is GF$(q)$-representable if and only if $q-1$ is non-prime or $t \le q-3$.

Using this, one can hunt for free spikes and swirls in the list of unavoidable minors in Theorem 1. There is a bit of case analysis to see what theorems fall out, but we get a few different corollaries that give upper bounds on the densities of matroids with out line-, spike-, and/or swirl-minors. All of the upper bounds in these corollaries are the densities of projective geometries, and are best-possible because the geometries themselves are tight examples.

Corollary 2: Let $\ell \ge 2$ and $t \ge 3$ be integers. If $M$ is a matroid of sufficiently large rank with no $U_{2,\ell+2}$-minor and no $\Lambda_t$-minor, then $|M| \le \frac{p^{r(M)}-1}{p-1}$.

Corollary 3: Let $\ell \ge 3$ and $t \ge 3$ be integers. If $M$ is a matroid of sufficiently large rank with no $U_{2,\ell+2}$-minor, no $\Lambda_t$-minor and no $\Delta_t$-minor, then $|M| \le \tfrac{1}{2}(3^{r(M)}-1)$.

The next corollary mostly tells you how dense a matroid can be if you exclude a line and a free swirl has a minor. However, it weirdly fails to apply to some $\ell$ because of the oddness of representation of free swirls. The only fields that can’t represent free swirls are are the ones of order $2^p$, where $2^p-1$ is prime. A prime of the form $2^p-1$ for another prime $p$, like $2^3 – 1 = 7, 2^5 – 1 = 31$ or $2^7 – 1 = 127$, is a Mersenne prime; it is not even known if there are infinitely many.

Corollary 4: Let $2^p-1$ and $2^{p’}-1$ be consecutive Mersenne primes, and let $k$ and $\ell$ be integers so that $2^p \le \ell < \min(2^{2p} + 2^p, 2^{p’})$ and $k \ge \max(3,2^p-2)$. If $M$ is a simple matroid of sufficiently large rank with no $U_{2,\ell+2}$ or $\Delta_k$-minor, then $|M| \le \frac{2^{pr(M)}-1}{2^p-1}$.

This fails to apply to some $\ell$, but only if $\ell$ is (roughly) greater than the square of a Mersenne prime but smaller than the next Mersenne primes. The first pair of Mersenne primes this far apart are $2^{127}-1$ and $2^{521}-1$, so for some $\ell$ around this size, the above corollary says nothing. The actual fact of the matter depends on the very poorly understood distribution of the Mersenne primes, so I don’t expect much improvement there in the near future.

Thanks, and see you next time!

 J Geelen, J.G. Oxley, D. Vertigan, G. Whittle, Totally free expansions of matroids, J. Combin. Theory. Ser. B 84 (2002), 130-179.

 P. Nelson,  Matroids denser than a projective geometry, to appear, SIAM Journal on Discrete Mathematics.

## One thought on “Growth Rates VI”

1. Tara Fife on said:

It looks like the less than or equal to sign in pointing the wrong way in the first theorem.

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