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

Peter Nelson has been discussing Growth Rates of matroids (in aptly named posts Growth Rates I, II, III and IV). Following his notation, I will denote by $\epsilon(M)$ the number of points of a matroid $M$ (i.e. the number of elements in the simplification of $M$). Deviating just slightly from Peter’s notation, I’ll denote by $h(\mathcal{M},r)$ the growth rate (also called size function) of a class of matroids $\mathcal{M}$. This is the maximum number of points in a matroid in $\mathcal{M}$ of rank at most $r$. In symbols:

$h(\mathcal{M},r)=\textrm{max}\{\epsilon(M)\ |\ M \in \mathcal{M}\ \textrm{and } r(M)\leq r\}$.

In his first post Peter stated the Growth Rate Theorem, a beautiful and very general result on growth rates of minor-closed classes of matroids. For binary matroids, this specialises to saying that, if $\mathcal{M}$ is a minor-closed class of binary matroids, then either:

1. $h(\mathcal{M},r)$ is linear, or
2. $h(\mathcal{M},r)$ is quadratic, and $\mathcal{M}$ contains all graphic matroids, or
3. $\mathcal{M}$ is the class of all binary matroids.

I will discuss results and conjectures about the exact value of the growth rate for specific classes of binary matroids. The conjectures stated here were made possible by Gordon Royle’s database of binary matroids. I’ve been working on some of these conjectures with Joseph Kung, Dillon Mayhew and Gordon Royle.  I’ll denote by $EX(M)$ the class of binary matroid with no $M$-minor.

Let’s first look at binary matroids that fall into outcome (1) of the Growth Rate Theorem for binary matroids, i.e. classes of binary matroids that do not contain all graphic matroids. For these classes we know that the growth rate is linear. The first class I’ll consider is that of cographic matroids. A simple cographic matroid arises from a graph where every vertex has degree at least 3. The rank of the matroid (if the graph in question is $G$), is $|E(G)|-|V(G)|+1$. Now suppose that $G$ has a vertex of degree at least 4. Split that vertex into two vertices of degree at least 2 and add an edge between these two vertices (this corresponds to an extension in the matroid). This new graph gives rise to a cographic matroid with the same rank as the initial one, but with one more element. Thus the largest simple cographic matroids arise from cubic (i.e. 3-regular) graphs. With this simple argument we proved that

1) $h(\textrm{cographic matroids}, r)=3(r-1)$.

This was first noted by Joseph Kung in [Ku86].

In the next results I’ll be a bit sloppy and write $EX(G)$ for $EX(M(G))$. I will also be a bit sloppy with small rank cases that can easily be worked out. It is well-known that the class $EX(K_4)$ is exactly the class of series-parallel graphs. Thus:

2) $h(EX(K_4),r)=2r-1$.

Let $W_n$ denote the wheel with $n$ spokes. By giving a decomposition theorem for $EX(W_4)$, Oxley [Ox87] proved that

3) $h(EX(W_4))=3r-2$ if $r$ is odd, and $h(EX(W_4))=3r-3$ if $r$ is even.

The extremal examples are parallel connections of copies of $F_7$ and at most one copy of the rank-4 binary spike (called $Z_4$ in [Ox11]). Having extremal examples of large rank built from small extremal examples seem to be “common” in these types of classes (in fact, that’s also the case for 2) if we see series-parallel graphs as parallel connections of copies of $K_3$). This is also the case for the class $EX(K_{3,3})$, as was shown by Mayhew, Royle and Whittle in [MRW10]. This result follows again from a decomposition theorem for the class $EX(K_{3,3})$.

4) $h(EX(K_{3,3}))=14r/3-a$, where $a=7$ if $r=0$ (mod 3), $a=11/3$ if $r=1$ (mod 3) and $a=19/3$ if $r=2$ (mod 3).

The extremal examples are parallel connections of copies of $PG(1,2)$, $PG(2,2)$ and $PG(3,2)$.

Unfortunately, when looking at the next obvious class what I can state is only a conjecture.

Conjecture 1: $h(EX(K_5),r)=9r/2-a$, where $a=13/2$ if $r$ is odd and $a=6$ if $r$ is even. Moreover, the extremal examples are generalised parallel connections along a line of copies of $C_{12}$ and at most one copy of $F_7$.

The matroid $C_{12}$ is one of the sporadic examples appearing in [MRW10] (where you can also find a definition). While I think that Conjecture 1 may be attacked directly, I wish  the best of luck to anyone who would try to prove it via a decomposition theorem for $EX(K_5)$ (which appears to be a much harder problem than the already very difficult decomposition theorem for $EX(K_{3,3}$).

Let’s now move on to classes of binary matroids with quadratic growth rate. A classical result by Heller [He57] gives the growth rate for binary matroids with no $F_7$-minor.

5) $h(EX(F_7),r)=\binom{r+1}{2}$

