$\newcommand{\del}{\,\backslash\,}$ $\newcommand{\con}{/}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\DeclareMathOperator{\ex}{ex}$ $\DeclareMathOperator{\PG}{PG}$ $\DeclareMathOperator{\AG}{AG}$
$\DeclareMathOperator{\BB}{BB}$

Note: next week there will be no post. The Matroid Union will return on January 6 with a post by Stefan. Happy holidays!

Guest post by Jim Geelen.

A graph is called $H$-free if it has no subgraph isomorphic to $H$. The Turán problem for a given graph $H$ is to determine, for each integer $n$, the maximum number, $\ex(H,n)$, of edges among all $n$-vertex $H$-free graphs. This problem has a natural analogue for binary geometries (that is, simple binary matroids). A binary geometry is called $N$-free if it has no restriction isomorphic to $N$. The Turán problem for a binary geometry $N$ is to determine, for each integer $r$, the maximum number, $\ex(N,r)$, of points in a rank-$r$ $N$-free binary geometry.

Geometers have done quite a lot of work on Turán problems for projective geometries (see [HS01, Section 7]), but it does not seem to be well known in matroid theory (I didn’t know about it in any case). The purpose of this post is to discuss the Bose-Burton Theorem [BB66], which solves the Turán problem for projective geometries, and to consider questions about the structure of $\PG(m-1,2)$-free binary geometries that are close to the density threshold.

$K_t$-free graphs

We start with the classical result of Turán.

The Turán graph $T(n,t)$ is the complete $(t-1)$-partite graph whose parts each have size $\lfloor{\frac{n}{t-1}}\rfloor$ or $\lceil{\frac{n}{t-1}}\rceil$. Equivalently, $T(n,t)$ is the densest $(t-1)$-colourable graph on $n$ vertices. Since $T(n,t)$ is $(t-1)$-colourable, it is $K_t$-free. Let $\tau(n,t)$ denote the number of edges of $T(n,t)$.

Turán’s Theorem: For all integers $n\ge t\ge 1$, if $G$ is a $K_t$-free graph with $n$ vertices, then $|E(G)|\le \tau(n,t)$. Moreover equality holds if and only if $G$ is isomorphic to $T(n,t)$.

$\PG(m-1,2)$-free geometries

The Bose-Burton geometry , denoted $\BB(r,c)$, is the geometry obtained from $\PG(r-1,2)$ by deleting all of the points in a flat of rank $r-c$. Thus $\BB(r,1)$ is isomorphic to the binary affine geometry $\AG(r-1,2)$. Note that $\BB(r,c)$ has $2^r – 2^{r-c}$ points. The critical exponent of a rank-$r$ binary geometry $M$ is the minimum $c$ such that $M$ is isomorphic to a restriction of $\BB(r,c)$. Thus $\BB(r,c)$ is the densest rank-$r$ binary geometry with critical exponent $c$.

Bose-Burton Theorem: For all integers $r\ge m\ge 1$, if $G$ is a $\PG(m-1,2)$-free binary geometry with rank $r$, then $|M|\le 2^r – 2^{r-m+1}.$ Moreover equality holds if and only if $M$ is isomorphic to $\BB(r,m-1)$.

The result is easier to prove in the following form.

Theorem: For all integers $r\ge m\ge 1$, if $X$ is a set of points in $\PG(r-1,2)$ such that $\PG(r-1,2)\del X$ is $\PG(m-1,2)$-free, then $|X| \ge 2^{r-m+1} -1$. Moreover, $|X| = 2^{r-m+1} -1$ if and only if $X$ is a rank $r-m+1$ flat of $\PG(r-1,2)$.

