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 graphic, SIAM 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.

Hello everyone – MatroidUnion is back!

Rudi and Jorn wrote a nice post earlier this year about questions in asymptotic matroid theory, and beautiful new results they’ve obtained in this area. While reading one of their papers on this topic, I saw that they restated the conjecture that almost all matroids on $n$ elements are non-representable. This was first explicitly written down by Mayhew, Newman, Welsh and Whittle [1] but earlier alluded to by Brylawski and Kelly [2] (in fact, the latter authors claim that the problem is an ‘exercise in random matroids’ but give no clue how to complete it). Indeed I would argue that most of us would independently come up with the same conjecture after thinking about these questions for a few minutes; surely representable matroids are vanishingly rare among all matroids!

In any case, reading this conjecture reminded me that, like many ‘obvious’ statements in asymptotic matroid theory it was still open, and seemed somewhat hard to approach with existing techniques. I’m happy to say that this is no longer the case; as it happened, I discovered a short proof that I will now give in this post. The proof is also on the arXiv [3]; there, it is written with the bounds as tight as possible. Here, I will relax the calculations a little here to make the proof more accessible, as well as using more elementary bounds so the entire argument is self-contained. The theorem we prove is the following:

Theorem: For $n \ge 10$, the number of representable matroids with ground set $[n] = \{1,\dotsc,n\}$ is at most $2^{2n^3}$.

The number of matroids on $n$ elements is well-known to be doubly exponential in $n$, so the above gives the ‘almost all’ statement we need, in fact confirming the intuition that representable matroids are extremely rare among matroids in general. The bound in the proof can in fact be improved to something of the form $2^{n^3(1/4 + o(1))}$, and I believe the true count has this form; see [3] for more of a discussion.

