Guest post by Jim Geelen.

Bert Gerards, Geoff Whittle and I have deleloped a structure theory for minor-closed classes of matroids representable over a given finite field; our results are of a similar flavour to the Graph Minors Structure Theorem of Robertson and Seymour [RS03]. I believe that a similar structure theory should emerge for any minor-closed class that omits a uniform matroid; see [Gee08]. However, the tools and intuition that we have developed for addressing matroids over finite fields fail when we consider minor-closed classes that contain all uniform matroids. Is this barrier the natural end of structure theory?

This question has led me to the following natural problem.

Problem 1: Describe the class of matroids with no $M(K_4)$-minor.

What kind of description do I want?

This is a complicated question for which I have no good answer. Whitney, himself, got away with posing the vague problem of characterizing the representable matroids, and I’m hoping for similar leniency here.

Pendavingh and van der Pol [PvdP] give a lower bound on the number of $n$-element matroids with no $M(K_4)$-minor that is asymptotic to Knuth’s lower bound [Knu74] on the number $n$-element matroids. In particular, the bound grows faster than $2^{p(n)}$ for any polynomial $p(n)$, making it quite difficult to give a rigorous complexity theoretic definition of a description.

What do we know?

Let $EX(M(K_4))$ denote the class of matroids with no $M(K_4)$-minor. Obviously $EX(M(K_4))$ is closed under minors, duality, direct sums, and $2$-sums.

Let $e$ be an element of a matroid $M$ and let $F$ be a flat of $M\backslash e$. If $F\cup \{e\}$ is a cyclic flat of $M$ and each cyclic flat of $M$ that contains $e$ also contains $F$, then we call $M$ a principal extension of $M\backslash e$. The following result implies that $EX(M(K_4))$ contains all transversal matroids and, hence, all gammoids.

Lemma 1: $EX(M(K_4))$ is closed under principal extension.

Proof.
Suppose that $M$ is obtained from $M\backslash e$ by principal extension into the flat $F$ and that $M\backslash e$ has no $M(K_4)$-minor. Toward a contradiction suppose that $D$ and $C$ are disjoint sets such that $M\backslash D/ C$ is isomorphic to $M(K_4)$. By possibly removing elements we may assume that $C\subseteq \{e\}$ and that $D\subseteq F$. Since one cannot obtain an $M(K_4)$-minor by parallel-extension, $r_M(F)\ge 2$. Each element of $M(K_4)$ is on the intersection of two triangles but $e$ is not, so $C=\{e\}$.

Consider a triangle $T$ of $M(K_4)$. If $T$ is independent in $M$, then $F$ is contained in the closure of $T\cup \{e\}$. Since $r(F)\ge 2$, at most two of the triangles of $M(K_4)$ become independent in $M$. Thus at least two of the triangles remain. Since $M(K_4)$ is not a restriction of $M\backslash e$, exactly two of the triangles remain. Let $f$ be the unique point not on one of those two triangles. Now it is easy to check that $\{e,f\}$ spans $F$ and $M/ f\backslash e$ has an $M(K_4)$-minor. $\Box$

The constructions described so far preserve representability, here is a construction that does not; the proof is obvious and omitted.

Lemma 2: $EX(M(K_4))$ is closed under the relaxation of circuit hyperplanes.

This is close to all that I know about the class.

Connectivity does not help

Matroid structure theory is built upon the founding principal that structure smooths out with increased connectivity. Unfortunately, this is just not the case for the class of matroids with no $M(K_4)$-minor. For each matroid $M$ we can construct, via principal extension, a round matroid $M’$ such that $M$ has an $M(K_4)$-minor if and only if $M’$ does. (A round matroid is one with infinite vertical connectivity.)

I don’t really know where to go from here, but we may learn something by retreating into some easier classes.

Sparse paving matroids

Motivated by the conjecture that almost all matroids are sparse paving and by the result in [PvdP] that there are many sparse paving matroids with no $M(K_4)$-minor, this seems to be a natural class to consider.

Problem 2: Describe the class of sparse paving matroids with no $M(K_4)$-minor.