Proof. Consider a counterexample $(r,m,X)$ with $m$ as small as possible; clearly $m\gt 1$. Let $p\not\in X$ be a point of $\PG(r-1,2)$; if $X$ is not a flat of $\PG(r-1,2)$, then we choose $p$ to be on a line spanned by two points in $X$. When we contract $p$ in $\PG(r-1,2)$ and simplify we get $\PG(r-2,2)$; let $X’$ be the image of $X$ under this contraction. By construction $\PG(r-2,2)-X’$ is $\PG(m-2,2)$-free. By our choice of counterexample, $$ |X’|\ge 2^{r-1 – {m-1} + 1} -1 = 2^{r-m+1}-1.$$ Moreover, by construction, $ |X| \ge |X’|$ and, by our choice of $p$, unless $X$ is a flat of $\PG(r-1,2)$, $ |X| \gt |X’|.$ This proves the result.$\Box$

Turán’s Theorem has some quite easy proofs, but none are as simple as the above proof of the Bose-Burton Theorem.

Graphs near the threshold

The density of an $n$-vertex graph with $m$-edges is defined to be $\frac{m}{n\choose 2}$. Note that, for large $n$ the density of the Turán graph $T(n,t)$ tends to $\frac{t-2}{t-1}$ (this is the probability that two randomly chosen vertices fall in distinct classes).

Turán’s Theorem gives a density threshold for $K_t$-free graphs and characterizes those graphs that meet the threshold; the characterization amounts to saying that the extremal graphs are $(t-1)$-colourable. One might hope that all $K_t$-free graphs with density close to $\frac{t-2}{t-1}$ are $(t-1)$-colourable, however, this turns out to be false. There exist triangle-free graphs that are not $(t-1)$-colourable, and by taking the direct sum with such a graph with a large Turán graph $T(n,t)$, we can get $K_t$-free graphs that are not $(t-1)$-colourable and whose densities are arbitrarily close to $\frac{t-2}{t-1}$.

Andrásfai, Erdös, and Sós [AES74] overcome this by considering the minimum degree instead of the density. Note that an $n$-vertex graph with minimum degree $\ge d\cdot n$ has density $\gt d$.

Theorem: If $G$ is a $K_t$-free graph on $n$-vertices with minimum degree $\ge \frac{3t-7}{3t-4} n$, then $G$ is $(t-1)$-colourable.

It may not be immediately obvious, but $\frac{3t-7}{3t-4} < \frac{t-2}{t-1}$. For example, the density threshold for $K_3$-free graphs is $\frac{t-2}{t-1} = \frac{1}{2}$, and the above theorem says that $n$-vertex $K_3$-free graphs with minimum degree $> \frac{3t-7}{3t-4}n = \frac 2 5 n$ are bipartite.

Geometries near the threshold

The density of a rank-$r$ binary geometry with $m$ points is defined to be $\frac{m}{2^r-1}$. Note that, for large $r$ the density of the Bose-Burton geometry $\BB(r,m-1)$ tends to $1-2^{1-m}$.

The Bose-Burton Theorem gives a density threshold and shows that the extremal $\PG(m-1,2)$-free binary geometries have critical exponent $m-1$. It turns out that, unlike the case for graphs, all $\PG(m-1,q)$-free binary geometries with density close to $1-2^{1-m}$, have critical exponent $m-1$. The following result is due to Goevaerts and Storme [GS06].

Theorem: For all integers $r\ge m\ge 2$, if $M$ is a rank-$r$ $\PG(m-1,2)$-free binary geometry with $|M| > \left(1-\frac{11}{2^{m+2}}\right)2^r$, then $M$ has critical exponent $\le m-1$.

The bound in the above theorem is sharp; see [GS06]. This result is particular to the binary field; Beutelspacher [Beu80] gives a bound for arbitrary fields, but that bound is only sharp for fields of square order.

Triangle-free graphs

The following striking sequence of results on triangle-free graphs begs for an analogue in the context of binary geometries.

