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 [1] 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 [2], 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 [3] 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 [4]; essentially we reduce Theorem 1 to the case where $M$ is very highly connected, then use the results in [4] 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 [2] 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 [5] 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:

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

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

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

[4] 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.

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

 

Google Summer of Code

Aside

I’m happy to announce that SageMath’s matroid functionality will be improved again this summer: Zach Gershkoff, a PhD student at Louisiana State University, will work on a dedicated Graphic Matroid class, among other improvements. See the project overview here.

This marks the fourth year in a row that a Matroid project was selected by SageMath for the Google Summer of Code program. Previous participants are Tara Fife, Chao Xu, and Jayant Apte.