and it’s not hard to see that the extremal examples are given by graphic matroids. Since $F_7$ is a splitter for the class of binary matroids with no $F_7^*$-minor, we deduce that, for $r\geq 4$,

6) $h(EX(F_7^*),r)=\binom{r+1}{2}$.

In [KDPR13] we showed that the same growth rate is maintained (for $r \geq 5$) by the larger class $EX(AG(3,2))$, and the extremal examples are still graphic matroids.

7) $h(EX(AG(3,2)),r)=\binom{r+1}{2}$.

We also showed that, for rank at least 6, the extremal non-regular example at rank $r$ is the generalised parallel connection along a line of $M(K_r)$ and $F_7$.

What about other classes of binary matroids with quadratic growth? Unfortunately not much is known… However, I do have some interesting conjectures to propose. These are easier to state in terms of even cycle matroids. I mentioned these matroids in my post on biased graphs, but I’ll quickly redefine them here. If $G$ is a graph and $S$ a subset of its edges, we call the pair $(G,S)$ a signed graph. The even cycle matroid arising from $(G,S)$ is the binary matroid represented by the following matrix. Take any binary matrix $A$ representing $M(G)$ (such a matrix has columns indexed by $E(G)$). Now add to $A$ the row incidence vector of $S$ (i.e. a row where entry $e$ is 1 if $e \in S$ and 0 otherwise).

How large can a simple even cycle matroid be? One can see fairly easily that if the even cycle matroid of $(G,S)$ is simple, then $G$ cannot have pairs of parallel edges that are both in $S$ or both not in $S$, and every loop of $G$ has to be in $S$. Moreover we can have at most one such loop. So the largest simple even cycle matroid (for rank $r$) is obtained when we choose $G$ to be $K_r$ with all edges doubled plus a loop, and we choose $S$ to contain exactly one edge per parallel class, plus the loop. The corresponding even cycle matroid is the geometric cone of $M(G)$. So the growth rate for the class of even cycle matroids is $2\binom{r}{2}+1$. The next conjecture states that this is also the growth rate for $EX(PG(3,2))$.

Conjecture 2: For $r \geq 6$, $h(EX(PG(3,2)),r)=2\binom{r}{2}+1$, and the extremal examples for $r\geq 7$ are even cycle matroids.

A binary matroid $M$ is an even cycle matroid if and only if it has a binary single element extension $M’$ (by an element $e$) such that $M’/e$ is graphic. Since any single element contraction of $PG(3,2)$ is not graphic, $PG(3,2)$ is not an even cycle matroid and the whole class of even cycle matroids is contained in $EX(PG(3,2))$.

Let $PG(3,2)^-$ denote the matroid obtained from $PG(3,2)$ by deleting an element. Then $PG(3,2)^-$ is also not an even cycle matroid. The next conjecture is weaker (and possibly easier to prove) than Conjecture 2.

Conjecture 3: For $r \geq 6$, $h(EX(PG(3,2)^-),r)=2\binom{r}{2}+1$, and the extremal examples for $r\geq 7$ are even cycle matroids.

What if we delete two elements from $PG(3,2)$? (I’ll call the corresponding matroid $PG(3,2)^{- -}$). I conclude the post with this conjecture.

Conjecture 4: For $r \geq 6$, $h(EX(PG(3,2)^{- -}),r)=\binom{r}{2}+2r-2$.

The extremal examples are again even cycle matroids, but not the same as for Conjecture 2. This is because $PG(3,2)^{- -}$ is an even cycle matroid itself, so $EX(PG(3,2)^{- -})$ cannot contain the whole class of even cycle matroids. The (conjectured) extremal examples in this class arise from signed graphs $(G_r,S_r)$ described as follows. Pick two vertices $u$ and $v$ in $K_r$. Double all the edges incident with $u$ or $v$ (or both) and add a loop. Call the resulting graph $G_r$. Now put in $S_r$ exactly one edge per parallel class of size 2, plus the loop (and no other edges). It can be shown by induction on $r$ (if you know the signed graph representation of $PG(3,2)^{- -}$) that these even cycle matroids do not, indeed, contain $PG(3,2)^{- -}$ as a minor.

References

[Ox87] J. Oxley,  The binary matroids with no 4-wheel minor, Trans. Amer. Math. Soc. 301, 1 (1987), 63-75.

[Ox11] J. Oxley, Matroid theory, second ed., vol. 21 of Oxford Graduate Texts in Mathematics. Oxford University Press, Oxford, 2011.