Our path to the proof is indirect; we proceed by considering a more general question on `zero-patterns’ of polynomials, in the vein of [4]. Let $f_1, \dotsc, f_N$ be integer polynomials in variables $x_1, \dotsc, x_m$. Write $\|f\|$ for the absolute value of the largest coefficient of a polynomial $f$, which we call its height; it is fairly easy to prove that $\|f + g\| \le \|f\| + \|g\|$ and that $\|fg\| \le \binom{\deg(f) + \deg(g)}{\deg(f)} \|f\|\ \|g\|$ for all $f$ and $g$. We will map these polynomials to various fields; for a field $\mathbb{K}$ and a polynomial $f$, write $f^{\mathbb{K}}$ for the polynomial in $\mathbb{K}[x_1, \dotsc, x_m]$ obtained by mapping each coefficient of $f$ to an element of $\mathbb{K}$ using the natural homomorphism $\phi\colon \mathbb{Z} \to \mathbb{K}$.

Given a field $\mathbb{K}$ and some $u_1, \dotsc, u_m \in \mathbb{K}$, the polynomials $f_i^{\mathbb{K}}(u_1, \dotsc, u_m)$ all take values in $\mathbb{K}$, and in general some will be zero and some nonzero in $\mathbb{K}$. We are interested in the number of different ways this can happen, where we allow both the field $\mathbb{K}$ and the $u_j$ to be chosen arbitrarily; to this end, we say a set $S \subseteq [N]$ is \realisable with respect to the polynomials $f_1, \dotsc, f_N$ if there is a field $\mathbb{K}$ and there are values $u_1, \dotsc, u_m \in \mathbb{K}$ such that \[S = \{i \in [N]: f^{\mathbb{K}}(u_1, \dotsc, u_m) \ne 0_{\mathbb{K}}\}.\] In other words, $S$ is realisable if and only if, after mapping to some field and substituting some values into the arguments, $S$ is the support of the list $f_1, \dotsc, f_N$. We will get to the matroid application in a minute; for now, we prove a lemma that bounds the number of different realisable sets:

Lemma: Let $c,d$ be integers and let $f_1, \dotsc, f_N$ be integer polynomials in $x_1, \dotsc, x_m$ with $\deg(f_i) \le d$ and $\|f_i\| \le c$ for all $i$. If an integer $k$ satisfies
\[ 2^k > (2kc(dN)^d)^{N\binom{Nd+m}{m}}, \] then there are at most $k$ realisable sets for $(f_1, \dotsc, f_N)$.

Proof: If not, then there are distinct realisable sets $S_1, \dotsc, S_k \subseteq [N]$. For each $i \in [k]$, define a polynomial $g_i$ by $g_i(x_1, \dotsc, x_m) = \prod_{j \in S_i}f_j(x)$. Clearly $\deg(g_i) \le Nd$, and since each $g_i$ is the product of at most $N$ different $f_i$, we use our upper bound on the product of heights to get
\[ \|g_i\| \le c^N \binom{dN}{d}^N (2kc’)^D\], so we have a collision – there exist distinct sets $I,I’ \subseteq [k]$ such that $g_I = g_I’$. By removing common elements we can assume that $I$ and $I’$ are disjoint.

Let $\ell \in I \cup I’$ be chosen so that $|S_{\ell}|$ is as small as possible. We can assume that $\ell \in I$. Since the set $S_{\ell}$ is realisable, there is a field $\mathbb{K}$ and there are values $u_1, \dotsc, u_m \in \mathbb{K}$ such that $S_{\ell} = \{i \in [N]: f_{\ell}^{\mathbb{K}}(u_1, \dotsc, u_m) \ne 0_{\mathbb{K}}\}$. So $g^{\mathbb{K}}_{\ell}$, by its definition, is the product of nonzero elements of $\mathbb{K}$, so is nonzero. For each $t \in I \cup I’ – \{\ell\}$, on the other hand, since $|S_t| \ge |S_\ell|$ and $S_t \ne S_\ell$ there is some $j \in S_t – S_\ell$, which implies that the zero term $f^{\mathbb{K}}_j(u_1, \dotsc, u_m)$ shows up in the product $g^{\mathbb{K}}_t(u_1, \dotsc, u_m)$. It follows from these two observations that
\[ 0_{\mathbb{K}} \ne g^{\mathbb{K}}_I(u_1, \dotsc, u_m) = g^{\mathbb{K}}_{I’}(u_1, \dotsc, u_m) = 0_{\mathbb{K}}, \] which is a contradiction.

Why is this relevant to representable matroids? Because representing a rank-$r$ matroid $M$ with ground set $[n]$ is equivalent to finding an $r \times n$ matrix $[x_{i,j}]$ over some field, for which the $r \times r$ determinants corresponding to bases of $M$ are nonzero and the other determinants are zero. In other words, a matroid $M$ is representable if and only if the set $\mathcal{B}$ of bases of $M$ is realisable with respect to the polynomials $(f_A \colon A \in \binom{[n]}{r})$, where $f_A$ is the integer polynomial in the $rn$ variables $[x_{ij} \colon i \in [r],j \in [n]]$ that is the determinant of the $r \times r$ submatrix of $[x_{ij}]$ with column set $A$. Thus, the number of rank-$r$ representable matroids on $n$ elements is the number of realisable sets with respect to these $f_A$.

To bound this quantity, we apply the Lemma, for which we need to understand the parameters $N,m,a,d$. Now $m = rn \le n^2$ is just the number of variables. $N = \binom{n}{r} \le 2^n$ is the number of $r \times r$ submatrices. (We can in fact assume that $N = 2^n$ and $m = n^2$ by introducing dummy polynomials and variables). Finally, since the $f_A$ are determinants, we have $\deg(f_A) = r \le n$ and $\|f_A\| = 1$ for all $a$, so $(N,m,c,d) = (2^n,n^2,1,n)$ will do. To apply the lemma, it suffices to find a $k$ for which
\[ 2^k > (2kc(dN)^d)^{N\binom{Nd+m}{m}}, \] or in other words, \[k > N\binom{Nd+m}{m}\log_2(2kc(dN)^d)).\] If you are happy to believe that $k = 2^{2n^3}/2n$ satisfies this, then you can skip the next two estimates, but for the sticklers among us, here they are:
Using $(N,m,d,c) = (2^n,n^2,n,1)$ and $n \ge 20$ we have \[N\binom{Nd+m}{m} \le 2^n(2^{n+1}n)^{n^2} = 2^{n^2(n+1 + \log_2(n)) + n} \le 2^{2n^3}/6n^4.\] (Here we need that $n^3 > n^2(1+\log_2 n) + n + \log_2(6n^4)$, which holds for $n \ge 10$.) Similarly, for $k = 2^{2n^3}/(2n)$ we have $2kc < 2^{2n^3}$, so
\[\log_2(2kc(dN)^d)) < \log_2(2^{2n^3}(n2^n)^n) < 2n^3 + n^2 + n \log_2 n < 3n^3.\] Combining these estimates, we see that $k = 2^{2n^3}/2n$ satisfies the hypotheses of the lemma, so this $k$ is an upper bound on the number of rank-$r$ representable matroids on $n$ elements. This is only a valid bound for each particular $r$, but that is what our extra factor of $2n$ was for; the rank $r$ can take at most $n+1$ values, so the number of representable matroids on $[n]$ in total is at most $(n+1)k < 2nk = 2^{2n^3}$. This completes the proof of the main theorem.

[1] D. Mayhew, M. Newman, D. Welsh, and G. Whittle, On the asymptotic proportion of connected matroids, European J. Combin. 32 (2011), 882-890.
[2] T. Brylawski and D. Kelly, Matroids and combinatorial geometries, University of North Carolina Department of Mathematics, Chapel Hill, N.C. (1980). Carolina Lecture Series
[3] P. Nelson, Almost all matroids are non-representable, arXiv:1605.04288 [math.CO]
[4] L. Rónyai, L. Babai and M. K. Ganapathy, On the number of zero-patterns of a sequence of polynomials, J. Amer. Math. Soc. 14 (2001), 717–735.

This post is about some conjectures on matroid minor structure theory in the most general setting possible: excluding a uniform matroid. Jim Geelen previously discussed questions in this area in [1], and most of what I write here comes from discussions with him.

Whether they be for graphs or matroids, qualitative structure theorems for minor-closed classes usually fit a particular template. They make a statement that the members of a minor-closed class are ‘close’ to having a particular basic structure, where the structure should be something that differs the graphs/matroids in the class from arbitrary/random ones. In the case of proper minor-closed classes of graphs, this structure takes the form of embeddability on a fixed topological surface, as was famously shown by Robertson and Seymour. For matroids representable over a fixed finite field, the structure arises from classes of group-labelled graphs that embed on a fixed topological surface, classes of group-labelled graphs in general, and (when the order of the field is non-prime) classes of matroids representable over a fixed subfield. These results for finite fields have been shown in recent years by Geelen, Gerards and Whittle, and have already given us powerful tools for understanding the matroids in minor-closed classes, as demonstrated most notably in their proof of Rota’s conjecture.

Extending graph minors structure theory to minor-closed classes of matroids over finite fields was no mean feat, but there is real reason to believe that we can generalise it further.  It seems unlikely that one could obtain very strong structural results for all minor-closed classes; for example, the class of sparse paving matroids (that is, the matroids whose girth is at least the rank and whose cogirth at least the corank) is minor-closed, and is conjectured to contain almost all matroids – intuitively, a structure theorem that allows us to ‘understand’ the class of sparse paving matroids seems unlikely. The sticking point here seems to be that this class contains all uniform matroids. At the moment, we think that one should be able to obtain sensible qualititative structure theorems precisely for the minor-closed classes that don’t contain all the uniform matroids. In this post, I’ll state a conjectures that makes this kind of statement. For this, we need two ingredients.

Basic Structures

We first need an idea which basic structures we expect to see as outcomes. These turn out to be pretty close to what goes on in the finite field representable case. Let $\mathcal{M}$ be a minor-closed class not containing all uniform matroids. Let $U$ be a uniform matroid not contained in $\mathcal{M}$. Without loss of generality, we may assume that $U = U_{s,2s}$ where $s \ge 4$, as every uniform matroid is a minor of a matroid of this form. Here are some examples of interesting classes that  $\mathcal{M}$ could be:

• The class of $\mathbb{F}$-representable matroids, where $\mathbb{F}$ is some finite field over which $U$ is not representable.
• The class of graphic matroids.
• The class of bicircular matroids. (These are the ‘graph-like’ matroids in which each edge element is placed freely on the line between two vertex elements).
• The class of frame matroids (i.e. the matroids of the form $M \backslash V$, where $V$ is a basis of a matroid $M$ for which every fundamental circuit has size at most two). This class contains both the previous ones, as well as various other graph-like matroids such as those arising from group-labelled graphs. $U_{4,8}$ is not a frame matroid and therefore neither is $U$.
• The class of duals of frame matroids. (Or graphic/bicircular matroids)
• A class of matroids arising (as graphic, cographic, bicircular, group-labelled-graphic, etc…)  from the class of graphs that embed on some surface.

Although they are not at all trivial from a graph-theoretic perspective, classes of the last type are less rich as they all have small vertical separations. Classes of the the other types, however, contain matroids of arbitrarily high vertical connectivity. Structural statements simplify a lot when they are made about highly connected matroids, and the main conjecture I’ll be stating will apply only to very highly vertically connected matroids in a given minor-closed class; the last type of class will therefore not show up.

The divide between the ‘highly connected’ minor-closed classes and other classes is made concrete by the following conjecture.

Conjecture 1. Let $\mathcal{M}$ be a minor-closed class of matroids not containing all uniform matroids. Either

• $\mathcal{M}$ contains the graphic matroids or their duals,
• $\mathcal{M}$ contains the bicircular matroids or their duals, or
• there is an integer $t$ so that $\mathcal{M}$ does not contain any vertically $t$-connected matroid on at least $2t$ elements.

Closeness 

We now need to say what, according to our structural conjecture, exactly is meant by two matroids being ‘close’. For minor-closed classes of graphs, ‘closeness’ is measured in terms of vortices, apex vertices, and clique-sums. For matroids over finite fields, the structure theory considers two matroids on the same ground set to be ‘close’ if they have representations that differ by a bounded-rank matrix. None of these ideas quite work for matroids in general, as we don’t have representations, let alone vertices. However, there is something that will.

A single-element projection of a matroid $M$ is a matroid $N$ for which there exists a matroid $L$ such that $L \backslash e = M$ and $L / e = N$. If $N$ is a single-element projection of $M$ then $N$ is a single-element lift of $M$. Single-element lifts and projections are dual notions that ‘perturb’ a matroid by a small amount to another matroid on the same ground set; for example, they change the rank and corank of any given set by at most $1$. We write $\mathrm{dist}(M,N)$ to denote the minimum number of single-element lifts and/or projections to transform $M$ into $N$. If this ‘distance’ is small, then $M$ and $N$ are ‘close’. This will serve as the notion of closeness in our structure conjecture. (In a more general structure theory, vortices will also arise). This distance only makes sense if $M$ and $N$ have the same ground set, if this is not the case, then we say $\mathrm{dist}(M,N) = \infty$.

Incidentally (and I’m looking at you, grad students), I would like an answer to the following question, which would simplify the notion of perturbation distance – I don’t have a good intuition for whether it should be true or false, and either way it could be easy.

Problem. Let $M$ and $N$ be matroids for which there exists a matroid $L$ that is a single-element lift of both $M$ and $N$. Does there exist a matroid $P$ that is a single-element projection of both $M$ and $N$?

The Conjecture

Here goes! If $\mathcal{M}$ is a minor-closed class not containing all uniform matroids, then the highly connected members of $\mathcal{M}$ should be close to being frame, co-frame, or representable.

Conjecture 2: Let $\mathcal{M}$ be a minor-closed class of matroids not containing a uniform matroid $U$. There is an integer $t \ge 0$ so that, if $M$ is a vertically $t$-connected matroid in $\mathcal{M}$, then there is a matroid $N$ such that $\mathrm{dist}(M,N) \le t$ and either

• $N$ is a frame matroid,
• $N^*$ is a frame matroid, or
• $N$ is representable over a field $\mathbb{F}$ for which $U$ is not $\mathbb{F}$-representable.

If true, this conjecture would tell us that minor-closed classes of matroids inhabit a very beautiful universe. The hypotheses are very minimal, applying to a massive variety of different $\mathcal{M}$. The conclusions, on the other hand, imply that all ‘nondegenerate’ members of $\mathcal{M}$ are at a small distance from a matroid $N$ that is very far from being generic. Somehow, as happens again and again in matroid theory, the ‘special’ classes of representable and graph-like matroids are in fact fundamental to understanding the minor order.

Conjecture 2 is one of the many goals of a more general matroid structure theory; in my next post I will discuss some recent progress we have made towards it.

Reference

[1] Some open problems on excluding a uniform matroid, J. Geelen, Adv. Appl. Math. 41 (2008), 628-637.