Matroids with no $M(K_4)$-minor

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.

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.


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

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

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

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

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

7 thoughts on “Matroids with no $M(K_4)$-minor

  1. Great post, Jim!

    Considering the sparse paving matroids (with or without $M(K_4)$) of a fixed rank on $n$ elements, Nikhil Bansal, Jorn van der Pol and myself conjectured that
    1) there are relatively few matroids with a number of circuit-hyperplanes that is almost maximal, and
    2) the matroids in the class with a substantial number of circuit-hyperplanes will be close to relaxations of those matroids with an almost maximal number.
    As you can see we were also hoping for some leniency here.

    In respose to your Problem 2, to describe the structure of the of sparse paving matroids in $E(M(K_4))$, I would make the same conjecture as for the sparse paving matroids in general: There are few such matroids with very many circuit-hyperplanes, and if you want to have many circuit-hyperplanes you have to conform to the structure of one of them. Here ‘very many’ is $>1/n$ fraction of the bases, and ‘many’ is $> log(n)/n^2$ fraction, say, where $n$ is the number of elements.

  2. Hi Rudi, thanks for the insight. How did you come up with those numbers?

    Proving such results would be a great start, but it is a far cry from the kind of constructive structure that we expect for minor-closed classes omitting a uniform matroid.

    • This highly structured set $S(k,n,m)$ contains about $1/n$ fraction of all the $k$-subsets. The Hoffmann bound shows that an independent set in the Johnson graph can contain at most a $2/n$ fraction of the vertices. So $O(1/n)$ fraction is about right for the maximum size.
      On the other hand, there are generic methods for creating independent sets with $O(1/n^2)$ fraction of the vertices, e.g. a random set of about $1/n^2$ of the $k$-sets has a nonzero probability of being independent by the Lovasz local lemma.
      So I’m expecting ‘background radiation’ below a $1/n^2$ fraction. At at least $\log(n)/n^2$ fraction, you should have cleared that region.

      But I completely agree that even if you could prove such a thing, it doesn’t come close to the structure you expect from excluding uniform.

      Too explain the difference between uniform and $K_4$ my intuition is perhaps too crude, but here it is. Excluding uniform forces the existence of dependencies everywhere (i.e. in all minors of a certain minimum rank and corank) and so intuitively you’d also expect a lot of dependencies lumped together somewhere (say in some minor). If you try to cram enough dependencies in a small minor, that minor can only resolve this by becoming nice and structured. Then in a highly connected matroid, this structure is also imposed on the rest of the matroid.
      Excluding $K_4$ only asks that the dependencies are sufficiently spread out in every minor, this is the opposite of lumped really. That forces nothing unless you also insist that the matroid is saturated with dependencies. So if I have to make a guess, the barrier of structure theory is the presence of many matroids with uniformly low ‘dependency-density’.

      There is an attractive related problem that seems a lot easier: finding a structural description of the gammoids!

      • Your “generic methods” for creating sparse paving matroids with no $M(K_4)$-minor are strong evidence that a constructive solution to Problem 2 is highly unlikely. My last hope would be to use the sparse paving matroids in $EX(M(K_4))$ as a basic class for building the rest. This is not unlike the using graphs with no stable set of size 3 as a basic class in the decomposition of claw-free graphs.

  3. Julie Sims proved that $EX(M(K_4))$ is a “complete” class, that the class is closed under minors, duality, direct sum, truncation and matroid induction. ..

    J.A. Sims, A complete class of matroids, Quart. J. Math. Oxford Ser. (2) 28 (1977) 449 -451.

    I think the list of operations includes principal extensions, but not circuit-hyperplane relaxation unless one can somehow write circuit-hyperplane relaxation as a matroid induction. Matroid induction is a powerful construction for getting new matroids and deserves a serious study if one wants to get away from bounded-line-sizes.

    Can say anything about the easier class $EX(M(K_4), W^3),$ where $W^3$ is the 3-whirl? using the wheels-whirl theorem, perhaps?

    • Hi Joseph,

      Thanks for the reference. I believe that matroid induction preserves representability, so it does not contain circuit-hyperplane relaxation. Also, the definition of “complete class” does not include principal extension, since the class of gammoids is complete.

      While looking at Sim’s paper I wondered whether, EX(M(K_4)) is closed under matroid union. Someone must have looked at this before.

  4. 9-13-2013

    Dear Jim,

    Matroid unions are covered by induction; to get the union of M and N, take the direct sum, on two copies of S, and then induct across the bipartite graph
    S disjoint union S to S, .
    with the edges (a,a). This is probably known and probably in Welsh or Oxley (First edition).

    So EX(M(K_4)) is closed under free products and similar constructions.



Leave a Reply

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