This problem looks complicated, even in rank 3. In higher rank, there are quite subtle constructions. Let $k$, $n$, and $m$ be positive integers with $k\le m$ and let $S(k,m,n)$ be the collection of all $k$-element subsets of $\{1,\ldots,n\}$ whose elements sum to $m$ modulo $n$. Now let $M(k,m,n)$ be the rank-$k$ matroid on $\{1,\ldots,n\}$ whose nonspanning circuits are $S(k,m,n)$. Now $M(k,m,n)$ is clearly a sparse paving matroid. Pendavingh and van der Pol prove that, if $n$ is odd, then
$M(k,m,n)$ has no $M(K_4)$-minor. This construction leads to an enormous number of $n$-element sparse paving matroids with no $M(K_4)$-minor since we can relax any subset of the circuit-hyperplanes $S(k,m,n)$ in $M(k,m,n)$.

This diversion into the class of sparse paving matroids does not look that promising. However, sparse paving matroids are, themselves, highly structured. They are both a single lift of a uniform matroid and a single projection of a uniform matroid. It might be necessary to take the class of sparse paving matroids with no $M(K_4)$-minor as one of the building blocks for $EX(M(K_4))$.

Back to finite fields

Having failed to come up with any significant general insights into matroids with no $M(K_4)$-minor, I will return to the comfort of finite fields, where we know considerably more. This is not likely to shed much light on the general problem, but interesting questions remain nonetheless.

For binary and ternary matroids we have exact characterizations due to Tutte and Oxley, respectively. Note that it suffices to characterize the $3$-connected matroids in the class.

Theorem 1: Every $3$-connected binary matroid with at least $4$ elements has an $M(K_4)$-minor.

Theorem 2: If $M$ is a $3$-connected ternary matroid with no $M(K_4)$-minor, then either $M$ is a whirl or $M$ is isomorphic to a minor of a particular $12$-element matroid $S(5,6,12)$.

For arbitrary finite fields we have a bound on the branch-width [GGW07].

Theorem 3: For each finite field $\mathbb{F}$ there is an integer $k$ such that, if $M$ is an $\mathbb{F}$-representable matroid with no $M(K_4)$-minor, then $M$ has branch-width at most $k$.

That theorem holds more generally with $K_4$ replaced with any planar graph. One would hope to be able to say more for $K_4$.

Conjecture: For each finite field $\mathbb{F}$ there are only finitely many vertically $4$-connected $\mathbb{F}$-representable matroids with no $M(K_4)$-minor.

In fact, I hope for even more, one should be able to describe how to construct all $3$-connected $\mathbb{F}$-representable matroids with no $M(K_4)$-minor. The construction should involve some thin infinite classes, a finite set of exceptional matroids, and a $3$-sum operation. One important thin class is the set of free spikes, and the matroids obtained from these by adding other points freely to the legs. Another thin class is constructed in a similar way from whirls. The $3$-sum operation needs to be carefully defined so that it does not construct $M(K_4)$-minors. For example, suppose that $M_1$ and $M_2$ are matroids, $E(M_1)\cap E(M_2) = L$, and $a,b\in L$ such that $L$ is a line of both $M_1$ and $M_2$, $L$ is modular in $M_2$, each point of $M_2$ in $L-\{a,b\}$ is freely placed on $L$, and neither $M_1$ nor $M_2\backslash (L-\{a,b\})$ has an $M(K_4)$-minor. Now let $M$ be obtained from the modular sum of $M_1$ and $M_2$ on $L$ by deleting $L-\{a,b\}$. Then $M$ has no $M(K_4)$-minor.

References

[Gee08]
J. Geelen,
Some open problems on excluding a uniform matroid,
Adv. in Appl. Math. 41 (2008), 628-637.

[GGW07]
J. Geelen, B. Gerards, G. Whittle,
Excluding a planar graph from GF$(q)$-representable matroids,
J. Combin. Theory, Ser. B 97 (2007), 971-998.

[Knu74]
D.E. Knuth,
The asymptitic number of geometries,
J. Combin. Theory, Ser. A 17 (1974), 398-400.