• There is no $n$-vertex triangle-free graph with minimum degree $\gt \frac 1 2 n$.
• Every $n$-vertex triangle-free graph with minimum degree $\gt \frac 2 5 n$ is bipartite; see [AES74].
• Every $n$-vertex triangle-free graph with minimum degree $\gt \frac{10}{29}n$ is three-colourable; see [Jin95].
• Every $n$-vertex triangle-free graph with minimum degree $\gt \frac{1}{3}n$ is four-colourable; see [BT].
• For each $d\lt \frac 1 3$ there exist triangle-free graphs $G$ with minimum degree $\gt d |V(G)|$ and arbitrarily large chromatic number; proved by Hajnal, see [ES73].

The above results solve a problem of Erdös and Simonovits for triangle-free graphs. The following question is a geometric analogue of that problem.

Question: For integers $c\ge m-1\ge 0$, what is the smallest real number $d(m,c)$ such that, if $M$ is a rank-$r$ $\PG(m-1,2)$-free binary geometry with $|M| \gt d(m,c) 2^r$, then $M$ has critical exponent $\le c$?

Govaerts and Storme’s Theorem shows that $d(m,m-1) = 1-\frac{11}{2^{m+2}}$. In particular, $d(2,1)= \frac{5}{16}$. Computing $d(2,c)$, for each $c\ge 2$, looks to be an interesting problem.

References

[AES74] B. Andrásfai, P. Erdös, V.T. Sós, On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Math. 8 (1974).

[BB66] R.C. Bose, R.C. Burton, A characterization of flat spaces in a finite geometry and the uniqueness of the Hamming and MacDonald codes, J. Combin. Theory 1 (1966).

[Beu80] A. Beutelspacher, Blocking sets and partial spreads in finite projective spaces, Geometriae Dedicata 9 (1980).

[BT] S. Brandt, S. Thomassé, Dense triangle-free graphs are four-colorable: A solution to the Erdös-Simonovits problem.

[ES73] P. Erdös, M. Simonovits, On a valence problem in extremal graph theory, Discrete Math. 5 (1973).

[GN13] J. Geelen, P. Nelson, On minor-closed classes of matroids with exponential growth rate, Advances Appl. Math. 50 (2013).

[GS06] P. Govaerts, L. Storme, The classification of the smallest nontrivial blocking sets in $\PG(n,2)$, Journal of Combinatorial Theory, Series A 113 (2006).

[HS01] J.W.P. Hirschfeld, L. Storme, The packing problem in statistics, coding theory and finite projective spaces: update 2001.

[Jin95] G. Jin, Triangle-free four-chromatic graphs, Discrete Math. 145 (1995).

[Tur41] P. Turán, Eine extremalaufgabe aus der Graphentheorie, Mat. Fiz, Lapok 48, (1941).

Guest post by Jim Geelen.

$\newcommand{\del}{\,\backslash\,}$ $\newcommand{\con}{/}$ $\newcommand{\cC}{\mathcal{C}}$ $\newcommand{\bF}{\mathbb{F}}$

Anyone who has given significant consideration to the classes of frame matroids and lifted graphic matroids will have been struck by their similarities. The point of this posting is that these classes can be unified in a way that might have significant algorithmic implications. We also prove an amazing result (Theorem 3) concerning representations of matroids in the unified class.

Graphic matroids

The class of graphic matroids is very well understood; for example, the set of excluded minors is known and there is a polynomial-time algorithm for recognizing whether a matroid, given by its rank oracle, is graphic.

There are two key parts to the recognition algorithm. First one needs an algorithm for testing whether a given binary matroid is graphic; see, for example, [BC80]. Second one needs to check, for a given matroid $M$ and graph $G$, whether $M=M(G)$. This second part is solved by the following beautiful result due to Seymour [Sey81].

Theorem 1: Let $M$ be a matroid and let $G$ be a loopless $2$-connected graph with $E(G)=E(M)$. Then $M=M(G)$ if and only if $r(M)\le |V(G)|-1$ and, for each vertex $v$ of $G$, the set of edges incident with $v$ in $G$ forms a cocircuit of $M$.

