$\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 [2] 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 [2]: 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 [1]) 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!

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

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

$\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.

Somewhat ironically for a ten-day-late blog post, I’ll be writing today about regularity.

This post has something of quite a different flavour from my previous posts – we’ll be discussing an analogue of Szemeredi’s regularity lemma for binary matroids. All our matroids today are simple and binary. As with the regularity lemma for graphs, though, it would be a mistake to just state the result without motivation; so we’ll discuss it in the context of trying to prove the following theorem:

Theorem 1: For all $\alpha > 0$ there exists $c \in \mathbb{N}$ such that, if $M$ is a simple binary matroid with $|M| \ge \alpha 2^{r(M)}$ and with no $C_5$-restriction, then $M$ has critical number at most $c$.

The critical number (usually called critical exponent) of a binary matroid $M$, viewed as a restriction of some projective geometry $G \cong \mathrm{PG}(n-1,2)$, is the minimum $t \ge 0$ such that $G$ has a rank-$(n-t)$ flat disjoint from $E(M)$. This doesn’t depend on the choice of $G$, giving the same $t$ even when $n > r(M)$. Critical number looks a bit strange but is actually a close analogue of chromatic number, which is why I’ve dropped the term ‘exponent’.

For example, for a graph $G$, the critical number of $M(G)$ is $1$ if and only if $G$ is bipartite. In general, the matroids of critical number $1$ are the restrictions of an affine geometry. Having bounded critical number is quite a strong constraint on a binary matroid with exponentially many elements, so Theorem 1 is a nice result. The analog for graphs, which says that every $C_5$-free graph $G$ with minimum degree at least $\alpha |V(G)|$ for $\alpha > 0$ has chromatic number bounded by a function of $\alpha$, was proved by Thomassen [3] in 2007.

The regularity lemma for graphs says, very roughly, that for every graph $G$, the vertex set $V(G)$ admits a partition into a bounded number of blocks of nearly equal size, so that nearly every pair of blocks induces a pseudorandom bipartite graph. Less roughly, the lemma that for all $\epsilon > 0$ and $m \in \mathbb{N}$, there is some $M$ such that every graph $G$ has a partition $(V_1, \dotsc, V_s)$ of its vertex set such that $s \le M$,  $|V_i|-|V_j| \le 1$ for each $i$ and $j$, and all but $\epsilon \binom{s}{2}$ of the pairs $i,j$ have the property that the bipartite graph consisting of the edges between $V_i$ and $V_j$ is $\epsilon$-uniform, which is some measure of randomness that gets stronger for smaller $\epsilon$; I’ll leave it undefined for graphs.

To state the regularity lemma for binary matroids, we first need to define a notion of pseudorandomness for sets of binary vectors. Let $X \subseteq V = \mathrm{GF(2)}^n$. For each codimension-$1$ subspace $H$ of $V$, note that $|V – H| = |H|$. A truly random subset of $V$ would therefore have roughly as many elements in $H$ as it does in $V – H$. We use this idea to define what we mean by pseudorandom; a set $X \subseteq V$ is $\epsilon$-uniform in $V$ if $| |X \cap H| – |X \cap (V -H)| | \le \epsilon|V|$. This definition turns out to have a natural interpretation in discrete Fourier analysis, but we won’t need to worry about that at all. We can now state the regularity lemma! This lemma was proved by Ben Green in a 2003 paper [1]. In fact, he does this in a much more general setting of finite abelian groups, but to his infinite credit he holds the reader’s hand and makes the much simpler $\mathrm{GF}(2)^n$ case its own section at the beginning. I’ll modify the lemma statement to be as concrete as I can, giving a statement about the entries of an actual binary matrix. Let $0 \le s \le r$ and let $W \in \mathrm{GF(2)}^{[r] \times E}$ be a matrix. For each vector $u \in \mathrm{GF}(2)^s$, let $W_u$ be the set of vectors $v \in \mathrm{GF}(2)^{r-s}$ such that $\binom{u}{v}$ is a column of $W$. For example, $W_{(1,1,0)}$ is the set of columns of $W$ whose first three entries are $(1,1,0)$, after the first three entries have been removed. Here’s the regularity lemma:

Green’s Regularity Lemma: For all $\epsilon > 0$, there exists $c \in \mathbb{N}$ such that, if $M$ is a binary matroid, then there is an integer $s \le c$ and a representation $W$ of $M$ with $r(M)$ rows such that $W_u$ is an $\epsilon$-regular for all but an $\epsilon$-fraction of $u \in \mathrm{GF}(2)^s$.

So, say $s = 4$ and $\epsilon = 1/16$ – this conclusion would mean that of the $16$ sets $W_{(0,0,0,0)}, W_{(0,0,0,0)}, \dotsc, W_{(1,1,1,1)}$, all but at most $16\epsilon = 1$ of them are $(1/16)$-uniform. So, just like the graph regularity lemma more or less partitions the edge set of a graph into random sets, the above lemma does this for binary matroids.

But how do we use $\epsilon$-uniformity? It is supposed to represent randomness, and there is a useful concrete way that it does: suppose $A$ is a truly random subset of $V = \mathrm{GF}(2)^n$ with $|A| = \alpha 2^n$, and let $x_0 \in \mathrm{GF}(2)^n$. We would expect around $\alpha^4 2^{3n}$ solutions $(a_1,a_2,a_3,a_4)$ to $a_1 + a_2 + a_3 + a_4 = v_0$, where $a_i \in A$ for each $i$. The great thing about uniform sets is that this estimate isn’t far off:

Sum Lemma: Let $\epsilon > 0$ and $A \subseteq V = \mathrm{GF}(2)^n$ be $\epsilon$-uniform set with $|A| = \alpha 2^n$. For each $x_0 \in \mathrm{GF}(2)^n$, the equation $a_1 + a_2 + a_3 + a_4 = x_0$ has at least $(\alpha^4 – \epsilon)2^{3n}$ solutions.

The above lemma, as well as essentially appearing in Green’s paper, appears in the textbook Additive Combinatorics of Tao and Vu [2]; we care about it because sets summing to zero are matroid circuits, so in an appropriate matroid, the above lemma tells us about $5$-circuits.

Amazingly, the regularity lemma and the sum lemma basically give Theorem 1 with very little work. Here goes:

Proof of Theorem 1: Let $\alpha > 0$ and $M$ be a simple $C_5$-free binary matroid with $|M| \ge \alpha 2^{r(M)}$. Let $\epsilon = \frac{1}{32} \alpha^4$. By Green’s regularity lemma, there is some $s \le c(\alpha,\epsilon)$ and a representation $W$ of $M$ such that $W_v$ is $\epsilon$-uniform for all but $\epsilon 2^s$ values of $v \in \mathrm{GF}(2)^s$. We argue that $M$ has critical number at most $s$. If $W_0$ is empty, then there is clearly a codimension-$s$ subspace of $\GF(2)^{r(M)}$ containing no column of $W$, so $M$ has critical number at most $s$ and we’re done. Otherwise, let $x_0 \in W_0$.

Since $\sum_{v \in \mathrm{GF}(2)^s} |W_v| = |M| \ge \alpha 2^{r(M)}$, and at most an $(\epsilon < \frac{\alpha}{2})$-fraction of the $W_v$ are not $\epsilon$-uniform, it follows that some $W_v$ satisfies $|W_v| \ge \frac{\alpha}{2} 2^{r(M)-s}$, and is also $\epsilon$-uniform. By the sum lemma, there are at least $\left(\left(\frac{\alpha}{2}\right)^4 – \epsilon\right) 2^{r(M)-s} > 0$ solutions to $w_1 + w_2 + w_3 + w_4 = x_0$ where $w_1,w_2,w_3,w_4 \in W_v$. Looking back at the matrix, we see that the columns corresponding to $w_1,w_2,w_3,w_4$ and $x_0$ form a $5$-element circuit of $M$, a contradiction.

Caveat – The last sentence is a bit of a lie, since it could be, for example, that $w_1 = w_2$ and $(w_3,w_4,x_0)$ gives a triangle of $M$, but it is actually easy to show that negligibly few of the solutions to $w_1 + w_2 + w_3 + w_4 = x_0$ can have this kind of degenerate form, so we can find a $5$-element circuit for sure.