[RS03]
N. Robertson, P.D. Seymour,
Graph Minors. XVI. Excluding a non-planar graph,
J. Combin. Theory, Ser. B 89 (2003), 43-76.

[PvdP]
R.A. Pendavingh, J.G. van der Pol,
Counting matroids in minor-closed classes,
arXiv:1302.1315v3 [math.CO].

In this post I will define some matroids on graphs and give some examples. Such examples include graphic matroids, bicircular matroids and Dowling geometries. These matroids arise in different contexts and this led to a profusion (and confusion) of terminology. As a consequence, it’s really difficult to look up literature and see what has or hasn’t been done in the area. I’ll try to give a road map of the terminology and the main results. For now I’ll mostly give basic definitions and examples, leaving results for the next post.

1. Biased graphs

All graphs in this post are allowed parallel edges and loops. I’ll constantly talk about cycles of a graph: as is common in graph theory, by a cycle I mean a nonempty connected subgraph in which every vertex has degree two. In various contexts these are also called polygons, circuits, circles… I’ll stick to the word “cycle”. I’ll also abuse terminology and use the word “cycle” to mean the set of edges of a cycle. By a nonempty path I mean a path with at least one edge. Let’s start by defining our general universe.

Def. A biased graph is a pair $(G,\mathcal{B})$ where $\mathcal{B}$ is a set of cycles of $G$ satisfying the following property:

Theta property: for every two cycles $C_1$ and $C_2$ in $\mathcal{B}$ intersecting in a nonempty path, the third cycle in $C_1 \cup C_2$ is also in $\mathcal{B}$.

The cycles in $\mathcal{B}$ are called balanced, and the other cycles are unbalanced. Two cycles sharing a non-empty path form a theta; a theta with all cycles unbalanced is an unbalanced theta.

The theta property guarantees that the matroids defined in the next two sections are indeed matroids. In particular, this property guarantees that the third circuit axiom is satisfied.

Here are some important examples of biased graphs (the importance will become clear in the next sections):

• Biased graphs having only balanced cycles.
• Biased graphs having only unbalanced cycles.
• Signed graphs: consider a graph $G$ and a set of edges $F$ of $G$. Then we declare a cycle of $G$ to be balanced if it contains an even number of edges in $F$, and unbalanced otherwise. The resulting biased graph is called a signed graph. Balanced cycles in signed graphs are also called even or positive in the literature, while unbalanced cycles are also called odd or negative.
• Group labelled graphs: consider a graph $G$ and a (say multiplicative) group $\Gamma$. Orient every edge of $G$ and assign to every oriented edge a value from $\Gamma$. This is how we obtain group labelled graphs. Group labelled graphs are also called gain graphs or voltage graphs. From a group labelled graph we obtain a biased graph as follows. Pick any cycle $C$ of $G$ and choose an orientation for $C$. Traverse $C$ with this orientation and multiply the values on the traversed edges, where backward edges will get the inverse value (so if $(u,v)$ is an oriented edge with value $g$ and this edge appears as $(v,u)$ in the orientation of $C$, the value for this edge will be $g^{-1}$). If the total value along the cycle is $1$, then the cycle is declared to be balanced, otherwise it is unbalanced. Changing the orientation of a cycle only changes the value to its inverse, so this assignment is well defined. It is easy to see that this assignment of balanced/unbalanced cycles satisfies the theta property, so we obtain a biased graph from our group labelled graph. I’ll often abuse terminology and call this biased graph a group labelled graph. Signed graphs are special cases of group labelled graphs, obtained by labelling the edges of a graph with elements from $GF(2)$ or, equivalently, from the multiplicative group of the ternary field. I set them aside because they are relevant on their own.

Following are the two main matroids arising from biased graphs. This general setting was first introduced by Zaslavsky (see [Zas89] and [Zas91]).

2. Frame matroids

Def. Given a biased graph $\Omega=(G,\mathcal{B})$, the frame matroid represented by $\Omega$ has as elements the edges of $G$ and as circuits the edge sets of subgraphs of the following forms (see the figure below): 

