# The densest matroids without a given projective geometry minor

This post is about some work done in collaboration with my graduate student Zachary Walsh. The problem is a simple one, and is the binary matroid analogue of a question studied by Thomason  about the edge-density of graphs with no $K_t$-minor. He shows that a simple graph on $n$ vertices without a $K_t$-minor has at most $\alpha(t)n$ edges, where $\alpha(t)$ is a best-possible constant depending only on $t$ that has the order of $t \sqrt{\log t}$. Determining this order exactly is no mean feat, but a disappointing reality is that the extremal examples are random graphs – in other words, there is no nice explicit construction for graphs that are as dense as possible with no $K_t$-minor. Because of this, tightening the upper bound of $\alpha(t)n$ to a specific function of $n$ and $t$ seems near-impossible.

The analogous question for matroids is much more pleasant. We’ll stick to binary matroids here, but in , we prove versions of theorem I discuss for all prime fields. For binary matroids, projective geometries play the same role that cliques do in graphs. Our main theorem is the following:

Theorem 1: Let $t$ be a nonnegative integer. If $n$ is sufficiently large, and $M$ is a simple rank-$n$ binary matroid with no $\mathrm{PG}(t+2,2)$-minor, then $|M| \le 2^t\binom{n+1-t}{2} + 2^t-1$. Furthermore, there is a unique simple rank-$n$ binary matroid for which equality holds.

Unlike for graphs, we can write down a nice function. Note that for $t = 0$, the function above is just $\binom{n+1}{2}$; in fact, in this case, the cycle matroid of a clique on $n+1$ vertices is the one example for which equality holds and in fact the result specialises to an old theorem of Heller  about the density of matroids without an $F_7$-minor. This was the only previously known case.

The case for $t = 1$ was conjectured by Irene in her post from 2014. Irene also conjectured the extremal examples; they are all even cycle matroids. These can be defined as the matroids having a representation of the form $\binom{w}{A}$, where $A$ is a matrix having at most two nonzero entries per column, and $w$ is any binary row vector. The largest simple rank-$n$ even cycle matroids can be shown to have no $\mathrm{PG}(3,2)$-minor and have $2\binom{n}{2}-1$ elements; this agrees with the expression in our theorem for $t = 1$.

These first two examples suggest a pattern allowing us to construct the extremal matroids more generally; we want a matrix with $n$ rows and as many columns as possible, having distinct nonzero columns, that is obtained from a matrix with at most two nonzero entries per column by appending $t$ rows. For a given column, there are $2^t$ choices for the first $t$ entries, and $\binom{n-t}{0} + \binom{n-t}{1} + \binom{n-t}{2}$ for the last $n-2$ (as we can choose zero, one or two positions where the column is nonzero). Since we can’t choose the zero vector both times, the total number of possible columns is $2^t(\binom{n-t}{0} + \binom{n-t}{1} + \binom{n-t}{2})-1 = 2^t\binom{n-t+1}{2} + 2^t-1$, the bound in our theorem. Let’s call this maximal matroid $G^t(n)$. Note that $G^0(n)$ is just the cycle matroid $M(K_{n+1})$

We can prove by induction that $G^t(n)$ has no $\mathrm{PG}(t+2,2)$-minor; the $t = 0$ case is obvious since $\mathrm{PG}(2,2)$ is nongraphic. Then, one can argue that appending a row to a binary representation of a matroid with no $\mathrm{PG}(k,2)$-minor gives a matroid with no $\mathrm{PG}(k+1,2)$-minor; since (for $t > 1$) $G^{t}(n)$ is obtained from $G^{t-1}(n-1)$ by taking parallel extensions of columns and then appending a row, inductively it has no $\mathrm{PG}(t+2,2)$-minor as required.

All I have argued here is that equality holds for the claimed examples. The proof in the other direction makes essential use of the structure theory for minor-closed classes of matroids due to Geelen, Gerards and Whittle ; essentially we reduce Theorem 1 to the case where $M$ is very highly connected, then use the results in  about matroids in minor-closed classes that have very high connectivity to argue the bound. I discussed a statement that uses these structure theorems in similar ways back in this post.

We can actually say things about excluding matroids other than just projective geometries. The machinery in  also gives a result about excluding affine geometries:

Theorem 2: Let $t \ge 0$ be an integer and $n$ be sufficiently large. If $M$ is a simple rank-$n$ binary matroid with no $\mathrm{AG}(t+3,2)$-minor, then $|M| \le 2^t\binom{n+1-t}{2} + 2^t-1$. Furthermore, if equality holds, then $M$ is isomorphic to $G^t(n)$.

This was proved for $t = 0$ in  but was unknown for larger $t$. Again, the examples where equality holds are these nice matroids $G^t(n)$. Our more general result characterizes precisely which minors we can exclude and get similar behaviour. To state it, we need one more definition. Let $A$ be the binary representation of $G^t(n+1)$ discussed earlier (where each column has at most two nonzero entries in the last $n+1-t$ positions) and let $A’$ be obtained from $A$ by appending a single column, labelled $e$, whose nonzero entries are in the last three positions. Let $G^t(n)’$ be the simplification of $M(A’) / e$; so $G^t(n)’$ is a rank-$n$ matroid obtained by applying a single `projection’ to $G^t(n+1)$. I will conclude by stating the most general version of our theorem for binary matroids; with a little work, it implies both the previous results.

Theorem 3: Let $t \ge 0$ be an integer and $N$ be a simple rank-$k$ binary matroid. The following are equivalent:

• For all sufficiently large $n$, if $M$ is a simple rank-$n$ binary matroid with no $N$-minor, then $|M| \le 2^t\binom{n+1-t}{2} + 2^t-1$, and $M \cong G^t(n)$ if equality holds.
• $N$ is a restriction of $G^t(k)’$ but not of $G^t(k)$.

References:

 A. Thomason: The extremal function for complete minors, J. Combinatorial Theory Ser. B 81 (2001), 318–338.

 P. Nelson, Z. Walsh, The extremal function for geometry minors of matroids over prime fields, arXiv:1703.03755 [math.CO]

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

 J. Kung, D. Mayhew, I. Pivotto, and G. Royle, Maximum size binary matroids with no AG(3,2)-minor are graphicSIAM J. Discrete Math. 28 (2014), 1559–1577.

 J. Geelen, B. Gerards and G. Whittle, The highly connected matroids in minor-closed classes, Ann. Comb. 19 (2015), 107–123.