Bias graphs

In the following three short sections, I will review the frame matroid and the lift matroid associated with a bias graph. These objects were introduced by Zaslavsky [Zas91] and were discussed in Irene Pivotto’s post on August 26.

Let $\cC$ be a set of circuits in a graph $G$. A theta in $G$ is loopless $2$-connected subgraph $H$ with $|E(H)| = |V(H)|+1$. Thus, a theta has two special vertices connected by three internally-disjoint paths, and such graphs have exactly three circuits. We say that $\mathcal C$ has the theta-property if there is no theta in $G$ having exactly two of its three circuits in $\cC$. The pair $(G,\cC)$ is called a bias graph if $\cC$ has the theta-property.

Frame matroids

The frame matroid associated with any bias graph $(G,\cC)$ is a unique matroid, denoted $FM(G,\cC)$, with ground set $E(G)$ such that a set $I\subseteq E(G)$ is independent if an only if no circuit of $G[I]$ is contained in $\cC$ and for each component of $G[I]$ has at most one circuit.

Zaslavsky showed that a matroid $M$ is a frame matroid if and only if there is a matroid $M’$ and a basis $B$ of $M’$ such that $M$ is a restriction of $M’$ and for each element $e\in E(M’)-B$, the unique circuit of $B\cup\{e\}$ contains at most two elements of $B$.

Lifts of graphic matroids

The lift matroid associated with any bias graph $(G,\cC)$ is a unique matroid, denoted $LM(G,\cC)$, with ground set $E(G)$ such that a set $I\subseteq E(G)$ is independent if an only if no circuit of $G[I]$ is contained in $\cC$ and $G[I]$ contains at most one circuit. Any matroid that is the lift matroid of a bias graph is called a lifted graphic matroid.

Zaslavsky showed that a matroid $M$ is a lifted graphic matroid if and only if there is a matroid $M’$ an element $e\in E(M’)$ such that $M’\del e = M$ and
$M’\con e$ is graphic.

Combining the classes

Let us call a graph $G$ a framework for a matroid $M$ if

• $E(M) = E(G)$,
• $G$ is connected,
• $r(M)\le |V(G)|$, and
• for each vertex $v$ of $G$, the set of edges incident with $v$ is a cocircuit of $M$.

We will call $M$ a framework matroid if it admits a framework representation.

The definition of a framework is motivated by Theorem 1; it has the appealing property that it is constructive. Given a matroid $M$, via a rank oracle, and a graph $G$ one can readily check (in polynomial time) whether or not $G$ is a framework for $M$. This constructive property is in contrast with the following conjectures.

Conjecture 1: There is no polynomial-time algorithm that, given a matroid $M$ via its rank oracle and a graph $G$, determines whether there is a bias graph $(G,\cC)$ such that $M=FM(G,\cC)$.

Conjecture 2: There is no polynomial-time algorithm that, given a matroid $M$ via its rank oracle and a graph $G$, determines whether there is a bias graph $(G,\cC)$ such that $M=LM(G,\cC)$.

I further believe that the recognition problem is intractable for both the class of frame matroids and the class of lifted graphic matroids. In contrast, I think that one can recognize framework matroids.

Conjecture 3: There is a polynomial-time algorithm that, given a matroid $M$ via its rank oracle, determines whether $M$ is a framework matroid.

Technical details

Let us call a graph $G$ a weak framework for a matroid $M$ if

• $E(M) = E(G)$,
• $r(M)\le |V(G)|$,
• for each vertex $v$ of $G$, the set of edges incident with $v$ is the union of a collection of cocircuits of $M$ and a set of loops of $M$, and
• each loop of $M$ is a loop of $G$.

This weakened notion behaves nicely with respect to our three classes.

• If $G$ is a graph, the $G$ is a weak framework for $M(G)$.
• If $M$ is the frame matroid for the bias graph $(G,\cC)$, then $G$ is a weak framework for $M(G)$.
• If $M$ is the lift matroid for the bias graph $(G,\cC)$, then $G$ is a weak framework for $M(G)$.