1. A balanced cycle.
2. Two unbalanced cycles sharing a vertex.
3. Two vertex-disjoint unbalanced cycles together with a minimal path joining them.
4. An unbalanced theta.

Circuits of frame matroids are subdivisions of these graphs. Unlabelled cycles are unbalanced.

The circuits in 2. and 3. are called handcuffs (respectively tight and loose). 

Zaslavsky [Zas91] calls these matroids biased matroids, but recently the term “frame matroids” has become more common. Originally, a frame matroid was defined to be a matroid $M$ to which a basis $B$ could be added so that every element of $M$ is spanned by two elements in $B$. Zaslavsky showed that this definition is equivalent to the one coming from biased graphs. Consider a frame matroid $M$ represented by a biased graph $\Omega$. Form a new biased graph $\Omega’$ by adding an unbalanced loop to every vertex of $\Omega$ and call $B$ the set of these unbalanced loops. Then $B$ is a basis of the frame matroid $M’$ of $\Omega’$ and $M$ is a restriction of $M’$. Every loop of $\Omega$ is either balanced (hence spanned by the empty set), or unbalanced (so in parallel to the element of $B$ incident to the same vertex). Moreover, every edge of $\Omega$ that is not a loop is spanned by the two loops of $B$ at its endpoints.

It follows immediately from the definition that the independent sets of the frame matroid of $(G,\mathcal{B})$ are the set of edges $F$ such that every component induced by $F$ contains at most one cycle, which will have to be unbalanced.

Here are some examples of frame matroids, arising from different choices for the biased graph $\Omega=(G,\mathcal{B})$.

• Graphic matroids: those are simply the frame matroids of biased graph with all cycles balanced. So frame matroids are a generalization of graphic matroids.
• Bicircular matroids: these are the frame matroids of biased graphs with all cycles unbalanced. Bicircular matroids have been widely studied (more of this in the next post, else no reader will make it to the definition of lift matroids).
• Signed-graphic matroids: these are frame matroids of signed graphs.
• Dowling geometries: first defined by Dowling ([Dow73]) these are frame matroids of group labelled graphs.

If $\mathbb{F}$ is a field and $\Omega$ is a group labelled graph on the multiplicative group of $\mathbb{F}$, then the frame matroid of $\Omega$ is $\mathbb{F}$-representable. A matrix representation is obtained in the following way: let $e$ be an edge of $\Omega$ with label $g$. If $e$ is a balanced loop (i.e. a loop labelled $1$), then the column for $e$ is an all-zero column; if $e$ is an unbalanced loop incident to vertex $u$, then the column for $e$ has the $u$ entry equal to $g$ and zero everywhere else.  If $e=uv$ is not a loop and $e$ is oriented as (u,v), then the corresponding column for $e$ has a $1$ in position $u$, $-g$ in position $v$ and zero everywhere else. The proof that this is a representation of the frame matroid of $\Omega$ is not obvious, but appears, for example, in [Zas82].

The class of frame matroids (and the subclasses defined above) are minor-closed classes. The same is true for lift matroids, defined in the next section. However, this post is long enough without adding matroid operations for biased graphs. I’ll leave that for the next post as well.

3. Lift matroids

Def. Given a biased graph $\Omega=(G,\mathcal{B})$, the lift matroid represented by $\Omega$ has as elements the edges of $G$ and as circuits the edge sets of subgraphs of the following forms (see the figure below): 

1. A balanced cycle.
2. Two unbalanced cycles sharing a vertex.
3. Two vertex-disjoint unbalanced cycles.
4. An unbalanced theta.

Circuits of lift matroids are subdivisions of these graphs. Unlabelled cycles are unbalanced.

At a first glance lift matroids may look quite similar to frame matroids, but the differences between them emerge as soon as you start working with them. My rule of thumb is that frame matroids are easier to deal with than lift matroids, for some definition of “easier”. Having circuits that are not connected in the graph makes things a lot more complicated in a lot of cases.

From the definition we can easily see that the independent sets of the lift matroid of $(G,\mathcal{B})$ are the set of edges $F$ containing at most one cycle, which will have to be unbalanced.

