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.

This post is mainly about results that I proved together with Matt DeVos and Daryl Funk, partly while they were visiting the University of Western Australia after the 37ACCMCC (Dillon talked about this conference in his blog post on December 16, 2013).

First, let me remind you of what a biased graph is (more details can be found in my introductory post). A biased graph is a pair $(G,\mathcal{B})$, where $G$ is a graph and $\mathcal{B}$ is a set of cycles of $G$ satisfying the theta-property: there is no theta subgraph of $G$ that contains exactly two cycles in $\mathcal{B}$. Cycles in $\mathcal{B}$ are called balanced, while the other cycles of $G$ are unbalanced.

A quite general way of constructing biased graphs is via group-labelled graphs. Pick your favourite (say multiplicative) group $\Gamma$ and graph $G$, and assign to each edge $e$ of $G$ an orientation and a value $\phi(e)$ from $\Gamma$: then what you have is a group-labelled graph. Now consider any walk $W$ in $G$, with edge sequence $e_1,e_2,\ldots,e_k$ and extend $\phi$ as

$\phi(W)=\prod_{i=1}^{k}\phi(e_i)^{\textrm{dir}(e_i)}$,

where $\textrm{dir}(e_i)$ is 1 if $e_i$ is forward in $W$, and -1 otherwise. Then we define a cycle $C$ of $G$ to be balanced if a simple closed walk $W$ around $C$ has $\phi(W)=1$. It’s easy to see that this definition is independent of the choice for $W$, and in this way we get, indeed, a biased graph. In this case we identify the group-labelled graph with the associated biased graph. If a biased graph can be constructed in this way from a group $\Gamma$, then we say that such a biased graph is $\Gamma$-labellable. If a biased graph is $\Gamma$-labellable for some group $\Gamma$, then we say that the biased graph is group-labellable. Not all biased graphs are group-labellable, hence the question that is the title of this post. As it turned out, there is a nice topological answer to this question.

Theorem 1: Let $(G,\mathcal{B})$ be a biased graph; construct a 2-cell complex $K$ from $G$ by adding a disc with boundary $C$ for every $C \in \mathcal{B}$. Then the following are equivalent:

1. $(G,\mathcal{B})$ is group-labellable.
2. $(G,\mathcal{B})$ is $\pi_1(K)$-labellable (where $\pi_1(K)$ is the fundamental group of $K$).
3. Every unbalanced cycle of $G$ is noncontractible in $K$.

Before I explain a bit how the proof works, let me discuss some nice constructions that we derived using this theorem. For any group $\Gamma$, the class of $\Gamma$-labellable graphs is closed under minors, for both definition of minors given in my second post on biased graphs. Using Theorem 1, we proved that if $\Gamma$ is an infinite group then there are infinitely many excluded minors to the class of $\Gamma$-labellable biased graphs. In fact, we proved something stronger, namely that there is an infinite list of excluded minors on $n$ vertices for every $n \geq 3$.

Theorem 2: For every $n \geq 3$ and $\ell$ there exists a biased graph $(G,\mathcal{B})$ with the following properties:

• $G$ is a graph on $n$ vertices and every pair of vertices is joined by at least $\ell$ edges.
• $(G,\mathcal{B})$ is not group-labellable.
• For every infinite group $\Gamma$, every proper minor of $(G,\mathcal{B})$ is $\Gamma$-labellable.

For a group $\Gamma$, let $\mathcal{F}_{\Gamma}$ and $\mathcal{L}_{\Gamma}$ denote the class of frame and lift matroids respectively that arise from $\Gamma$-labelled graphs. From Theorem 2 (and a one-page argument) we also show that

Theorem 3: For every infinite group $\Gamma$ and every $n \geq 3$ the classes $\mathcal{F}_{\Gamma}$ and $\mathcal{L}_{\Gamma}$ have infinitely many excluded minors of rank $n$.

Theorem 3 implies in particular that frame and lift matroids are not well-quasi ordered. This was already known, since swirls and spikes form infinite antichains of, respectively, frame and lift matroids (see [GGW02] and [M05]). As far as I know, however, it wasn’t known that there are infinite antichains of frame and lift matroids all of the same rank.

I’ll conclude the post by mentioning the two main ingredients for the proof of Theorem 1. The first main part of the proof consists of expressing $\pi_1(K)$ in the appropriate way. Let $\gamma_e$ be a variable associated with every edge in $G$. We use an application of Van Kampen’s Theorem (see Hatcher’s book on algebraic topology), to express $\pi_1(K)$ as the group presented by the generating set $\{\gamma_e | e \in E(G)\}$, with the relations given by setting

$\prod_{i=1}^{k}\phi(e_i)^{\textrm{dir}(e_i)}=1$,

for each balanced cycle $C$ and any closed walk $W$ around $C$ with edge sequence $e_1,\ldots,e_k$. This allows us to show that (3) implies (2).

The second ingredient of the proof involves reroutings. Consider a closed walk $W$ containing a path $P$, and a balanced cycle $C$ containing $P$. Let $P’$ be the complement of $P$ in $C$; then the walk $W’$ obtained by from $W$ by replacing $P$ with $P’$ is obtained by rerouting along the balanced cycle $C$. If in the previous definition $W$ and $W’$ are both simple walks around a cycle, then the theta property implies that $W$ is balanced if and only if $W’$ is balanced. However, if we start with a simple closed walk $W_1$ around a cycle, we do a series of reroutings and we end with a simple closed walk $W_k$ around a cycle, then knowing the bias of $W_1$ doesn’t tell us anything about the bias of $W_k$, since the intermediate closed walks in the sequence of reroutings may not be simple closed walks around a cycle. However, things are different for group-labelled graphs.

Suppose that $(G,\mathcal{B})$ is a group-labelled graph (so every edge $e$ of $G$ has an orientation and a value $\phi(e)$ from some group $\Gamma$). Consider the extension of $\phi$ to closed walks of $G$, as above. If a closed walk $W’$ is obtained from a closed walk $W$ by rerouting along a balanced cycle, then $\phi(W)=\phi(W’)$ (because $C$ is balanced, so $\phi(P)=\phi(P’)$ in the definition of rerouting). So if $(G,\mathcal{B})$  is group-labelled, then we can never start from a simple closed walk around a balanced cycle and obtain (via reroutings) a simple closed walk around an unbalanced cycle. That is, any biased graph $(G,\mathcal{B})$ that is group-labellable satisfies the following:

4. There does not exist a sequence $W_1,W_2,\ldots,W_k$ of closed walks such that each $W_{i+1}$ is obtained from $W_i$ by rerouting along a balanced cycle and $W_1$ is a simple walk around a balanced cycle and $W_k$ is a simple walk around an unbalanced cycle.

By the argument above, (1) in Theorem 1 implies (4). Using the fundamental group of $K$ we can show that if (3) fail then (4) fails (so (4) implies (3)).

References

[GGW02] J. Geelen, A.M.H. Gerards, and G. Whittle, Branch-Width and Well-Quasi-Ordering in Matroids and Graphs, J. Combin. Theory Ser. B 84 (2002), 270-290.

[M05] D. Mayhew, Inequivalent Representations of Bias Matroids, Combinatorics, Probability and Computing 14 (2005) 567-583.