This post is about some conjectures on matroid minor structure theory in the most general setting possible: excluding a uniform matroid. Jim Geelen previously discussed questions in this area in [1], and most of what I write here comes from discussions with him.

Whether they be for graphs or matroids, qualitative structure theorems for minor-closed classes usually fit a particular template. They make a statement that the members of a minor-closed class are ‘close’ to having a particular basic structure, where the structure should be something that differs the graphs/matroids in the class from arbitrary/random ones. In the case of proper minor-closed classes of graphs, this structure takes the form of embeddability on a fixed topological surface, as was famously shown by Robertson and Seymour. For matroids representable over a fixed finite field, the structure arises from classes of group-labelled graphs that embed on a fixed topological surface, classes of group-labelled graphs in general, and (when the order of the field is non-prime) classes of matroids representable over a fixed subfield. These results for finite fields have been shown in recent years by Geelen, Gerards and Whittle, and have already given us powerful tools for understanding the matroids in minor-closed classes, as demonstrated most notably in their proof of Rota’s conjecture.

Extending graph minors structure theory to minor-closed classes of matroids over finite fields was no mean feat, but there is real reason to believe that we can generalise it further.  It seems unlikely that one could obtain very strong structural results for all minor-closed classes; for example, the class of sparse paving matroids (that is, the matroids whose girth is at least the rank and whose cogirth at least the corank) is minor-closed, and is conjectured to contain almost all matroids – intuitively, a structure theorem that allows us to ‘understand’ the class of sparse paving matroids seems unlikely. The sticking point here seems to be that this class contains all uniform matroids. At the moment, we think that one should be able to obtain sensible qualititative structure theorems precisely for the minor-closed classes that don’t contain all the uniform matroids. In this post, I’ll state a conjectures that makes this kind of statement. For this, we need two ingredients.

Basic Structures

We first need an idea which basic structures we expect to see as outcomes. These turn out to be pretty close to what goes on in the finite field representable case. Let $\mathcal{M}$ be a minor-closed class not containing all uniform matroids. Let $U$ be a uniform matroid not contained in $\mathcal{M}$. Without loss of generality, we may assume that $U = U_{s,2s}$ where $s \ge 4$, as every uniform matroid is a minor of a matroid of this form. Here are some examples of interesting classes that  $\mathcal{M}$ could be:

• The class of $\mathbb{F}$-representable matroids, where $\mathbb{F}$ is some finite field over which $U$ is not representable.
• The class of graphic matroids.
• The class of bicircular matroids. (These are the ‘graph-like’ matroids in which each edge element is placed freely on the line between two vertex elements).
• The class of frame matroids (i.e. the matroids of the form $M \backslash V$, where $V$ is a basis of a matroid $M$ for which every fundamental circuit has size at most two). This class contains both the previous ones, as well as various other graph-like matroids such as those arising from group-labelled graphs. $U_{4,8}$ is not a frame matroid and therefore neither is $U$.
• The class of duals of frame matroids. (Or graphic/bicircular matroids)
• A class of matroids arising (as graphic, cographic, bicircular, group-labelled-graphic, etc…)  from the class of graphs that embed on some surface.

Although they are not at all trivial from a graph-theoretic perspective, classes of the last type are less rich as they all have small vertical separations. Classes of the the other types, however, contain matroids of arbitrarily high vertical connectivity. Structural statements simplify a lot when they are made about highly connected matroids, and the main conjecture I’ll be stating will apply only to very highly vertically connected matroids in a given minor-closed class; the last type of class will therefore not show up.

The divide between the ‘highly connected’ minor-closed classes and other classes is made concrete by the following conjecture.

Conjecture 1. Let $\mathcal{M}$ be a minor-closed class of matroids not containing all uniform matroids. Either

• $\mathcal{M}$ contains the graphic matroids or their duals,
• $\mathcal{M}$ contains the bicircular matroids or their duals, or
• there is an integer $t$ so that $\mathcal{M}$ does not contain any vertically $t$-connected matroid on at least $2t$ elements.

Closeness 

We now need to say what, according to our structural conjecture, exactly is meant by two matroids being ‘close’. For minor-closed classes of graphs, ‘closeness’ is measured in terms of vortices, apex vertices, and clique-sums. For matroids over finite fields, the structure theory considers two matroids on the same ground set to be ‘close’ if they have representations that differ by a bounded-rank matrix. None of these ideas quite work for matroids in general, as we don’t have representations, let alone vertices. However, there is something that will.