Lemma 1: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected and $H$ is a subgraph of $G$, then $H$ is a weak framework of $M| E(H)$.

Proof. Note that for any edge $e$ of $G$, $G-e$ is a weak framework of $M-e$. Now consider a vertex $v$ of $G$ and let $X$ denote the set of edges incident with $v$. If there is a nonloop edge $e$ of $G$ that is incident with $v$, then there is a cocircuit $C^*$ of $M$ such that $e\in C^*\subseteq X$. Then $r(E(G-v)) \le r(E(G)) – 1 \le |V(G)|-1 = |V(G-v)|$. Hence $G-v$ is a weak framework of $M\del X$. Now the result follows by deleting the vertices $V(G)-V(H)$, in an appropriately chosen order, and then deleting the edges in $E(G[V(H)]) – E(H)$. $\Box$

Lemma 2: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected, then $r(M)\ge |V(G)|-1$ and equality holds if and only if $M$ is the cycle matroid of $G$.

Proof. Order the vertices of $G$ in the order $(v_1,v_2,\ldots,v_n)$ such that, for each $i\ge 2$, the vertex $v_i$ has a neighbour among $\{v_1,\ldots,v_{i-1}\}$. The sets $E(G[\{v_1,v_2,\ldots,v_n\}]),\, E(G[\{v_1,v_2,\ldots,v_n\}]),\,\ldots, \,E(G[\{v_1\}])$ have strictly decreasing rank in $M$, so $r(M)\ge |V(G)|-1$.

Equality clearly holds when $M=M(G)$. Conversely suppose that equality holds. A routine variation on the proof of Lemma 1 proves that, for each subgraph $H$ of $G$, we have $r(E(H)) \le |V(H)|-1$. Then, by the first part of the proof, for each connected subgraph $H$ of $G$ we have $r(E(H)) = |V(H)|-1$. In particular, if $H$ is a circuit of $G$, then $E(H)$ is a circuit of $M$, and, if $H$ is a tree of $G$, then $E(H)$ is independent in $M$. Thus $M = M(G)$. $\Box$

The following result is an easy application of Lemmas 1 and 2.

Lemma 3: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected and $M$ is $3$-connected, then $G$ is $2$-connected.

Lemma 4: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected, $M$ is $3$-connected, and $|E(M)|\ge 4$, then $M$ is a framework matroid.

Proof. We may assume that among all connected weak frameworks for $M$ we have chosen $G$ with as many loops as possible. Since $M$ has no loops, if $G$ is not itself a framework of $M$, then there is a vertex $v$ of $G$ such that the set $X$ of edges incident with $v$ is the union of at least two distinct cocircuits of $G$. By Lemma 1 and the fact that $M$ is simple, there is at most one loop at $v$. Choose a cocircuit $C^*\subseteq X$ so that $X-C^*$ contains no loop of $G$. Now define $G’$ by replacing each edge $e=vw$ of $X-C^*$ with a loop at $w$. Note that $G’$ is a weak framework of $M$ and, since $G$ is $2$-connected, $G’$ is connected. However, this contradicts our choice of $G$ and that completes the proof.$\Box$

This proves that:

Theorem 2: The class of framework matroids contains all $3$-connected frame matroids and all $3$-connected lifted graphic matroids.

Represented matroids

A matrix with at most two nonzero nonzero entries in each column is called a frame matrix. Let $A_1$ and $A_2$ be matrices over a field $\bF$ with a common set $E$ of column indices. We say that $A_1$ and $A_2$ are row equivalent if $A_1$ can be obtained from $A_2$ by elementary row operations.

Problem 1: Given as input a matrix $A$, decide whether $A$ is row equivalent to a frame matrix.

Note that, if a matrix $A$ is row-equivalent to a frame matrix, then $M(A)$ is a frame matroid.

