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