An advertisement

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.

Leave a Reply

Your email address will not be published. Required fields are marked *