Thus, the regularity lemma gave us pseudorandomness, and pseudorandomness gave us a plethora of $5$-circuits. What is great is that we received these techniques on a silver platter – when we started thinking about these questions and realised an analogue of the regularity lemma was vital, we were quite happy to find that it had already been done. At the moment, we’ve got a couple more applications of these ideas, which I will perhaps write about in a future post. In the meantime, our paper with the above proof is on the arxiv at http://arxiv.org/pdf/1403.1617.pdf – I tried to write it in a way that is friendly to matroid theorists, and it gives a bit more context motivating Theorem 1. See you next time!

[1] B. Green, A Szemeredi-type regularity lemma in abelian groups, with applications, Geometric & Functional Analysis GAFA 15 (2005), 340-376.

[2] T. C. Tao and V. H. Vu, Additive Combinatorics, Cambridge Studies in Advanced Mathematics,  105, Cambridge University Press, Cambridge (2006).

[3] C. Thomassen, On the chromatic number of pentagon-free graphs of large minimum degree, Combinatorica 27 (2007), 241-243

Hi everyone,

Since Jim’s entries have been on other topics, I thought I’d take advantage of his modesty and use this entry to direct people’s attention to what I consider a very important paper he recently wrote with Bert Gerards and Geoff Whittle:

‘The highly connected matroids in minor-closed classes’,

This paper will appear in the special issue of Annals of Combinatorics for James Oxley, but currently can be found at http://arxiv.org/abs/1312.5012 .

The paper is the first to put in writing some of the amazing structure theorems for $\mathrm{GF}(q)$-representable matroids that the authors have proved on their way to Rota’s conjecture. The theorems aren’t proved in the paper, nor stated in their full generality; however, they are stated for the important special cases of highly vertically connected matroids. Incredibly, the authors give (among other things) an exact structure theorem for all sufficiently highly connected matroids in an arbitrary minor-closed class of $\mathrm{GF}(q)$-representable matroids.

Even though the high connectivity simplifies the structure theorem statements enormously, there are still some technical aspects. Nonetheless, I think this paper should give the community an important head-start on proving some theorems, in a way I will try to explain by sketching a proof of a conjecture in the paper that Stefan van Zwam and I recently came up with. Our write-up is mostly done and should be on the arxiv in the next few weeks.

The discussion in this post won’t use the ‘exact’ results stated in section 4, merely the more digestible ‘qualitative’ ones in section 3. First, here is Theorem 3.1 in the paper, stated for binary matroids. (We’ll stick with binary in this post.)

Theorem 1: Let $\mathcal{M}$ be a proper minor-closed class of binary matroids.  There exist integers $k$ and $t$ so that every vertically $k$-connected matroid in $\mathcal{M}$ is a rank-$(\le t)$ perturbation of a graphic or cographic matroid.

Here, a rank-$(\le t)$ perturbation of a binary matroid $N$ means a matroid of the form $M(A + T)$, where $A$ and $T$ are binary matrices such that $M(A) \equiv N$ and $T$ has rank at most $t$.

To get a feel for this theorem, consider the class of regular matroids, where it holds for $k = 5$ and $t = 0$; ie. the vertically $5$-connected regular matroids are either graphic or cographic. For general classes, the highly connected matroids are a bounded perturbation of graphic or cographic (as opposed to exactly (co)graphic), but this is often good enough to prove theorems.

The result we will prove is Conjecture 6.1 from the paper.. In the paper we’re writing, we have to make a bit of a song and dance about the exact correspondence between linear codes and matroids, but I’ll make this as brief as possible, just talking in terms of matroids.

We say a class $\mathcal{M}$ of binary matroids is asymptotically good if there exists $\delta > 0$ and a sequence $M_1,M_2, \dotsc, $ of matroids in $\mathcal{M}$ of increasing size such that for each $i$ the matroid $M_u$ satisfies $|M_i| \ge (1+\delta)r(M_i)$ and has no circuit of size less than $\delta |M_i|$. (Loosely, in coding theory terms, this corresponds to a sequence of codes of increasing size, all having reasonably large rate and minimum distance). The class of all binary codes is asymptotically good; choosing each $M_n$ to correspond to a random $n \times n$ binary matrix will work. On the other hand, Kashyap [3] proved the following:

Theorem 2: The classes of graphic and cographic matroids are not asymptotically good.

Our result generalises this to all proper minor-closed classes.

