$\newcommand{\cM}{\mathcal{M}}$

This entry continues on from my last, which concerns the growth rates of matroids in minor-closed classes. A one-line recap of my notation is that, if $\cM$ is a minor-closed class of matroids, then $h_{\cM}(n)$ denotes the ($\mathbb{Z} \cup \{\infty\}$)-valued function whose value at each integer $n$ is the maximum number of elements in a simple matroid in the class of rank at most $n$. Last time I finished with the growth rate theorem of Geelen, Kabell, Kung and Whittle – here it is again.

Growth Rate Theorem
Let $\cM$ be a minor-closed class of matroids. Either

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

This is surprising – up to a constant factor, the growth rate function for an arbitrary minor-closed class has just four possible types and, if the class has superlinear growth rate function then the function is `explained’ by the class containing a natural class with which its growth rate function agrees asymptotically. In this entry and the next, we’ll discuss some questions related to this theorem, starting with the scariest.

Structure

Thinking as we did with Mader’s theorem (Theorem 1 in my last entry), the burning question is why growth rate functions are restricted in this way. In the case of graphs, growth rate functions are controlled because of the structure guaranteed by the graph minors structure theorem. For this purpose, we can only really hope to describe classes satisfying outcomes 1-3 of the theorem, so we exclude some rank-$2$ uniform matroid to gain traction, and pose the following question:

Problem 1: Given an integer $n$, find a structural description for minor-closed classes of matroids not containing $U_{2,n}$.

An solution to this problem would yield a theorem that implies the growth rate theorem (and much more) very easily.

This problem is probably extremely difficult in general, but the case where the matroids are representable over a fixed finite field GF($q$) has been solved. As a major part of their work on the recently vanquished Rota’s Conjecture, Geelen, Gerards and Whittle have proved (but unfortunately not quite written yet – see [GGW07]) a structure theorem for the matroids in arbitrary minor-closed class of GF$(q)$-representable matroids. The representable case of the growth rate theorem falls out of their theorem without much effort.

However, the non-representable case has genuine difficulties not arising from representable matroids that make a structure theorem much harder to dream up. Spikes, for example, cause a special type of trouble that doesn’t crop up over finite fields (see [G08] for a discussion). Problem 1 in its full generality is still very much open.

Zooming In

Something that seems more approachable is to ask more exact questions about how growth rate functions behave. It is one thing to know that $h_{\cM}(n)$ is bounded above and below by, say, a quadratic in $n$, but it is another thing to know the asymptotic or exact behaviour of the function itself. In some cases, this is trivial; there are no prizes for working out the answer if $\cM$ is the class of graphic matroids, for example. In some cases, it seems very hard – even the class of graphic matroids with no $M(K_t)$-minor for general $t$ has a growth rate function that is only partially understood (it is a linear function whose gradient is known asymptotically in $t$, but not known for any fixed $t > 9$ (edit: corrected – thanks Jim), see Thomason [T01]).

However, for many specific classes, the problem is interesting and some results are known. Kung, Mayhew, Pivotto and Royle [KMPR13] recently showed that the growth rate function for the binary matroids with no AG$(3,2)$-minor is the same as that of the graphic matroids for all $n \ge 5$. Geelen and I [GN10] showed that, for sufficiently large $n$, the growth rate function for the class of matroids with no $U_{2,\ell+2}$-minor is equal to that of the GF$(q)$-representable matroids, where $q$ is the largest prime power not exceeding $\ell$. We also have shown, (and will write someday) that every minor-closed class $\cM$ whose growth rate function is exponential in $n$ satisfies $h_{\cM}(n) = \frac{q^{n+k}-1}{q-1} – qd$ for all sufficiently large $n$, where $k$ and $d$ are nonnegative integers with $d \le \frac{q^{2k}-1}{q^2-1}$.

Many questions of this sort are still open. Here is one in quite a general form:

Problem 2: Let $\mathfrak{F}$ be a set of fields containing at least one finite field, and $\cM$ be the class of matroids representable over all fields in $\mathfrak{F}$. Determine $h_{\cM}(n)$.

This determination could be asymptotic, exact, or exact for all large $n$. Some cases are easy; if $\mathfrak{F}$ contains GF$(2)$ then it is either the class of binary matroids or regular matroids. If $\mathfrak{F}$ contains GF$(3)$ then the answer will follow from Whittle’s characterisation of ternary matroids [W97]. If all fields in $\mathfrak{F}$ share a common subfield that is not itself in $\mathfrak{F}$, then $\cM$ has exponential growth rate function and the (eventually exact) answer probably follows from our theorem above. If $\mathfrak{F} = \{\mathrm{GF}(4), \mathrm{GF}(5)\}$ then $\cM$ is the class of golden-mean matroids and there is a conjectured answer of Archer [A05] confirmed in some cases by Welsh [W11]. The case where $\mathfrak{F}$ contains $\mathbb{C}$ and one other field GF$(q)$ is very interesting and the extremal examples are probably all Dowling geometries over GF$(q)$. Here is a concrete conjecture to that effect:

Conjecture 1: Let $q$ be a prime power. The class $\cM$ of matroids representable over $\mathbb{C}$ and GF$(q)$ has growth rate function $h_{\cM}(n) = n + (q-1)\binom{n}{2}$ for all sufficiently large $n$.

One could modify this conjecture to the case where $\cM$ is the class of $\mathbb{C}$-representable matroids with no $U_{2,t}$-minor for some integer $t \ge 4$. In this case, the extremal examples are still probably the Dowling geometries, but again not much is known.

Next time, we’ll talk about generalisations of $h_{\cM}(n)$ applying to classes that do contain all simple rank-$2$ matroids. See you then.

References

[A05] S. Archer. Near varieties and extremal matroids, PhD thesis, Victoria University of Wellington, 2005.

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

[GGW07] J. Geelen, B. Gerards, G. Whittle. Towards a matroid-minor structure theory. In Combinatorics, complexity and chance, vol. 34 of Oxford Lecture Ser. Math. Applic. 72-92. Oxford Univ. Press, Oxford, 2007.

[GN10] J. Geelen, P. Nelson. The number of points in a matroid with no $n$-point line as a minor. J. Combin. Theory Ser. B, 100(6):625-630, 2010

[KMPR13] J. Kung, D. Mayhew, I. Pivotto, G. Royle. Maximum size binary matroids with no AG(3,2)-minor are graphic. arXiv:1304.2448 [math.CO]

[T01] A. Thomason. The extremal function for complete minors. J. Combin. Theory Ser.B 81:318-338, 2001

[W11] M. Welsh. Golden mean and secret sharing matroids. Master’s thesis, Victoria University of Wellington, 2011.

[W97] G. Whittle. On matroids representable over GF(3) and other fields. Trans. Amer. Math. Soc., 349(2):579-603, 1997

Partial fields give a more flexible theory of matroid representation than mere fields. Rather than committing to a field, a partial field allows you to capture several representations at once. They were first introduced by Semple and Whittle [SW96]. The archetypical example is the following theorem by Tutte:

Theorem 1. The following statements are equivalent for a matroid $M$:

1. $M$ is representable over both $\text{GF}(2)$ and $\text{GF}(3)$;
2. $M$ is representable over $\text{GF}(2)$ and some field of characteristic other than $2$;
3. $M$ is representable over $\mathbb{R}$ by a totally unimodular matrix;
4. $M$ is representable over every field.

Matroid representations over partial fields generalize totally unimodular matrices, as we will see below. We know that regular matroids (i.e. the matroids from Theorem 1) possess many interesting properties. Let $\mathcal{M}$ be the class of regular matroids.

1. The excluded minors for $\mathcal{M}$ are $U_{2,4}$, $F_7$, and $F_7^*$.
2. Every regular matroid is uniquely representable over every field (up to row operations and column scaling).
3. All regular matroids can be obtained from graphic matroids and $R_{10}$ by dualizing and 1-, 2-, 3-sums (this is Seymour’s Decomposition Theorem).
4. A simple, regular matroid of rank $r$ has at most ${r+1 \choose 2}$ elements, with equality for the graphic matroids of complete graphs.
5. If $A$ is a totally unimodular matrix of full row rank representing $M$, then $\det(A A^T)$ equals the number of bases of $M$.

For every partial field $\mathbb{P}$, one may ask if analogues of these properties exist for the class of $\mathbb{P}$-representable matroids. This is an area of research with a number of interesting results and many unsolved problems.

In this post I will limit myself to introducing matroid representation over partial fields, linking them to the definition of totally unimodular matrices, and giving some examples. In my next post I will discuss Whittle’s characterization [Whi95, 97] of the representations of ternary matroids.

1. Definitions

The definition of a partial field is straightforward:

Definition 2. A partial field is a pair $\mathbb{P} = (R, G)$, where $R$ is a commutative ring, and $G$ is a subgroup of the invertible elements of $R$ such that $-1 \in G$.

I will introduce matroid representations over partial fields through chain groups. For fields, this corresponds to the row space of the representation matrix. The advantage is a very clean basic theory, plus an extension to noncommutative rings at no extra cost. Incidentally, this is how Tutte himself thought about regular matroids.

Definition 3. Let $R$ be a ring, and $E$ a finite set. A chain group is a subset $C \subseteq R^E$ such that, for $c, d \in C$ and $r \in R$,

1. $0 \in C$;
2. $c+d \in C$;
3. $rc \in C$.

The elements of a chain group are called chains.

Definition 4. The support of a chain $c\in C$ is
$$\| c \| := \{e \in E : c_e \neq 0\}.$$

A nonzero chain with inclusionwise minimal support is called elementary.

Definition 5. Let $G \subseteq R$. A chain $c \in R^E$ is $G$-primitive if $c \in (G\cup\{0\})^E$.

Definition 6. Let $\mathbb{P} = (R, G)$ be a partial field, and $E$ a finite set. A chain group $C \subseteq R^E$ is a $\mathbb{P}$-chain group if, for every elementary chain $c$ there exists an $r\in R$ such that $c = rg$ for some $G$-primitive chain $g$.

I realize this was a fairly long string of definitions, but the payoff is that we can very quickly define matroid representations:

Theorem 7. Let $\mathbb{P}$ be a partial field, and $C$ a $\mathbb{P}$-chain group. Define
$$\mathcal{C}^* := \{ \|c\| : c \in C, \text{ elementary}\}.$$
Then $\mathcal{C}^*$ is the collection of cocircuits of a matroid, $M(C)$.

Proof. We verify the (co)circuit axioms.

1. $\emptyset\not\in \mathcal{C}^*$.
   An elementary chain was defined to be nonzero.
2. If $C, D \in \mathcal{C}^*$ and $C \subseteq D$ then $C = D$.
   The supports of elementary chains are inclusionwise minimal.
3. If $C, D \in \mathcal{C}^*$ are distinct, and $e \in C \cap D$ then there is a member $F \in \mathcal{C}^*$ with $F \subseteq (C\cup D) – \{e\}$.
   Let $c, d$ be chains with $\|c\| = C$ and $\|d\| = D$. Since these chains are elementary, we may assume they are $G$-primitive, i.e. every nonzero entry is invertible. Now write
   $$g := c_e^{-1} c – d_e^{-1} d.$$
   Then $g$ is nonzero, and therefore there is an elementary chain $f$ whose support is contained in that of $g$. We simply take $F = \|f\|$. $\square$

Definition 8. We say a matroid $M$ is $\mathbb{P}$-representable if there exists a $\mathbb{P}$-chain group $C$ such that $M = M(C)$.

One thing to note is that everything above holds even if we don’t assume $R$ to be commutative. This theory of skew partial fields was explored in [PZ13]. For the remainder of this post we’ll stick to the commutative case, though.

2. Restrictions on determinants

If you’ve seen totally unimodular matrices defined, you’ve probably seen a definition involving determinants. This also works for partial fields:

Definition 9. Let $\mathbb{P} = (R, G)$ be a partial field. A $\mathbb{P}$-matrix is a matrix $A$ with entries in $R$ such that each square submatrix has a determinant in $G \cup \{0\}$.

We denote by $A[X]$ the submatrix of $A$ with columns indexed by $X$.

Theorem 10. Let $\mathbb{P} = (R, G)$ be a partial field, and $A$ a $\mathbb{P}$-matrix with $r$ rows and columns indexed by $E$. Define
$$\mathcal{B}_A := \{ X \subseteq E : |X| = r \text{ and } \det(A[X]) \neq 0\}.$$
If this set is nonempty, then $\mathcal{B}_A$ is the set of bases of a matroid, $M[A]$.

Proof. We use a trick from commutative algebra. Let $I$ be a maximal ideal of $R$. Such an ideal is guaranteed to exist (assuming the axiom of choice). Then $\mathbb{F} := R/I$ is a field. Consider the ring homomorphism $\phi: R \to \mathbb{F}$ sending $r$ to $r + I$. Since this is a homomorphism, it commutes with addition and multiplication. Hence, if we apply it to the entries of $A$, we preserve the nonzero determinants. Since we have a matroid after applying $\phi$, we must have had a matroid before. $\square$

The link with the previous section is simple:

Theorem 11. Let $C$ be the chain group generated by the rows of a $\mathbb{P}$-matrix $A$. Then $C$ is a $\mathbb{P}$-chain group and $M(C) = M[A]$.

We also have a converse:

Theorem 12. Let $C$ be a $\mathbb{P}$-chain group, let $B$ be a basis of $M(C)$, and let $A$ be the matrix whose rows are $G$-primitive chains such that their supports form the $B$-fundamental cocircuits of $M(C)$. Then $A$ is a $\mathbb{P}$-matrix, and $M[A] = M(C)$.

This post is already getting long, so I will skip the proof and refer to [PZ13, Section 3.4] instead.

3. Examples

The key takeaway from the proof of Theorem 10 is the idea of a homomorphism:

Definition 13. Let $\mathbb{P}_1 = (R_1, G_1)$ and $\mathbb{P}_2 = (R_2, G_2)$ be partial fields, and let $\phi: R_1 \to R_2$ be a ring homomorphism such that $\phi(G_1) \subseteq G_2$. Then $\phi$ is a partial field homomorphism.

Theorem 14. If $\phi$ is as above, then every $\mathbb{P}_1$-representable matroid is also $\mathbb{P}_2$-representable.

We omit the proof, which is only a slight modification of the proof of Theorem 10. Note that we can identify a field $\mathbb{F}$ with the partial field $(\mathbb{F}, \mathbb{F}^*)$.

The regular partial field is $\mathbb{U}_0 = (\mathbb{Z}, \{-1, 1\})$. The $\mathbb{U}_0$-matrices are precisely the totally unimodular matrices. There is clearly a partial field homomorphism to any partial field, so regular matroids are, in fact, representable over every partial field too!

The dyadic partial field is $\mathbb{D} = (\mathbb{Z}[\frac{1}{2}], \langle -1, 2 \rangle)$. This means that we extended the ring of integers with all powers of $\frac{1}{2}$, and consider matrices where all subdeterminants are, in absolute value, a (positive or negative) power of $2$. There is a ring homomorphism to every field of characteristic other than 2.

The golden ratio partial field is $\mathbb{G} = (\mathbb{Z}[\tau], \langle -1, \tau\rangle)$, where $\tau$ is the golden ratio, i.e. the positive root of $x^2 – x – 1 = 0$. There is a homomorphism to a number of fields, notably $\text{GF}(4)$ and $\text{GF}(5)$. In fact, it can be shown that a matroid has a golden ratio representation if and only if it is representable over both $\text{GF}(4)$ and $\text{GF}(5)$.

The partial field $\mathbb{P}_4$ is defined as follows. Let $\alpha$ be an indeterminate, let $G$ be the subgroup of the units of $\mathbb{Q}(\alpha)$ generated by $\{-1, \alpha, \alpha-1, \alpha + 1, \alpha – 2\}$, and let $R$ be the smallest subring of $\mathbb{Q}(\alpha)$ containing $G$. There is a partial field homomorphism to every field with at least four elements (obtained by mapping $\alpha$ to any element other than $0, 1, -1, 2$). Let me end with a conjecture about this partial field:

Conjecture 15. A matroid is representable over all fields with at least four elements if and only if it is representable over $\mathbb{P}_4$.

Note that the partial fields for the corresponding statements for two and three elements are known: they are, respectively, the regular and near-regular partial fields.

For a bigger catalog of partial fields, including a list of homomorphisms between them, I refer to the appendix of my PhD Thesis, [vZ09].

References

[SW96] Charles Semple and Geoff Whittle. Partial fields and matroid representation. Adv. in Appl. Math., 17(2):184–208, 1996.

[PZ13] R.A. Pendavingh, S.H.M. van Zwam. Skew partial fields, multilinear representations of matroids, and a matrix tree theorem. Advances in Applied Mathematics, Vol. 50, Issue 1, pp. 201-227, 2013 (PDF, arXiv, doi).

[Whi95]  Geoff Whittle. A characterisation of the matroids representable over GF(3) and the rationals. J. Combin. Theory Ser. B, 65(2):222–261, 1995.

[Whi97]  Geoff Whittle. On matroids representable over GF(3) and other fields. Trans. Amer. Math. Soc., 349(2):579–603, 1997.

[vZ09] Stefan H. M. van Zwam. Partial Fields in Matroid Theory. PhD thesis, Technische Universiteit Eindhoven, 2009.

For a while now I’ve been curious about some objects in algebraic geometry that have the word “matroid” attached to them, although they are not strictly speaking matroids in Whitney’s sense. There are several varieties of such objects: flag matroids, symplectic matroids, Coxeter matroids, and so on. I’m going to make it my mission to learn about these objects, and seeing as they best way to learn a new topic is to write about it, the fruits of my labours will appear here. For the most part, I’m going to be relying on the book Coxeter Matroids, by Borovik, Gelfand, and White.

I’ll start with something fairly simple: flag matroids. The most straightforward definition (at least from the perspective of an “ordinary matroid” theorist) involves quotients. Let $M$ be an ordinary matroid. We say that the matroid $Q$ is a quotient of $M$ if there exists a matroid, $N$, such that $N\backslash X=M$ for some $X\subseteq E(N)$, and $N/X=Q$. In other words, $Q$ is a quotient of $M$ if it can be obtained from $M$ by extending with a set of elements, and then contracting that set. There are many equivalent conditions for $Q$ to be a quotient of $M$. For example, we could equivalently say that $M$ and $Q$ have the same ground set, and every circuit in $M$ is a union of circuits in $Q$.

Now a flag matroid is easily understood: a flag matroid is a sequence $(M_{1},\ldots, M_{m})$ of ordinary matroids, such that $M_{i}$ is a quotient of $M_{i+1}$ for all $i\in\{1,\ldots, m-1\}$. Note that this implies that $M_{i}$ is a quotient of $M_{j}$ for all $j>i$. An ordinary matroid is therefore just a flag matroid in the case that $m=1$.

Stated in this way, the definition doesn’t seem very appealing. However there is an equivalent characterization (used by Borovik et al. use as their primary definition) which is more promising from the point of view of allowing generalizations. For this characterization, we need to introduce an ordering on $k$-element subsets of a finite set. Let $[n]$ be the set $\{1,\ldots, n\}$, and let $w$ be a permutation of $[n]$. Let $A$ and $B$ be $k$-element subsets of $[n]$. We will assume that $A=\{a_{1},\ldots, a_{k}\}$ and $B=\{b_{1},\ldots, b_{k}\}$, where
\begin{multline*}
w^{-1}(a_{1}) < w^{-1}(a_{2}) < \cdots < w^{-1}(a_{k})\quad \text{and}\\ w^{-1}(b_{1}) < w^{-1}(b_{2}) < \cdots < w^{-1}(b_{k}). \end{multline*} Then we declare that $A\leq^{w} B$ if $w^{-1}(a_{i})\leq w^{-1}(b_{i})$ for all $i\in \{1,\ldots, k\}$. It helps me to conceptualise this definition in the following way: arrange two copies of the sequence $w(1),w(2),\ldots, w(n)$ on top of each other. In the top row, highlight the members of $A$, and in the bottom row highlight the members of $B$. Draw a line from the first member of $A$ to the first member of $B$, from the second member of $A$ to the second member of $B$, and so on. If $A\leq^{w} B$, then all the lines that you have just drawn are either vertical or slope down from left to right. If we use this trick, then it becomes trivial to see that $\leq^{w}$ is a partial order on the $k$-element subsets of $[n]$. In 1968, Gale characterized matroids as follows: Theorem. Let $\mathcal{B}$ be a collection of $k$-element subsets from $[n]$. Then $\mathcal{B}$ is the family of bases of a matroid if and only if, for every permutation $w$ of $[n]$, there is a subset $B\in \mathcal{B}$ such that $A\leq^{w} B$ for every $A\in \mathcal{B}$.

Gale’s proof is short, and quite pleasant, so I include it. Given $\mathcal{B}$, a collection of $k$-element subsets of $[n]$, and $w$, a permutation of $[n]$, I will use the phrase upper bound to mean a subset $B\in \mathcal{B}$ such that $A\leq^{w} B$ for every $A\in\mathcal{B}$. By maximal member, I mean a subset $B\in \mathcal{B}$ such that $A\in \mathcal{B}$ and $B\leq^{w} A$ implies $A=B$.

Proof. First assume that $\mathcal{B}$ is the family of bases of a matroid, but that there is a permutation, $w$, such that $\mathcal{B}$ has no upper bound under $\leq^{w}$. Because there are only finitely many $k$-element subsets of $[n]$, there exists a maximal member of $\mathcal{B}$ under $\leq^{w}$. In fact, there must be at least two maximal members of $\mathcal{B}$, for if there is only one, then that member is an upper bound. Let $A$ and $B$ be distinct maximal members of $\mathcal{B}$. Let $x$ be the first element in the sequence $w(1),\ldots, w(n)$ that is in the symmetric difference of $A$ and $B$. Without loss of generality we can assume that $x\in A$. By basis-exchange, there is an element $y\in B-A$ such that $(A-x)\cup y$ is in $\mathcal{B}$. However $A\leq^{w} (A-x)\cup y$, so we have a contradiction to the maximality of $A$.

Now we prove the converse. Let $A$ and $B$ be members of $\mathcal{B}$, and let $x$ be in $A-B$. Assume that $t=|B-A|$. Choose the permutation $w$ so that the last $k+t$ elements in the sequence $w(1),\ldots, w(n)$ are $x$, then the $t$ elements of $B-A$, and then the $k-1$ elements of $A-x$. Let $C$ be the upper bound in $\mathcal{B}$ relative to $\leq^{w}$. Because $A\leq^{w} C$ it follows that $A-x\subseteq C$. Because $B\leq^{w} C$ it follows that the element in $C-A$ must be in $B-A$. Therefore $C=(A-x)\cup y$ for some $y\in B-A$, and the basis-exchange property holds.$\quad\square$

Now let us a define a flag on the set $[n]$ to be a sequence, $(F_{1},\ldots, F_{m})$, of subsets such that $F_{1}\subset F_{2}\subset \cdots \subset F_{m}\subseteq [n]$. Let $\mathcal{F}$ be a collection of flags on $[n]$ and assume that there is a sequence of integers, $(k_{1},\ldots, k_{m})$, such that $|F_{i}|=k_{i}$ whenever $(F_{1},\ldots, F_{m})$ is in $\mathcal{F}$ and $i$ is in $\{1,\ldots, m\}$. This means that the $i$-th components of flags in $\mathcal{F}$ all have the same cardinality. If $F=(F_{1},\ldots, F_{m})$ and $G=(G_{1},\ldots, G_{m})$ belong to $\mathcal{F}$, and $w$ is again a permutation of $[n]$, then we say that $F\leq^{w} G$ if $F_{i}\leq^{w} G_{i}$, for every $i\in \{1,\ldots, m\}$. We can define a flag matroid in the following way: $\mathcal{F}$ is a flag matroid if and only if, for every permutation $w$ of $[n]$, there is a flag $G\in \mathcal{F}$ such that $F\leq^{w} G$ for every $F\in \mathcal{F}$.

From this definition and from Gale’s theorem, we see that if we take the $i$-th components of all flags in $\mathcal{F}$, we obtain the family of bases of a matroid, $M_{i}$. The sequence $(M_{1},\ldots, M_{m})$ is the sequence of quotients I referred to earlier. The fact that the definitions are equivalent follows from Theorem 1.7.1 in Borovik et al.

Generalizations such as symplectic matroids and Coxeter matroids arise from this definition by removing the requirement that $w$ comes from the symmetric group $Sym([n])$, and instead using another permutation group. I’ll write more about these generalizations next time.

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].