Here are some examples of lift matroids, arising from different choices for the biased graph $\Omega=(G,\mathcal{B})$.

• Graphic matroids: those are simply the lift matroids of biased graph with all cycles balanced. So lift matroids are also a generalization of graphic matroids.
• Even cycle matroids: these are lift matroids of signed graphs. Even cycle matroids appear in alternative proofs of the list of excluded minors for graphic matroids ([Ger95]) and Seymour’s decomposition of regular matroids ([GG95]). In fact, any binary single element coextension of a graphic matroid is an even cycle matroid.
• Spikes: let $G$ be obtained from the cycle on $n$ edges by doubling every edge. Declare every pair of parallel edges to form an unbalanced cycle. The other cycles of the graph may be declared to be balanced or unbalanced, as long as the theta property is satisfied. The lift matroid of the resulting biased graph is a spike with no tip. To obtain a spike with a tip, add an unbalanced loop to the graph.

If $\mathbb{F}$ is a field and $\Omega$ is a group labelled graph on the additive group of $\mathbb{F}$, then the frame matroid of $\Omega$ is $\mathbb{F}$-representable. A matrix representation is obtained in the following way: let $A$ be the vertex-edge oriented incidence matrix of $G$, with the orientation given in the group labelled graph. Add a row to $A$, where the entry for edge $e$ is the group label of $e$. The reader is invited to check that this is a valid matrix representation for the matroid.

In the next post I’ll survey some problems and results regarding these matroids.

References

The Twitterverse has been abuzz recently with the news that Rota’s Conjecture has been proved by Jim Geelen, Bert Gerards, and Geoff Whittle! See press releases here and here (with an interview of Geoff at the bottom) and here. This news was known, by word of mouth, to people in the community close to the sources for a while, but let me take this opportunity to try to explain to the non-experts what this conjecture is all about. I will build up in a few steps from a small class of objects to bigger and bigger classes. For the experts, this survey by Geelen, Gerards, and Whittle might be better reading. Continue reading →

$\newcommand{\cG}{\mathcal{G}}$ $\newcommand{\cM}{\mathcal{M}}$ $\newcommand{\elem}{\varepsilon}$ $\newcommand{\con}{/}$ $\newcommand{\del}{\!\backslash\!}$

I’m going to give what is hopefully a less frenetically paced exposition of what many readers have probably seen me talk about more that once – the growth rates of matroids in minor-closed classes. I’ll try to cover things from the ground up in order to motivate the subject, as well as provide some short proofs. The traditional starting point, from which I won’t deviate, is a theorem of Mader [Mader67]:

Theorem 1. If $\mathcal{G}$ is a proper minor-closed class of graphs, then $|E(G)| \le c_{\mathcal{G}}|V(G)|$ for each simple graph $G$ in $\cG$.

Here, `proper’ means that $\cG$ isn’t the class of all graphs, and $c_{\mathcal{G}}$ is a positive real constant depending only on $\cG$. Note that this theorem fails if we allow $\mathcal{G}$ to be the class of all graphs; the complete graph $K_t$ has $\binom{t}{2}$ edges and $t$ vertices, and the ratio $\binom{t}{2}$ is not bounded above by any linear function of $t$. With this fact in mind, what is interesting is the dichotomy; either $\cG$ is the class of all graphs and the densest simple graphs in $\mathcal{G}$ (the cliques) have a number of edges that is quadratic in their number of vertices, or $\mathcal{G}$ is not the class of all graphs and this bound is linear. This is not just a curiosity – we know now that it reflects the structure proved by Robertson and Seymour in the graph minors structure theorem – the graphs in a proper minor-closed class are at most linearly dense because they are `almost’ embeddable on a fixed surface. Of course we didn’t know this in 1967, so it presented a question rather than a corroboration.