Theorem 3: No proper minor-closed class of binary matroids is asymptotically good.

Proving Theorem 3

Our goal is to prove Theorem 3 from Theorem 1. We do this in three steps, which together are a broad template for using the structure theorems in other ways, even though what I am discussing is going towards a specific result. The basic idea is this: suppose that we want to to prove that all large matroids in a proper minor-closed classes of binary matroids have property P. For all integers $t$ and $k$, we do the following:

1. Prove that it suffices to prove Theorem X for the subclass of vertically $k$-connected matroids in $\mathcal{M}$.
2. Prove a strong version of Theorem X for graphic and cographic matroids; call this Theorem Y.
3. Using Theorem Y, prove that Theorem X holds for the rank-$(\le t)$ perturbations of graphic and cographic matroids.

Together with Theorem 1, these steps imply that Theorem X holds for $\mathcal{M}$. – I’ll leave that deduction as an exercise. In our case, Theorem X is the statement that the class $\mathcal{M}$ is asymptotically good.

Step 1: Connectivity reduction
First, we bootstrap our way up to vertical $k$-connectivity via the following Lemma.

Lemma 4: Let $k$ be an integer. If $\mathcal{M}$ is asymptotically good, then so is the class of vertically $k$-connected matroids in $\mathcal{M}$.

This involves thinking about how very small separations in a matroid interact with small circuits. Like with most of these things, the numbers are fiddly, but in the end small vertical separations ought not to show up in a ‘best’ sequence certifying asymptotic goodness of $\mathcal{M}$, and the numbers bear this out. Now on to the next step…

Step 2: Graphic and Cographic

We saw earlier that Kashyap proved that the graphic and cographic matroids are not asymptotically good classes. We need something stronger, though: a result that can survive a perturbation. What we prove is the following:

Lemma 5: If $M$ is a graphic or cographic matroid with $|M| \ge (1+\delta)r(M)$, then there is a set $X \subseteq E(M)$ with $r_M(X) < |X| – 2t$ and $|X| = O(\log r(M))$.

The cographic case is very easy (the associated graph has constant average degree, so just take the union of a collection of small stars). The graphic case follows from a result of Alon, Hoory and Linial [1] which finds a single circuit of logarithmic size – if we apply this $(2t+1)$ times after removing the circuits successively, we get our required set. Finally…

Step 3: Surviving a perturbation

We constructed Lemma 5 to still give us a result when $M$ is perturbed. The following is an easy exercise:

Lemma 6: If $M$ is a rank-$(\le t )$ perturbation of $M’$, then $|r_M(X) – r_{M’}(X)| \le 2t$ for each $X \subseteq E(M)$.

From this and Lemma 5 (and a tiny bit of fudging with changing the rank of the matroid), we get what we want:

Lemma 7: If $M$ is a rank-$(\le t)$ perturbation of a graphic or cographic matroid and $|M| \ge (1+ \delta)|M|$, then there is a set $X \subseteq E(M)$ with $r_M(X) < |X|$ and $|X| = O(\log r(M))$.

And now we’re done – here’s the argument. Suppose that $\mathcal{M}$ is an asymptotically good minor-closed class of binary matroids. Let $k$ and $t$ be the integers given by Theorem 1. By Lemma 4, the class of vertically $k$-connected matroids in $M$ is asymptotically good. By Theorem 1, every such matroid is a rank-$(\le t)$ perturbation of graphic or cographic. By Lemma 7, any such matroid with $|M| \ge (1+ \delta)r(M)$ contains a dependent set of logarithmic size; this contradicts the definition of asymptotic goodness.

I hope this post has given you some idea of the power of the structure theorems in this paper. Being able to apply our knowledge of graphic and cographic matroids to arbitrary minor-closed classes of binary matroids is a huge boon, one that certainly deserves our attention. I haven’t even discussed nonbinary matroids or the exact structural results – maybe I’ll get to the latter in my next post. Until then, I’ll see you round!

[1] N. Alon, S. Hoory and N. Linial, The Moore bound for irregular graphs, Graphs Combin. 18 (2001), 53-57.

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

[3] N. Kashyap, A decomposition theory for binary linear codes, IEEE Transactions on Information Theory 54 (2008), 3035-3038.