A single-element projection of a matroid $M$ is a matroid $N$ for which there exists a matroid $L$ such that $L \backslash e = M$ and $L / e = N$. If $N$ is a single-element projection of $M$ then $N$ is a single-element lift of $M$. Single-element lifts and projections are dual notions that ‘perturb’ a matroid by a small amount to another matroid on the same ground set; for example, they change the rank and corank of any given set by at most $1$. We write $\mathrm{dist}(M,N)$ to denote the minimum number of single-element lifts and/or projections to transform $M$ into $N$. If this ‘distance’ is small, then $M$ and $N$ are ‘close’. This will serve as the notion of closeness in our structure conjecture. (In a more general structure theory, vortices will also arise). This distance only makes sense if $M$ and $N$ have the same ground set, if this is not the case, then we say $\mathrm{dist}(M,N) = \infty$.

Incidentally (and I’m looking at you, grad students), I would like an answer to the following question, which would simplify the notion of perturbation distance – I don’t have a good intuition for whether it should be true or false, and either way it could be easy.

Problem. Let $M$ and $N$ be matroids for which there exists a matroid $L$ that is a single-element lift of both $M$ and $N$. Does there exist a matroid $P$ that is a single-element projection of both $M$ and $N$?

The Conjecture

Here goes! If $\mathcal{M}$ is a minor-closed class not containing all uniform matroids, then the highly connected members of $\mathcal{M}$ should be close to being frame, co-frame, or representable.

Conjecture 2: Let $\mathcal{M}$ be a minor-closed class of matroids not containing a uniform matroid $U$. There is an integer $t \ge 0$ so that, if $M$ is a vertically $t$-connected matroid in $\mathcal{M}$, then there is a matroid $N$ such that $\mathrm{dist}(M,N) \le t$ and either

• $N$ is a frame matroid,
• $N^*$ is a frame matroid, or
• $N$ is representable over a field $\mathbb{F}$ for which $U$ is not $\mathbb{F}$-representable.

If true, this conjecture would tell us that minor-closed classes of matroids inhabit a very beautiful universe. The hypotheses are very minimal, applying to a massive variety of different $\mathcal{M}$. The conclusions, on the other hand, imply that all ‘nondegenerate’ members of $\mathcal{M}$ are at a small distance from a matroid $N$ that is very far from being generic. Somehow, as happens again and again in matroid theory, the ‘special’ classes of representable and graph-like matroids are in fact fundamental to understanding the minor order.

Conjecture 2 is one of the many goals of a more general matroid structure theory; in my next post I will discuss some recent progress we have made towards it.

Reference

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

In this week-late post I will talk some more about results and conjectures concerning chromatic polynomials of graphs and matroids. As the title suggests, this is a continuation from my April post on the same topic. At the end of that post I said that I would discuss complex chromatic roots of graphs, but here I’ve decided to talk about matroids instead.

The chromatic polynomial of graphs is defined in terms of number of colourings with a given number of colours; this definition does not extend to matroids for obvious reasons. However, the Recipe Theorem by Oxley and Welsh in [OW79] tells us that a function on graphs or matroids satisfying a deletion-contraction recursion is essentially an evaluation of the Tutte polynomial. Now the chromatic polynomial does satisfy this type of recursion, and in fact Tutte’s polynomial was first called by Tutte the dichromatic polynomial, since he saw it as a generalisation of the chromatic polynomial of a graph. If $T_G(x,y)$ denotes the Tutte polynomial of a graph $G$, then \[P(G,q)=(-1)^{|V(G)-k(G)}q^{k(G)}T_G(1-q,0).\]

This definition can easily be extended to matroids. However, the equivalent of the chromatic polynomial for matroids is called the characteristic polynomial, and it is very slightly different (in that is has a missing power of $q$ factor). The characteristic polynomial of a matroid $M$ is denoted as $C(M,q)$ and may be defined as \[C(M,q)=(-1)^{r(M)}T_M(1-q,0).\]

So if $G$ is a graph with $k(G)$ components and $M=M(G)$, then $C(M,q)=q^{-k(G)}P(G,q)$, which for our purposes means that the chromatic polynomial of a graph $G$ and the characteristic polynomial of its graphic matroid $M(G)$ are essentially the same. I’m not sure why this terminology was adopted, since the characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix, hence has nothing to do with the characteristic polynomial of its graphic matroid. Anyway, let’s see what we can say about real chromatic roots of matroids. We can still talk about root-free intervals and upper root-free intervals in the same way as for graphs.