Moving on to matroids, we first define some convenient notation. For a matroid $M$, we write $\elem(M)$ for $|\mathrm{si}(M)|$ (equivalently the number of rank-$1$ flats of $M$); this stops us having to awkwardly talk about simple matroids all the time. For a minor-closed class $\cM$, we use $h_{\cM}(n)$ to denote the function whose value at an integer $n$ is the maximum of $\elem(M)$ over all matroids $M \in \cM$ whose rank is at most $n$. Some people call this the size function but I’ll call in the growth rate function. We allow $h_{\cM}(n) = \infty$ – indeed any class that contains $U_{2,k}$ for all $k$ will satisfy this for all $n \ge 2$. In the interesting cases this function is monotonely increasing without bound. For example, for the class $\cM$ of graphic matroids has growth rate function $h_{\cM}(n) = \binom{n+1}{2}$, and by Theorem 1 above, all of its proper subclasses have growth rate function at most linear in $n$.

The next few theorems will combine to divide minor-closed classes of matroids into four types, just as Theorem 1 divides classes of graphs into two. These theorems all concern `dichotomies’ in growth rate functions. The first, due to Kung [Kung91] distinguishes classes with finite growth rate functions from those with infinite growth rate function. We’ll even prove it, since the proof is so nice.

Theorem 2.  If $\cM$ is a minor-closed class of matroids, then either

• $h_{\cM}(n) = \infty$ for all $n \ge 2$, or
• there is some $\ell \ge 2$ such that $U_{2,\ell+2} \notin \cM$ and $h_{\cM}(n) \le \frac{\ell^n-1}{\ell-1}$ for all $n$.

Proof: If $U_{2,\ell+2} \in \cM$ for all $\ell \ge 2$ then the first outcome holds, so we may assume that $U_{2,\ell+2} \notin \cM$ for some $\ell \ge 2$, and will show that $\elem(M) \le \frac{\ell^r-1}{\ell-1}$ for each integer $r$. Let $M \in \cM$ be a rank-$r$ matroid and $e$ be a nonloop of $M$. Inductively we may assume that $\elem(M \con e) \le \frac{\ell^{r-1}-1}{\ell-1}$, and we know $M$ has $\elem(M \con e)$ lines containing $e$. Since $M$ has no $U_{2,\ell+2}$-minor, each of these lines has at most $\ell$ points other than $e$, so $\elem(M) \le \ell \elem(M \con e) + 1 \le \ell\frac{\ell^{r-1}-1}{\ell-1}+ 1 \le \frac{\ell^r-1}{\ell-1}$, as required.

This theorem tells us that there is no minor-closed class with finite growth rate function greater than exponential in $n$, and cleanly divides growth rate functions into the infinite and the finite. In fact, there is much more to the story than this; we’ll finish by stating the theorem that will be the focus of my next post. This theorem was conjectured by Kung [Kung91] and stated in [GKW09] as a consequence of various theorems of Geelen, Kabell, Kung and Whittle.

Growth Rate Theorem. If $\cM$ is a minor-closed class of matroids, then either

• $h_{\cM}(n) \le c_{\cM}n$ for all $n$,
• $\binom{n+1}{2} \le h_{\cM}(n) \le c_{\cM}n^2$ for all $n$ and $\cM$ contains all graphic matroids,
• there is a prime power $q$ such that $\frac{q^n-1}{q-1} \le h_{\cM}(n) \le c_{\cM}q^n$ for all $n$ and $\cM$ contains all GF$(q)$-representable matroids, or
• $h_{\cM}(n) = \infty$ for all $n \ge 2$ and $\cM$ contains all simple rank-$2$ matroids.

Again $c_{\cM}$ is always a real constant depending only on $\cM$. In other words, up to a constant, there are just four possible qualitative behaviours for growth rate functions: linear, quadratic, exponential and infinite. This is dramatic behaviour and deserves more consideration. See you next time!

References

• [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.
• [Kung91] J. P. S. Kung. Extremal matroid theory. In Graph structure theory (Seattle, WA, 1991), volume 147 of Contemp. Math., pages 21–61. Amer. Math. Soc., Providence, RI, 1993.
• [Mader67] W. Mader. Homomorphieeigenschaften und mittlere kantendichte von graphen. Mathematische Annalen, 174:265–268, 1967. 10.1007/BF01364272.