Conjecture 4: There is a polynomial-time algorithm that solves Problem 1.

We say that $A_1$ and $A_2$ are projectively equivalent if $A_1$ is row equivalent to a matrix $A_3$ that can be obtained from $A_2$ by column scaling. A signed incidence matrix is a frame matrix with entries in $\{0,\pm 1\}$ such that each column sums to zero. A lift of a matrix is a matrix obtained by appending a new row. A lifted signed-incidence matrix is a lift of a signed-incidence matrix.

Problem 2: Given as input a matrix $A$, decide whether $A$ is projectively equivalent to a lifted signed-incidence matrix.

Note that, if a matrix $A$ is projectively equivalent to a lifted signed-incidence matrix, then $M(A)$ is a lift of a graphic matroid.

Conjecture 5: There is a polynomial-time algorithm that solves Problem 2.

The amazing theorem

Let $A\in \bF^{V\times E}$ be a frame matrix with no all-zero column. The support of $A$ is the graph $G=(V,E)$ such that a vertex $v\in V$ is incident with an edge $e\in E$ if and only if the $(v,e)$-entry of $A$ is nonzero. If $A$ is a signed-incidence matrix with support $G$, then we say that $A$ is a signed incidence matrix of $G$.

The following remarkable fact came out of discussions with Bert Gerards and Geoff Whittle.

Theorem 3: Let $A$ be a matrix and let $M=M(A)$ be a framework matroid with framework $G$. Then either

• $A$ is projectively equivalent to a lift of the signed-incidence matrix of $G$, or
• $A$ is row equivalent to a frame matrix whose support is $G$.

Proof. By Lemma 2, we may assume that $r(M) = |V(G)|$. For each cocircuit $C$ of $M$ there is a vector $v$ in the row space of $A$ whose support is $C$. Therefore there is a frame matrix $A’$ whose support is $G$ and whose row space is contained in the row space of $A$. Now $G$ is a weak framework for $M(A’)$, so the rank of $A’$ is either $|V(G)|$ or $|V(G)|-1$. If $A’$ has rank $|V(G)|$, then $A$ is row equivalent to the frame matrix $A’$, as required. Thus we may assume that $A’$ has rank $|V(G)|-1$. Then, by Lemma 2, $M(A’)= M(G)$ and hence $A’$ is projectively equivalent to the signed incidence matrix of $G$. Finally, since the row space of $A’$ is contained in the row space of $A$ and $rank(A) = rank(A’)+1$, $A$ is row equivalent to a lift of $A’$. $\Box$

Theorem 3 some interesting consequences; the first of these is a striking converse to Theorem 2.

Corollary 1: For any field $\bF$, if $M$ is an $\bF$-representable framework matroid, then $M$ is either a frame matroid or a lifted graphic matroid.

Corollary 2: If $M$ is a $3$-connected matroid that has a representation by a frame matrix, then every representation of $M$ is either row equivalent to a frame matrix or is projectively equivalent to a lifted signed incidence matrix.

Corollary 3: If $M$ is a $3$-connected matroid that has a representation by a lifted signed incidence matrix, then every representation of $M$ is either projectively equivalent to a lifted signed incidence matrix or is row equivalent to a frame matrix.

Consider, for example, the matroid $R_{10}$. It is represented over GF$(3)$ by the “unsigned” incidence matrix of $K_5$. However, over GF$(2)$ it is represented by a lift of a signed incidence matrix of $K_5$.

References

[BC80] R.E. Bixby, W.H. Cunningham, Converting linear programs to network problems, Math. Oper. Res. 5 (1980), 321-357.
[Sey81] P.D. Seymour, Recognizing graphic matroids, Combinatorica 1 (1981), 75-78.
[Zas91] T. Zaslavsky, Biased graphs. II. The three matroids, J. Combin. Theory, Ser. B 51 (1991), 46-72.

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