Just to recap, a real interval $(a,b)$ is a root-free interval for a family of matroids $\mathcal{M}$ if no matroid in  $\mathcal{M}$ has a chromatic root (i.e. a root of its characteristic polynomial) in the interval $(a,b)$, while $\mathcal{M}$ has an upper root-free interval if there is a real number $a$ such that no matroid in $\mathcal{M}$ has a real root larger than $a$. The class of all matroids does not have an upper root-free interval (since you can get arbitrarily large chromatic roots from graphs). Many of the results I mentioned for graphs in my previous post generalise to matroids. In particular, if $M$ is a loopless connected matroid, then:

• $C(M,q)$ is an alternating polynomial with degree $r(M)$,
• $C(M,q)$ is non-zero with sign $(-1)^{r(E)}$ for $q\in (-\infty,0)$,
• $C(M,q)$ has a simple zero at $q=1$, and
• $C(M,q)$ is non-zero with sign $(-1)^{r(E)+1}$ for $q\in (0,\frac{32}{27})$.

As for graphs, the first three results are easy to see if you write the chromatic polynomial in the right form. Namely

\[C(M,q)=\sum_{X\subseteq E(M)}(-1)^{|X|}q^{r(E)-r(X)}.\]

The fourth result above was proved for matroids by Edwards, Hierons and Jackson [EHJ98]. So the magic number $\frac{32}{27}$ is still magic for matroids.

If a class of matroids contains all graphic matroids, then it has no upper root-free interval (because of cliques). What about minor-closed classes of matroids not containing all graphs?

If you recall, Woodall and Thomassen proved independently that if $\mathcal{G}$ is a proper minor-closed family of graphs, then $(d(\mathcal{G}),\infty)$ is an upper root-free interval for $\mathcal{G}$, where $d(\mathcal{G})$ is the minimum number such that every graph in $\mathcal{G}$ has a vertex of degree at most $d$ (this is finite by a theorem of Mader). The surprising fact is that this result was published in 1997, while it is in fact implied by a more general and quite a bit older result for matroids. In 1978 Oxley proved the following.

Theorem 1: Let $D=\{x_1,\ldots,x_k\}$ be a cocircuit of a matroid $M$. Then \[C(M,q)=(q-k)C(M\backslash D,q)+\sum_{j=2}^{k}\sum_{i=1}^{j-1} C(M\backslash x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_{j-1}/x_i,x_j, q).\]

This looks a bit complicated, but by induction it implies the following.

Corollary 2: If all minors of a matroid $M$ have a cocircuit of size at most $k$, then $C(M,q)>0$ for all $q \geq k$.

Corollary 2 in turns implies that any proper minor-closed class of graphs has an upper root-free interval (i.e. the result of Woodall and Thomassen). It also implies the same result for matroids of bounded branch width. Unfortunately, minor-closed classes of matroids may not have bounded minimum cocircuit size, even if they don’t contain all graphic matroids, so the following is still wide open.

Conjecture 3: Every minor closed class of matroids that does not contain all graphic matroids has an upper root-free interval.

A very special but still very difficult case of this conjecture is the following.

Conjecture 4: The class of cographic matroids has an upper root-free interval.

Conjecture 4 has been studied quite a bit, since it is in fact a question on flows in graphs (the characteristic polynomial of a matroid is the flow polynomial of its dual). I’ll conclude the post with a bit of history on this problem.

Welsh conjecture that $(4,\infty)$ is an upper root-free interval for cographic matroids. For planar graphs this would imply the Birkoff-Lewis conjecture. However, Gordon Royle found counterexamples to this conjecture by looking at a family of graphs called generalised Petersen graphs. Based on the examples he found for which he could calculate the real roots, he modified Welsh’s conjecture, changing the 4 to a 5, as “$(5,\infty)$ is an upper root-free interval for cographic matroids”. However, this conjecture turned out to also be false, as proved by Jesus Salas and Jesper Jacobsen, who managed to show that some large generalised Petersen graph has real flow roots slightly over 5. Incidentally, in July I went to Royal Holloway to attend the Workshop on New Directions for the Tutte Polynomial and I saw Jesus Salas give a talk on this. You can have a look at his slides on the conference page. So now the question remains of whether cographic matroids do have an upper root-free interval, and if so, what the interval is.

References