betaFeedback

WorksMathematics

Triples in matroid circuits

Abstract

We prove that, if XX is a four-element independent set in a vertically 55-connected representable matroid MM, then either there is a circuit of MM that contains at least three elements of XX, or there is a representation AA of MM such that each column of AA has at most two non-zero elements and each of the columns indexed by XX has exactly one non-zero element. We also prove a version of this result without the connectivity assumptions.

Introduction

A frame matrix is a matrix in which each column has at most two non-zero entries. A unit-column is a column with exactly one non-zero element. If a matroid MM is represented by a frame matrix AA and XX is the set of elements in MM that index unit columns, then no circuit in MM can contain three or more elements in XX. We prove the following partial converse. Here two matrices are row-equivalent if they have the same row-space.

Theorem 1.1. Let MM be a vertically 5-connected matroid represented by a matrix AA. If XX is an independent set, with ∣X∣≥4|X| \ge4, then either there is a circuit of MM that contains at least three elements of XX, or AA is row-equivalent to a frame matrix A′A' and each element of XX indexes a unit column of A′A'.

Vertical 5-connectivity is necessary, which we discuss in § 2, but our main result has no connectivity restrictions. Roughly, Theorem 15.1 states that, if XX is an independent set, with ∣X∣≥4|X| \ge4, in a

2010 Mathematics Subject Classification. 05B35.

Jim Geelen (Department of Combinatorics and Optimization, University of Waterloo, Canada) was supported by grants from NSERC and the Office of Naval Research.

Bert Gerards (Sittard, The Netherlands).

Geoff Whittle (School of Mathematics and Statistics, Victoria University of Wellington, New Zealand) was supported by a grant from the Marsden Fund of New Zealand.

This project is also supported through a generous personal donation from Neil Robertson to the University of Waterloo. representable matroid MM and there is no circuit containing three or more elements of XX, then MM can be constructed from a frame matroid (as in Theorem 1.1) by attaching other matroids via 1-, 2-, 3-, and 4-sums. Moreover, the 4-sums attach onto planes spanned by three unit columns. This result is an important tool in our matroid minors project, which we discuss in the following section.

Motivation

We call a set XX of elements in a matroid MM coupled if there is no circuit in MM that contains three of more elements of MM. Note that XX is coupled if and only if there is no U2,3U_{2,3}-minor NN of MM with E(N)⊆XE(N) \subseteq X. Therefore, if XX is coupled in MM then it is also coupled in any minor of MM that contains XX.

Given three distinct elements aa, bb, and cc in a matroid MM, the three-elements problem is the problem of determining whether or not {a,b,c}\{a,b,c\} is coupled.

Binary matroids. The three-elements problem was solved for co-graphic matroids by Chakravarti and Robertson [1] and then extended to binary matroids by Seymour [9] who proved the following result.

Theorem 2.1. If {a,b,c}\{a,b,c\} is a coupled set in a vertically 4-connected, binary matroid MM, then MM is the cycle-matroid of a graph GG and aa, bb, and cc are incident with a common vertex in GG.

Note that if vv is the vertex of GG that is incident with aa, bb, and cc and AA is the matrix obtained from a signed incidence matrix of GG representing MM by deleting the row indexed by vv, then AA is a frame matrix and each of aa, bb, and cc indexes a unit column of AA.

Theorem 2.1 provides an efficient algorithm for solving the three-elements problem in a binary matroid M=M(A)M=M(A). Note that, adding points to the lines spanned by {a,b}\{a,b\}, {b,c}\{b,c\}, and {a,c}\{a,c\} does not affect whether or not {a,b,c}\{a,b,c\} is coupled; therefore we may assume that MM has an M(K4)M(K_4)-restriction NN containing aa, bb, and cc. In the case that MM is vertically 4-connected, we can test whether or not {a,b,c}\{a,b,c\} is coupled by simply testing whether MM is graphic. Indeed, if MM is graphic, then the minor NN will force aa, bb, and cc to be incident with a common vertex. In the case that MM is not vertically 4-connected, there is a vertical 3-separation (X,Y)(X,Y) with a,b,c∈Xa,b,c \in X. Now we can construct a binary extension of MM by adding (all possible) points spanned by both XX and YY, then deleting YY. It is routine to show that this does not affect whether or not {a,b,c}\{a,b,c\} is coupled (assuming that we decompose on vertical separations of minimum order first). This decomposition decreases the rank, so repeating in this way we will eventually reduce to the vertical 4-connected case.

Our main result (Theorem 15.1) is in fact a generalization of Theorem 2.1. To see the connection, we can construct a binary matroid M+M^{+} by coextending MM by a new element dd so that {a,b,c,d}\{a,b,c,d\} is a cocircuit in M+M^{+}. In binary matroids any circuit meets any cocircuit in an even number of elements. Therefore, {a,b,c}\{a,b,c\} is coupled in MM if and only if {a,b,c,d}\{a,b,c,d\} is coupled in M+M^{+}. It still requires some additional work to obtain Theorem 2.1, but the key observation is that, since {a,b,c,d}\{a,b,c,d\} is a cocircuit, the decomposition given by Theorem 15.1 will not involve 4-sums.

Intractability for general matroids. If TT is a triangle in a 3-connected non-binary matroid, then there is a U2,4U_{2,4}-minor containing {a,b,c}\{a,b,c\}; see Theorem 6.3. Note that TT will be a cocircuit in such a minor. Dually this gives the following result.

Theorem 2.2. If {a,b,c}\{a,b,c\} is a triad in a 3-connected matroid MM, then {a,b,c}\{a,b,c\} is coupled in MM if and only if MM is binary.

This result is interesting from a structural point-of-view, but it has some shortcomings with respect to algorithms. Seymour [11] showed that the problem of deciding whether or not a matroid is binary is intractable, under the rank-oracle model, and we will use a variation of that argument to show that the three-elements problem is also intractable.

For any integer n≥3n \ge3, we take MnM_n to be a rank-(n+1)(n+1) “binary spike with tip and co-tip”. Specifically, MnM_n is a binary matroid with ground-set {b0,b1,…,bn}∪{a0,a1,…,an}\{b_0,b_1,\ldots,b_n\} \cup\{a_0,a_1,\ldots,a_n\} where {b0,b1,…,bn}\{b_0,b_1,\ldots,b_n\} is a basis, each of {b0,b1,a1},…,{b0,bn,an}\{b_0,b_1,a_1\},\ldots,\{b_0,b_n,a_n\} is a triangle, and each of {a0,b1,a1},…,{a0,bn,an}\{a_0,b_1,a_1\},\ldots,\{a_0,b_n,a_n\} is a triad. It is easy to check that, MnM_n has at least 2n−12^{n-1} circuit-hyperplanes and that relaxing any one of these circuit-hyperplanes will result in a non-binary matroid. Now {a0,a1,b1}\{a_0,a_1,b_1\} is not contained in a circuit in MnM_n, but it is in each of the relaxations. Therefore we cannot safely conclude that {a0,a1,b1}\{a_0,a_1,b_1\} is coupled without explicitly checking the rank of exponentially many sets. That is, the three-elements problem cannot be solved in polynomial-time under the rank-oracle model.

We expect that the three-elements problem can be solved in polynomial-time when MM is given by a matrix representation. We also hope to find a complete structural characterization for coupled triples in represented matroids.

Vertical 5-connectivity is necessary. Consider the matroid MM represented by the following matrix over any field with characteristic different from 2,

[100011111100001001−1−1−1001100010−1−110−10−1010001−11−100−10−1−1].\left[ \begin{array}{c c c c|c c c|c c c c c c} 1&0&0&0&1&1&1&1&1&1&0&0&0\\ 0&1&0&0&1&-1&-1&-1&0&0&1&1&0\\ 0&0&1&0&-1&-1&1&0&-1&0&-1&0&1\\ 0&0&0&1&-1&1&-1&0&0&-1&0&-1&-1 \end{array} \right].

Note that

(a) M∣(B∪Y)M|(B \cup Y) is isomorphic to M(K5)M(K_5),

(b) BB is a cocircuit in MM and every pair of elements in BB spans an element in YY,

(c) every element in YY is spanned by two elements in XX, and

(d) M∣(B∪X)M|(B \cup X) is the dual of the non-Fano.

Using (c), the set XX is coupled in M∣(X∪Y)M|(X\cup Y) and, by (b), it remains coupled in MM. Moreover, MM is vertically 5-connected, since MM is spanned by M(K5)M(K_5). We leave it to the reader to check that MM cannot be represented by a frame matrix. We can use 4-sums to attach these matroids to frame representations to show that the 5-connectivity requirement in Theorem 1.1 is necessary.

The problem with this example is that there is a frame representation of M(K4)M(K_4) that does not extend to a frame representation of M(K5)M(K_5), so we can take a 4-sum of a frame representation and M(K5)M(K_5) such that the resulting matroid is not a frame representation. More generally, we can do the same thing for M(Kn)M(K_n), when n≥5n \ge5. There are other constructions, but a complete characterization, in the representable case, still looks achievable.

The two-linkage problem. Given distinct vertices s1s_1, t1t_1, s2s_2, t2t_2 in a graph GG, the two-linkage problem is the problem of deciding whether or not there exist two disjoint paths, one connecting s1s_1 to t1t_1 and the other connecting s2s_2 to t2t_2. This is in fact a special case of the three-elements problem for binary matroids. We may add edges a=s1s2a=s_1s_2, b=s1t2b=s_1t_2, and c=s2t2c=s_2t_2 without affecting whether or not the linkage exists. It is an easy exercise to verify that the linkage exists if and only if the elements aa, bb, and cc are contained in a circuit in M(G)∗M(G)^*. Using this, one can see that Seymour’s theorem (2.1) implies the following result that was proved independently by Seymour [8] and Thomassen [13].

Theorem 2.3. Let s1s_1, t1t_1, s2s_2, t2t_2 be disjoint vertices in a 4-connected graph GG. If there do not exist two disjoint paths one connecting s1s_1 to

t1t_1 and the other connecting s2s_2 to t2t_2, then GG admits a planar embedding with s1s_1, s2s_2, t1t_1, t2t_2 embedded in that order on the outer face.

Graph minors. The two-linkage problem plays an important role in the proof of the graph-minors structure theorem [7] of Robertson and Seymour. In particular, Theorem 2.3 is used in the proof of the “flatwall theorem” [6] which roughly states that, for k2≫k1≫t≫nk_2 \gg k_1 \gg t \gg n, given a k2×k2k_2 \times k_2-grid-minor in a graph GG with no KnK_n-minor, there is a subgraph HH of GG such that HH embeds in the plane “up to 3-separations”, HH includes a k1×k1k_1 \times k_1-sub-grid of our grid minor, and there is a set X⊆V(G)∖V(H)X \subseteq V(G) \setminus V(H) of at most tt vertices such that no vertex of GG outside HH and XX is connected to any vertex of HH except those on the outer face in the planar embedding. Our main result plays a similar role in structure theory for matroids represented over a finite field.

A Sylvester-Gallai Theorem for planes

As usual, we use the terms point, line, and plane for a flat of rank one, two, or three respectively. In particular, note that a point is a set, not an element. We say that two lines in a matroid are skew if their union has rank 4, and we call a line long if it has at least three points. The Sylvester-Gallai Theorem states that every rank-3 real-representable matroid has a two-point line; see [12, 2, 3]. Motzkin [4] observed that this result does not directly extend to rank-4, since the union of two skew long lines has no three-point plane. The problem of completely characterizing the rank-4 real-representable matroids that have no three-point plane remains open, but Motzkin proved a significant partial result, stated below.

A plane is called ordinary if it is the union of a line and a point. Thus, in a matroid without any long lines, an ordinary plane has only three points.

Lemma 3.1 (Motzkin’s Lemma). Every rank-4 real-representable matroid contains an ordinary plane.

In Section 10, we will apply Motzkin’s Lemma to gammoids, which are matroids that arise from connectivity in directed graphs. Specifically, a matroid MM on a set ZZ is a gammoid if there is a directed graph G=(V,E)G = (V, E), with Z⊆VZ \subseteq V, and a set X⊆VX \subseteq V such that the rank of each W⊆ZW \subseteq Z is equal to the maximum number of disjoint directed paths from WW to XX in GG. The class of gammoids is minor-closed; in fact a matroid is a gammoid if and only if it is a minor of a transversal matroid; see Oxley [5 Section 3.2]. Since transversal matroids are real-representable [5 Corollary 11.2.18], gammoids are also real-representable.

We guess that gammoids satisfy the following strengthening of Motzkin’s Lemma.

Conjecture 3.2. Every rank-4 gammoid either has a three-point plane or it is the union of two skew long-lines.

Connectivity in undirected graphs

The gammoids that we are interested in come from connectivity in undirected graphs; we can replace each edge with a pair of oppositely directed edges without affecting the connectivities between any two sets of vertices, so these are, in fact, gammoids.

We take the convention that the empty graph is connected. In a departure from matroid terminology, 3-connected graphs are not required to be simple.

For subgraphs AA and BB of a graph GG, we can define A∪BA \cup B and A∩BA \cap B, naturally, by taking intersections or unions of both the vertex sets and edge sets. A separation in a graph GG is a pair (A,B)(A,B) of subgraphs of GG such that G=A∪BG=A \cup B; the order of the separation is ∣V(A∩B)∣\lvert V(A \cap B)\rvert. We call a separation (A,B)(A,B) proper if V(A)∖V(B)V(A) \setminus V(B) and V(B)∖V(A)V(B) \setminus V(A) are both non-empty. For sets XX and YY of vertices, an (X,Y)(X,Y)-separation is a separation (A,B)(A,B) with X⊆V(A)X \subseteq V(A) and Y⊆V(B)Y \subseteq V(B). We define κG(X,Y)\kappa_G(X,Y) to be the minimum order of an (X,Y)(X,Y)-separation. Note that we do not require XX and YY to be disjoint.

Let XX be a set of vertices in a graph G=(V,E)G=(V,E). As discussed above, there is a gammoid K(G,X)K(G,X) on VV such that the rank of a set WW is κG(W,X)\kappa_G(W,X).

Tight sets. Let ee be an edge in a graph GG. We write Ge→zG_{e\to z} to denote the graph obtained from GG by contracting ee to a vertex zz. Let XX and ZZ be sets of vertices in a graph G=(V,E)G=(V,E). We say that ZZ is XX-tight, if, for each vertex v∈V∖Zv \in V \setminus Z, the connectivity from Z∪{v}Z \cup\{v\} to XX is ∣Z∣+1\lvert Z\rvert+ 1. In terms of the connectivity matroid, K(G,X)K(G,X), this says that ZZ is both independent set and a flat. In particular, an XX-tight triple is a three-point plane in K(G,X)K(G,X).

The notion of XX-tightness is very useful in matroid minors. For example, one can show that, if (G,T)(G,T) is a graft and ZZ is an XX-tight subset of TT, then we can contract all of GG down to XX keeping the TT-set of size at least ∣Z∣\lvert Z\rvert. That is essentially the content of Lemma 10.2, except that the lemma is not restricted to binary matroids.

The following result shows how to remove edges that are not incident with ZZ. There is a companion result, below, for removing edges incident with ZZ.

Lemma 4.1. Let XX and ZZ be sets of vertices in a graph G=(V,E)G=(V,E), let e=xye=xy be an edge of G−ZG-Z with y∉Xy\notin X. If ZZ is XX-tight in GG, then ZZ is XX-tight in at least one of G−eG-e or Ge→xG_{e\to x}.

Proof. Let k=∣X∣k=|X|. If ZZ is not XX-tight in Ge→xG_{e\to x}, then there is a (Z,X)(Z,X)-separation (A1,B1)(A_1,B_1) of order k+1k+1 in G−eG-e such that {x,y}⊆V(A1∩B1)\{x,y\}\subseteq V(A_1\cap B_1). If ZZ is not XX-tight in G∖eG\setminus e, then there is a (Z,X)(Z,X)-separation (A2,B2)(A_2,B_2) of order kk in G−eG-e such that y∈V(A2)∖V(B2)y\in V(A_2)\setminus V(B_2) and x∈V(B2)∖V(A2)x\in V(B_2)\setminus V(A_2). Note that

(A1∩A2,B1∪B2) and (A1∪A2,B1∩B2)(A_1\cap A_2,B_1\cup B_2)\text{ and }(A_1\cup A_2,B_1\cap B_2)

are both (Z,X)(Z,X)-separations in G−eG-e and, by submodularity, the sum of the orders of these separations is at most 2k+12k+1. Since {x,y}⊆V(A1∩B1)\{x,y\}\subseteq V(A_1\cap B_1),

(A1∩A2,(B1∪B2)+e) and ((A1∪A2)+e,B1∩B2)(A_1\cap A_2,(B_1\cup B_2)+e)\text{ and }((A_1\cup A_2)+e,B_1\cap B_2)

are both (Z,X)(Z,X)-separations in GG and the sum of the orders of these separations is at most 2k+12k+1. However, since xx is a vertex in both A1∩A2A_1\cap A_2 and (A1∪A2)+e(A_1\cup A_2)+e, this contradicts the fact that ZZ is XX-tight in GG. □

Next we show we can reduce the degree of each vertex in Z∖XZ\setminus X to two.

Lemma 4.2. Let XX and ZZ be sets of vertices in a graph G=(V,E)G=(V,E), and let z∈Z∖Xz\in Z\setminus X. If ZZ is XX-tight and zz has degree at least 3, then there is an edge ee incident with zz such that ZZ is XX-tight in G−eG-e.

Proof. Let k=∣X∣k=|X|. Consider constructing a new graph G+G^{+} by adding a twin z′z' of zz to GG. Since ZZ is XX-tight in GG, there exist k+1k+1 disjoint (Z∪{z′},X)(Z\cup\{z'\},X)-paths in G+G^{+}. Therefore there are (Z,X)(Z,X)-paths P0,P1,…,PkP_0,P_1,\ldots,P_k such that P0∪P1,P2,…,PkP_0\cup P_1,P_2,\ldots,P_k are disjoint and V(P0∩P1)={z}V(P_0\cap P_1)=\{z\}. Suppose that e=zye=zy is an edge incident with zz that is in neither P0P_0 nor P1P_1. We claim that ZZ is XX-tight in G−eG-e. Suppose otherwise and consider an (Z,X)(Z,X)-separation (A,B)(A,B) of order kk in G−eG-e with V(A)≠ZV(A)\ne Z. Since ZZ is XX-tight in GG, neither AA nor BB can contain both ends of ee. Thus z∈V(A)∖V(B)z\in V(A)\setminus V(B) and y∈V(B)∖V(A)y\in V(B)\setminus V(A). This is not possible, since the k+1k+1 paths P0,P1,P2,…,PkP_0,P_1,P_2,\ldots,P_k must each intersect V(A∩B)V(A\cap B) at distinct vertices. □

Matroid connectivity

We assume that the reader is familiar with matroid theory; we mostly follow the terminology and notation of Oxley [5]. There is a significant interplay between graphs and matroids in this paper. To make the connection relatively seamless, we use non-standard terminology for “separations” in a matroid.

Recall that the local connectivity between two sets XX and YY in a matroid MM is defined as

ΠM(X,Y):=r(X)+r(Y)−r(X∪Y).\Pi_M(X,Y) := r(X) + r(Y) - r(X \cup Y).

The Tutte connectivity of a set XX is

λM(X):=ΠM(X,E(M)∖X).\lambda_M(X) := \Pi_M(X,E(M) \setminus X).

A separation is a pair (A,B)(A,B) of sets in MM such that A∪B=E(M)A \cup B = E(M); the order of the separation is ΠM(A,B)\Pi_M(A,B). For two sets XX and YY in a matroid MM, an (X,Y)(X,Y)-separation is a separation (A,B)(A,B) with X⊆AX \subseteq A and Y⊆BY \subseteq B. The connectivity between two sets XX and YY, denoted by κM(X,Y)\kappa_M(X,Y), is defined as the minimum order of an (X,Y)(X,Y)-separation in MM. Note that this differs from the definition on Oxley [5 page 320] since we do not require that XX and YY are disjoint. Our definition is tantamount to making XX and YY disjoint by adding parallel copies of the common elements and then applying the definition in Oxley.

We recall that a vertical separation in a matroid MM is a separation (A,B)(A,B) of E(M)E(M) such that neither AA nor BB is spanning. We say that MM is vertically kk-connected if it has no vertical separation of order less than k−1k-1.

Note that, Oxley’s “kk-separations” are separations of order at most k−1k-1 here. Nevertheless, our usage of “kk-connected” and “vertically kk-connected” are consistent with Oxley’s definition.

For ease of reference, here are two well-known connectivity results that we use.

Theorem 5.1 (Oxley [5 Theorem 4.3.1].). If ee is an element in a connected matroid MM, then M∖eM\setminus e or M/eM/e is connected.

Theorem 5.2 (Tutte’s linking theorem; see Oxley [5 Theorem 8.5.2]). If XX and YY are disjoint sets of elements in a matroid MM and e∈E(M)∖(X∪Y)e \in E(M) \setminus(X \cup Y), then

max⁡(κM∖e(X,Y),κM/e(X,Y))=κM(X,Y).\max(\kappa_{M\setminus e}(X,Y),\kappa_{M/e}(X,Y)) = \kappa_M(X,Y).

Strands. Let NN be a restriction of a matroid MM. We call a set S⊆E(M)S \subseteq E(M) a strand for NN if ΠM(E(N),S)=1\Pi_M(E(N),S) = 1 and each pair of elements in SS is in series in M∣(E(N)∪S)M|(E(N) \cup S). The following result will be familiar to anyone who has thought about ear decomposition for matroids; Tutte [14] uses similar results in his algorithm for testing whether a binary matroid is graphic.

Lemma 5.3. If NN is a restriction of a matroid MM and e∈E(M)∖E(N)e \in E(M) \setminus E(N) is such that the component of MM that contains ee also contains at least one element of NN, then there is a strand for NN in MM that contains ee.

Proof. Suppose otherwise, and consider a counterexample with ∣M∣|M| minimum. Let CC be a circuit of MM that contains ee and at least one element of NN. We may assume that ee is not spanned by NN, since otherwise {e}\{e\} is already a strand. Thus there is some element, say f∈C∖{e}f \in C \setminus\{e\} that is not spanned by NN. By minimality, there is a strand SS for NN in M/fM/f that contains ee. But then, either SS or S∪{f}S \cup\{f\} is a strand for NN in MM. □

Modular flats

A pair (F1,F2)(F_1,F_2) of subsets of E(M)E(M) is modular if r(F1∩F2)=ΠM(F1,F2)r(F_1 \cap F_2) = \Pi_M(F_1,F_2). A set FF of elements is modular if (F,F′)(F,F') is a modular pair for each flat F′F' of MM. In a simple matroid a modular set is necessarily a flat. It is easy to see that modularity is preserved under minors. That is, if FF is a modular flat and e∈E(M)∖Fe \in E(M) \setminus F, then FF is modular in both M\eM\backslash e and M/eM/e. Moreover, if e∈Fe \in F, then F∖{e}F \setminus\{e\} is also modular in M/eM/e, but deleting elements of FF need not preserve modularity. The following result is well-known.

Lemma 6.1. For a set FF of elements in a matroid MM, the following are equivalent:

(1) FF is a modular set in MM,

(2) for each minor NN of MM containing M∣FM|F as a spanning restriction, each element of E(N)∖FE(N) \setminus F is either a loop or is in parallel with an element of FF.

(3) each strand of M∣FM|F in MM spans a non-loop element of FF.

Proof. If (1) fails, then there is a flat F′F' of MM such that (F,F′)(F,F') is not a modular pair. Let II be a maximal independent set of (M/F)∣F′(M/F)|F' and let N=M/IN = M/I. Note that F′∖IF' \setminus I is contained in the closure of FF in NN and rN(F∩F′)=rM(F∩F′)<ΠM(F,F′)=rN(F′∖I)r_N(F \cap F') = r_M(F \cap F') < \Pi_M(F,F') = r_N(F' \setminus I) so there is an element e∈F′∖Ie \in F' \setminus I that is not in parallel with any element of FF, so (2) fails.

If (2) fails, there is a maximal independent set II of M/FM/F and an element e∈E(M)∖Ie \in E(M) \setminus I, such that, in M/IM/I, ee is not a loop and is not in parallel with any element of FF. Let Y:=I∪{e}Y := I \cup\{e\}. Then $\Pi_M(F,Y) = 1 and yet YY does not span a non-loop element of FF. Since ⊓M(F,Y)=1\sqcap_M(F,Y)=1, there is a circuit of M∣(F∪Y)M|(F\cup Y) that contains an element of FF and an element of YY. By Lemma 5.3, YY contains a strand for M∣FM|F and, hence, (3) fails.

If (3) fails and SS is a strand of M∣FM|F in MM that does not span any non-loop element of FF, then (F,cl⁡M(S))(F,\operatorname{cl}_M(S)) is not modular, so (1) fails, as required.

A matroid is round if its ground-set cannot be covered by two hyperplanes. The next result was probably already known to Tutte [14] who used similar results in his algorithm for testing whether a binary matroid is graphic.

Lemma 6.2. Let XX be a modular set of elements in a matroid MM and let NN be a component of M/XM/X. If ZZ is the set of elements in XX that are spanned by E(N)E(N) in MM, then M∣ZM|Z is round.

Proof. Suppose that the result fails, and consider a counterexample (M,X,N)(M,X,N) with ∣M∣|M| minimum. By minimality, we have E(M)=X∪E(N)E(M)=X\cup E(N), X=ZX=Z, and MM is simple and connected. Since (M,X,N)(M,X,N) is a counterexample, there exist hyperplanes H1H_1 and H2H_2 of M∣XM|X such that X=H1∪H2X=H_1\cup H_2. Note that H1H_1 and H2H_2 are disjoint since otherwise we could contract the intersection. Consider an element ee in NN. By minimality N/eN/e is not connected, so, by Theorem 5.1, N\eN\backslash e is connected. Again applying minimality, E(N)\eE(N)\backslash e cannot span an element in both H1H_1 and H2H_2, so, up to symmetry, ⊓M(E(N)\e,H1)=0\sqcap_M(E(N)\backslash e,H_1)=0. But then ⊓M(E(N),H1)=1\sqcap_M(E(N),H_1)=1 and hence ∣H1∣=1|H_1|=1. Since H1H_1 and H2H_2 are both hyperplanes of M∣XM|X, we also have ∣H2∣=1|H_2|=1. Since MM is connected there is a circuit CC that contains both elements of XX. Now C\XC\backslash X is a strand for M∣XM|X, but C\XC\backslash X spans no element of XX, contrary to the fact that XX is modular.

Structure theory. Modular flats have an interesting connection with structure theory. The first result is an easy consequence of Seymour’s result [11] that U2,4U_{2,4} is 2-rounded; see Oxley [5 Proposition 12.3.8].

Theorem 6.3. If a triangle TT in a 3-connected matroid MM is modular, then MM is binary.

Proof. Let T={a,b,c}T=\{a,b,c\}. If MM is not binary, MM has a U2,4U_{2,4}-minor. Then, by the 2-roundedness of U2,4U_{2,4}, there is a U2,4U_{2,4}-minor NN that contains {a,b}\{a,b\}. We may assume that NN also contains cc; to see this consider what happens when cc is the last element removed when constructing NN. But then, by Lemma 6.1, TT is not modular in MM.

Here is an even more striking example, which is just Seymour’s Theorem 2.1 in disguise.

Theorem 6.4. Let N≅M(K4)N \cong M(K_4) be a restriction of a vertically 4-connected matroid MM. If E(N)E(N) is modular in MM, then MM is graphic.

Proof. Each triangle in NN is modular in MM, so, by Theorem 6.3, MM is binary. Now we obtain the result by applying Theorem 2.1 to a triad {a,b,c}\{a,b,c\} of NN. □

Modular sums. The following result is easy and well-known; we omit the proof. Here, we are primarily interested in the case that N=U2,3N = U_{2,3}.

Lemma 6.5. Let NN be a matroid and let (F1,F2)(F_1,F_2) be a modular pair of flats in a matroid MM with E(M)=F1∪F2E(M) = F_1 \cup F_2. If E(N)⊆F1E(N) \subseteq F_1, then NN is a minor of MM if and only if NN is a minor of M∣F1M|F_1.

The matroid MM is a generalized parallel connection (or modular sum) of M∣F1M|F_1 and M∣F2M|F_2; see Oxley [5 Section 11.4]. The lemma shows that we can use modular sums to build up matroids that avoid NN as minor. We assume that M/F1M/F_1 is connected, since otherwise we could construct MM via a series of modular sums, treating the components one at a time.

Note that, by Lemma 6.2, the matroid M∣(F1∩F2)M|(F_1 \cap F_2) is round. The cycle matroid of a graph GG is round if and only if GG is complete. This is why we only see clique-sums in the graph minors structure theory. Roundness is significantly less prescriptive for general matroids. For example, all 3-connected rank-3 matroids are round, giving rise to the possibility of other interesting 4-sums.

Planted matroids and modularity

One useful property of representable matroids is that when ⊓M(X,Y)>0\sqcap_M(X,Y) > 0 we can extend MM by a non-loop element ee in the span of both XX and YY. We rely more on such extension properties than on specific coordinatizations. For this reason it is convenient to think of a representation of a simple matroid as a restriction of a (possibly infinite) projective geometry of finite rank. Moreover, we will also consider representations of non-simple matroids, so we need to add loops and parallel elements to the projective geometry.

We are almost exclusively interested in finite matroids, but for the following brief discussion we allow infinite matroids of finite rank. We say that a matroid is modular if each pair (F1,F2)(F_1,F_2) of flats is modular. Projective geometries are modular and any matroid that simplifies to a projective geometry is also modular. A modular space is a (possibly infinite) connected modular matroid with finite rank. The connectivity requirement ensures that every line in a modular space has at least three points.

Note that rank-3 modular spaces simplify to projective planes, whose structure is known to exhibit some wild behaviour. However, by Birkoff’s Fundamental Theorem on Projective Geometry, modular spaces of rank at least 4 simplify to projective geometries over division rings. Nevertheless, we do not need to understand the underlying algebraic structure of modular spaces.

Henceforth, matroids are finite. A planted matroid is a pair (M,Q)(M,Q) where QQ is a modular space and MM is a finite restriction of QQ. To avoid ambiguity, we will call the flats of QQ subspaces and the closure in QQ of a set ZZ of elements will be called the span of ZZ, whereas within MM we will use the more familiar terms flat and closure. We say that two finite sets V1V_1 and V2V_2 in QQ are point-wise equivalent if there is a bijection ϕ:V1→V2\phi: V_1 \to V_2 such that for each v∈V1v \in V_1 either v=ϕ(v)v = \phi(v), or {v,ϕ(v)}\{v,\phi(v)\} is a parallel pair, or vv and ϕ(v)\phi(v) are both loops.

If (M1,Q)(M_1,Q) and (M2,Q)(M_2,Q) are planted matroids on a common ambient space then we can define the intersection and union of M1M_1 and M2M_2 naturally as

M1∩M2:=Q∣(E(M1)∩E(M2)),andM_1 \cap M_2 := Q|(E(M_1) \cap E(M_2)), \quad\text{and}
M1∪M2:=Q∣(E(M1)∪E(M2)).M_1 \cup M_2 := Q|(E(M_1) \cup E(M_2)).

For a planted matroid (M,Q)(M,Q) and X⊆E(Q)X \subseteq E(Q) we denote M∪(Q∣X)M \cup(Q|X) by M∪XM \cup X and when X={e}X = \{e\} we simply write M+eM + e.

Minors behave nicely for planted matroids. For e∈E(M)e \in E(M), the deletion of ee is (M,Q)\e:=(M\e,Q)(M,Q)\backslash e := (M\backslash e,Q) and the contraction of ee is (M,Q)/e:=(M/e,Q/e)(M,Q)/e := (M/e,Q/e). Sometimes we will contract an element e∈E(Q)∖E(M)e \in E(Q) \setminus E(M), but we do not consider this a minor. We denote (M∪{e})/e(M \cup\{e\})/e by M//eM//e, and we call this a projection. For an element e∈E(M)e \in E(M), we define the projection, M//eM//e, to be the matroid obtained from M/eM/e by adding ee back as a loop.

It is worth mentioning, but not important for us, that planted matroids do not behave well under duality, but that is only due to the afore-mentioned issues with rank-3 modular spaces. Every rank-3 matroid MM extends to a modular space, but that need not be the case for the dual.

Decomposition on a separation

In Section 6 we considered the composition of matroids using modular sums; here we consider decomposition. Let (M,Q)(M,Q) be a planted matroid. For a matroid NN with E(N)⊆E(M)E(N) \subseteq E(M) we want to determine whether MM has NN as a minor. Further suppose that we have a separation (A,B)(A, B) of order kk in MM with E(N)⊆AE(N) \subseteq A. In this section we discuss the issues that arise in decomposing MM across the separation (A,B)(A, B). For notational reasons it is convenient to assume that AA and BB are disjoint. If this is not the case, we will replace the elements of BB that are also in AA with parallel copies, and leave AA unchanged. Let MA=Q∣AM_A = Q|A and MB=Q∣BM_B = Q|B.

Let FF be the rank-kk subspace of QQ containing the points in the span of both AA and BB and let ZZ be a minimal spanning subset of FF such that Q∣ZQ|Z is modular in MB∪ZM_B \cup Z. By Lemma 6.1, each strand SS of MAM_A in MM spans exactly one element in ZZ and, by minimality, each element in ZZ is spanned by some strand of MAM_A in MM. Thus ZZ is finite and uniquely determined up to point-wise equivalence. We call the matroid Q∣ZQ|Z a torso of (A,B)(A, B) in (M,Q)(M, Q). Moreover, since it is uniquely determined up to point-wise equivalence we may also call it the torso of (A,B)(A, B) in (M,Q)(M, Q).

Suppose that TT is the torso of (A,B)(A, B) in (M,Q)(M, Q) and consider decomposing MM into MA∪TM_A \cup T and MB∪TM_B \cup T. Note that M∪TM \cup T is a modular sum of MA∪TM_A \cup T and MB∪TM_B \cup T. It follows from Lemma 6.5 that, if MA∪TM_A \cup T does not contain NN as a minor, then neither does MM. The converse is, however, not as clear-cut.

As noted above, each element ee in the torso is in the span of some strand SS for NN. We say that ee is a base-point for the strand SS. In M∪S∪{e}M \cup S \cup\{e\}, the set SS is a series-class and when we contract all but one element, say ff, the pair {e,f}\{e, f\} will be parallel. Thus an element in the torso of (A,B)(A, B) is any point in the span of AA onto which we can contract elements of MM, without reducing the rank of MAM_A.

One difficulty is that, while the elements in the torso record the points to which we can contract elements, we cannot necessarily contract two prescribed elements down simultaneously. This issue is addressed in graphs by the two-linkage problem, but it is not a problem that we know how to address in matroids. We say that a restriction T′T' of the torso TT is realizable if there are disjoint sets CC and ZZ in BB such that r(C∪A)=r(C)+r(A)r(C \cup A) = r(C) + r(A), and ZZ is point-wise equivalent with E(T′)E(T') in Q//CQ//C.

Due to the issues raised by realizability, it is possible that MA∪TM_A \cup T contains NN as a minor whereas MM does not. Nevertheless, we can decompose across separations of order at most 22.

Lemma 8.1. Let TT be the torso of a separation (A,B)(A, B) of order at most 22 in a planted matroid (M,Q)(M, Q) and let NN be a matroid with E(N)⊆AE(N) \subseteq A. Then NN is a minor of MM if and only if NN is a minor of (Q∣A)∪T(Q|A) \cup T.

Proof. Let MA=(Q∣A)∪TM_A=(Q|A)\cup T. For the non-trivial direction, suppose that NN is a minor of MAM_A and let (C,D)(C,D) be a partition of E(T)E(T) such that NN is a minor of MA/C\DM_A/C\backslash D. We need to prove that NN is a minor of MM. Since singletons are realizable, we may assume that CC contains at least two elements in TT. But then CC spans TT and, hence, MA/C\D=MA/E(T)=M/BM_A/C\backslash D=M_A/E(T)=M/B. So NN is a minor of MM, as required. □

We are, of course, interested in the case that N≅U2,3N\cong U_{2,3}, for which we can immediately draw the following conclusion.

Lemma 8.2. Let TT be the torso of a separation (A,B)(A,B) of order at most 2 in a planted matroid (M,Q)(M,Q) and let X⊆AX\subseteq A. Then XX is coupled in MM if and only if XX is coupled in (Q∣A)∪T(Q|A)\cup T.

Rooted matroids

A rooted matroid is a triple (M,Q,V)(M,Q,V) such that (M,Q)(M,Q) is a planted matroid, and VV is an independent set in QQ; we refer to VV as the vertex-set of the rooted matroid. Note that the vertices need not be contained in MM. We say that a rooted matroid (M,Q,V)(M,Q,V) is coupled if VV is coupled in M∪VM\cup V. To avoid ugly terminology, we will abbreviate “coupled rooted matroid” to coupled matroid.

We say that a rooted matroid (N,Q′,V′)(N,Q',V') is a minor of a rooted matroid (M,Q,V)(M,Q,V) if (N,Q′)(N,Q') is a minor of (M,Q)(M,Q) and V′⊆VV'\subseteq V.

Bridges. A bridge of (M,Q,V)(M,Q,V) is a rooted matroid (B,Q,Z)(B,Q,Z) such that E(B)E(B) is the ground-set of a component of M//VM//V and ZZ is a minimal subset of VV such that ⊓Q(Z,E(B))=⊓Q(V,E(B))\sqcap_Q(Z,E(B))=\sqcap_Q(V,E(B)). Since VV is independent, the set ZZ is uniquely determined; ZZ is the set of elements in VV such that B∪ZB\cup Z is a component of B∪VB\cup V. We call ZZ the set of attachments of the bridge. We say that a bridge is trivial if it is spanned by VV; if (B,Q,Z)(B,Q,Z) is a trivial bridge, then ∣B∣=1|B|=1.

Torsos of rooted matroids. The torso of a rooted matroid (M,Q,V)(M,Q,V) is the torso of the separation (V,E(M))(V,E(M)) in (M∪V,Q)(M\cup V,Q). If TT is the torso of (M,Q,V)(M,Q,V) then we call (T,Q,V)(T,Q,V) the rooted torso of (M,Q,V)(M,Q,V). The following lemma is an immediate consequence of Lemma 6.2.

Lemma 9.1. If TT is the torso of a bridge (B,Q,X)(B,Q,X) of a rooted matroid (M,Q,V)(M,Q,V), then TT is round.

We view a rooted matroid (M,Q,V)(M,Q,V) as way of building (M,Q)(M,Q) via modular sums. Let (B1,Q,V1),…,(Bk,Q,Vk)(B_1,Q,V_1),\ldots,(B_k,Q,V_k) be the bridges of (M,Q,V)(M,Q,V) and let TT be the torso. Now let T1,…,TkT_1,\ldots,T_k be the torsos of the bridges (B1,Q,V1),…,(Bk,Q,Vk)(B_1,Q,V_1),\ldots,(B_k,Q,V_k). To avoid ambiguities caused by point-wise equivalence, we take T1,…,TkT_1,\ldots,T_k as restrictions of TT. Now the rooted matroid (M∪T,Q,V)(M \cup T,Q,V) is obtained from (T,Q,V)(T,Q,V) by attaching the “extended bridges” (B1∪T1,Q,V1),…,(Bk∪Tk,Q,Vk)(B_1\cup T_1,Q,V_1),\ldots,(B_k\cup T_k,Q,V_k) using modular sums; finally, we obtain (M,Q)(M,Q) as a restriction of (M∪V∪T,Q)(M\cup V\cup T,Q).

Frameworks and patchworks. A framework is a rooted matroid (M,Q,V)(M,Q,V) such that each element of MM is spanned by a set of at most two elements of VV. Equivalently, (M,Q,V)(M,Q,V) is a framework if and only if VV spans E(M)E(M) in QQ and (M,Q,V)(M,Q,V) is coupled. More generally, a rooted matroid (M,Q,V)(M,Q,V) is coupled if and only if the rooted torso of (M,Q,V)(M,Q,V) is a framework. Frameworks are maintained under taking minors.

Lemma 9.2. If (M,Q,V)(M,Q,V) is a framework, CC and DD are disjoint sets in MM, and V′V' is a maximal independent subset of VV in Q//CQ//C, then (M∖D/C,Q//C,V′)(M\setminus D/C,Q//C,V') is a framework.

Proof. Inductively it suffices to consider the case that ∣C∪D∣=1|C\cup D|=1, which we leave to the reader. □

We say that a bridge (B,Q,Z)(B,Q,Z) of a rooted matroid (M,Q,V)(M,Q,V) is a patch or a kk-patch if k=∣Z∣≤3k=|Z|\le3 and the rooted torso of (B,Q,Z)(B,Q,Z) is a framework. A rooted matroid (M,Q,V)(M,Q,V) is a patchwork if each of its bridges is a patch. Patchworks are also maintained under taking minors.

Lemma 9.3. If (M,Q,V)(M,Q,V) is a patchwork, CC and DD are disjoint sets in MM, and V′V' is a maximal independent subset of VV in Q//CQ//C, then (M∖D/C,Q//C,V′)(M\setminus D/C,Q//C,V') is a patchwork.

Proof. Again it suffices to consider the case that ∣C∪D∣=1|C\cup D|=1, which we leave to the reader. □

Our main result, Theorem 15.1, says that: if a rooted matroid (M,Q,X)(M,Q,X) is coupled, then there is an independent set VV in QQ containing XX such that (M,Q,V)(M,Q,V) is a patchwork.

Extending a framework

The results in this section prove our main theorem (Theorem 15.1) in the special case that MM is a one-element extension of a framework. For a rooted matroid (M,Q,V)(M,Q,V) and an element ee in QQ that is spanned by VV, the attachment-set of ee is the minimal subset of VV that spans ee; since VV is independent, this is well-defined.

Skeletons. Let (M,Q,V)(M,Q,V) be a framework. The skeleton of a framework (M,Q,V)(M,Q,V) is the graph G=(V,E′)G=(V,E') defined as follows: E′E' is the set of non-loop elements of MM and the set of ends of an edge e∈E′e\in E' is the attachment-set of ee in the framework. It is common practice to add the loops of MM as loop edges of GG at arbitrary vertices, but we choose to omit them.

Let GG be the skeleton of (M,Q,V)(M,Q,V). A cycle CC of GG is called balanced if E(C)E(C) is a cycle of MM. Let B\mathcal{B} denote the set of all balanced cycles of GG. The pair (G,B)(G,\mathcal{B}) is a biased graph and MM is the frame matroid determined by (G,B)(G,\mathcal{B}); see Zaslavsky [15]. We assume that the reader is familiar with these notions, but we will review some of the highlights.

Let HH be a subgraph of GG and let X=E(H)X=E(H). We say that HH is balanced if each cycle of HH is balanced. If HH is balanced then M∣XM|X is graphic, but the converse need not hold. The rank of XX in MM is ∣V(H)∣−c|V(H)|-c, where cc is the number of balanced components of HH.

We note that any element of VV that is contained in MM will be both a vertex of GG and a loop at that vertex. This causes some ambiguity when we write G−eG-e, but the meaning will be clear from the context.

As we have already seen, frameworks are preserved under taking minors. For any element of MM, the deletion (M\e,Q,V)(M\backslash e,Q,V) is a framework with skeleton G−eG-e. When ee is an edge with distinct ends aa and bb in GG, in the contraction Q//eQ//e the elements aa and bb will be parallel. So (M/e,Q//e,V∖{b})(M/e,Q//e,V\setminus\{b\}) will be a framework whose skeleton is obtained from G/eG/e by deleting any loops of M/eM/e. Finally consider the case that ee is a non-balanced loop at a vertex aa. Then (M/e,Q//e,V∖{a})(M/e,Q//e,V\setminus\{a\}) is a framework; the skeleton G′G' is obtained from GG by first deleting any loops of M/eM/e, then we remove the vertex aa from the vertex-set and from the end-set of any edge. (So the non-loop edges that are incident with aa in GG become loop edges in G′G'.)

For a framework (M,Q,V)(M,Q,V), let TT be the attachment set of an element e∈E(Q)e\in E(Q) that is spanned by VV. For any non-empty subset XX of VV with T∩X≠∅T\cap X\ne\varnothing, we have ΠQ(X,(V∖X)∪{e})=1\Pi_Q(X,(V\setminus X)\cup\{e\})=1, so, up to point-wise equivalence, there is a non-loop unique element e′∈Qe'\in Q that is spanned by both XX and (T∖X)∪{e}(T\setminus X)\cup\{e\}. Note that, ee and e′e' are parallel in Q//(V∖X)Q//(V\setminus X). We call e′e' the image of ee on XX. If T⊆XT\subseteq X, then ee and e′e' will be point-wise equivalent, otherwise, when X∖T≠∅X\setminus T\ne\varnothing, the set (T∖X)∪{e,e′}(T\setminus X)\cup\{e,e'\} is a circuit.

Now, consider effect, on the attachment set, of contracting an edge f=xyf=xy of the skeleton of (M,Q,V)(M,Q,V); here we are allowing x=yx=y. Let T′T' be the attachment set of ee in (M/f,Q//f,V∖{y})(M/f,Q//f,V\setminus\{y\}). If x=yx=y, then T′=T∖{y}T'=T\setminus\{y\}. Consider the alternative case that x≠yx\ne y. If TT does not contain both xx and yy, then T∪{e}T\cup\{e\} remains a circuit in Q/fQ/f and hence T′=TT'=T. This leaves the more interesting case that x,y∈Tx,y \in T, which depends on the location of the image e′e' of ee on the line {x,y}\{x,y\}. If ff is point-wise equivalent with e′e', then (T∖{x,y})∪{e}(T \setminus\{x,y\}) \cup\{e\} is a circuit in Q//fQ//f, so T′=T∖{x,y}T'=T \setminus\{x,y\}. Otherwise, when {e′,f}\{e',f\} is independent, (T∖{x,y})∪{e,e′}(T \setminus\{x,y\}) \cup\{e,e'\} remains a circuit in Q//fQ//f and {x,e′}\{x,e'\} become a parallel pair. Thus T′=T∖{y}T'=T \setminus\{y\}.

Our first result uses the definition of “XX-tight” from Section 4.

Lemma 10.1. Let GG be the skeleton of a framework (M,Q,V)(M,Q,V), let TT be the attachment set of an element e∈E(Q)∖E(M)e \in E(Q) \setminus E(M) that is spanned by VV, and let X⊆VX \subseteq V. If M∪XM \cup X is connected, and there is a set WW of vertices in TT that is XX-tight, then there is a circuit in M∪X∪{e}M \cup X \cup\{e\} that contains ∣W∣|W| or more elements of XX.

Proof. Consider a counterexample with ∣M∣|M| minimum; thus no two vertices in XX are adjacent. Let HH be a complete graph on XX. It is easy to see that G∪HG \cup H cannot have a cut-edge, since such an element could be contracted. Then, by Lemma 4.1, every edge of GG is incident with WW. Moreover, since WW is XX-tight, we have V=W∪XV = W \cup X. Furthermore, by minimality, no two vertices of WW are adjacent in GG. Finally, by Lemma 4.2, each vertex in W∖XW \setminus X has degree 2. We may assume that WW is not contained in XX since otherwise the result clearly holds. Moreover, since WW is XX-tight, there is no circuit in GG. Let x∈Xx \in X be a degree-1 vertex of GG, let w∈Ww \in W be its neighbour, and let y∈X∖{x}y \in X \setminus\{x\} be the other neighbour of ww. Let fxf_x and fyf_y be the edges with ends {w,x}\{w,x\} and {w,y}\{w,y\} respectively.

Note that (W∖{w})∪{x}(W \setminus\{w\}) \cup\{x\} is XX-tight in G−wG-w. If x∈Tx \in T, then we obtain a contradiction by contracting fyf_y. On the other hand, when x∉Tx \notin T, then we obtain a contradiction by contracting fxf_x. □

The following result connects tightness with our earlier Sylvester-Gallai-type results. We recall that K(G,X)K(G,X) is the matroid on V(G)V(G) such that the rank of a set Z⊆V(G)Z \subseteq V(G) is the connectivity from ZZ to XX.

Lemma 10.2. Let GG be the skeleton of a framework (M,Q,V)(M,Q,V), let TT be the attachment set of an element e∈E(Q)∖E(M)e \in E(Q) \setminus E(M) that is spanned by VV, and let X⊆VX \subseteq V. If GG is 2-connected and K(G,X)∣TK(G,X)|T has a three-point plane, then there is a circuit in M∪X∪{e}M \cup X \cup\{e\} that contains three or more elements of XX.

Proof. Since GG is 2-connected, K(G,X)K(G,X) is simple. Let PP be a three-point plane in K(G,X)∣TK(G,X)|T. Now let (A,B)(A,B) be a (P,X)(P,X)-separation in GG of order 3 such that V(A)V(A) is the flat of K(G,X)K(G,X) that is spanned by PP. Note that V(A∩B)V(A \cap B) is XX-tight in BB and, since PP is a three-point

plane in K(G,X)K(G, X), we have V(A)∩T=PV(A) \cap T = P. Therefore, we can contract PP onto V(A∩B)V(A \cap B) and apply Lemma 10.1 to get the result. □

The following result is not specifically required, but it does show the strength of the machinery that we have developed.

Lemma 10.3. Let GG be the skeleton of a framework (M,Q,V)(M, Q, V), let TT be the attachment set of an element e∈E(Q)∖E(M)e \in E(Q) \setminus E(M) that is spanned by VV, and let X⊆VX \subseteq V. If GG is 3-connected and κG(T,X)≥4\kappa_G(T, X) \ge4, then there is a circuit in M∪X∪{e}M \cup X \cup\{e\} that contains three or more elements of XX.

Proof. Since GG is 3-connected and κG(T,X)≥4\kappa_G(T, X) \ge4, the gammoid K(G,X)K(G, X) has no triangles and has rank at least 4. Since κG(T,X)≥4\kappa_G(T, X) \ge4, the restriction K(G,X)∣TK(G, X)|T has rank at least 4. Then, by Motzkin’s Lemma, K(G,X)∣TK(G, X)|T has a three-point plane. (Motzkin’s Lemma, as stated, is for rank-four matroids, but we can reduce to rank four by truncation.) Now the result follows from Lemma 10.2. □

Extending into the torso of a patchwork

Our main result (Theorem 15.1) is that every coupled matroid (M,Q,X)(M, Q, X) extends to a patchwork. We prove the theorem via induction, resulting in the case that, for some element ee in MM, there is a patchwork (M∖e,Q,V)(M\setminus e, Q, V) such that ee is spanned by VV. At that point, it is easy to imagine (M∖e,Q,V)(M\setminus e, Q, V) as a framework, allowing us to apply the results from Section 10. However, we need to be careful since there are restrictions of the torso that are not realizable. The results in this section address that problem.

We recall that the rooted torso (T,Q,V)(T, Q, V) of a coupled matroid (M,Q,V)(M, Q, V) is a framework. We refer to the skeleton of (T,Q,V)(T, Q, V) as the skeleton of (M,Q,V)(M, Q, V).

We start by showing that two vertices are adjacent in the skeleton if and only if there is a patch containing the vertices as attachments; we omit the more obvious direction.

Lemma 11.1. If GG is the skeleton of a coupled matroid (M,Q,V)(M, Q, V) and (B,Q,Z)(B, Q, Z) is a bridge of (M,Q,V)(M, Q, V), then the vertices in ZZ are pairwise adjacent in GG.

Proof. Suppose that there are two distinct non-adjacent vertices x,y∈Zx, y \in Z in GG. Let TT be the torso of (B,Q,Z)(B, Q, Z). By the definition of the attachment set there is an element of TT that is not spanned by Z−xZ - x and there is an element of TT that is not spanned by Z−yZ - y. However, (T,Q,Z)(T, Q, Z) is a framework. Thus we can cover TT by two proper flats (those spanned by Z−xZ - x and Z−yZ - y), contrary to Lemma 9.1. □

We would ideally like to take a minor of a patchwork to get a framework with the same skeleton (up to simplification). This is not always possible, but the following result meets our needs.

Lemma 11.2. If (P,Q,Z)(P,Q,Z) is a 3-patch in a patchwork (M,Q,V)(M,Q,V), then there is a triangle TT in the torso of (P,Q,Z)(P,Q,Z) such that Q∣(Z∪T)Q\mid(Z\cup T) is isomorphic to M(K4)M(K_4) and each two-element subset of TT is realizable.

Proof. Let Z={x,y,z}Z=\{x,y,z\}. Since P∪ZP\cup Z is connected, there is a circuit CC in P∪ZP\cup Z that contains yy and zz. Since ZZ is coupled, x∉Cx\notin C. Since P∪ZP\cup Z and P//ZP//Z are both connected, so is (P∪{x})//{y,z}(P\cup\{x\})//\{y,z\}. By Lemma 5.3, there is a strand SS for (C∖{y,z})(C\setminus\{y,z\}) in (P∪{x})//{y,z}(P\cup\{x\})//\{y,z\} that contains xx. Let A=C∪SA=C\cup S. Note that

(i) AA is independent in QQ,

(ii) CC is a circuit in Q∣AQ\mid A

(iii) Q(A)Q(A) is connected and has corank 2, and

(iv) ⊓Q(A∖Z,Z)=2\sqcap_Q(A\setminus Z,Z)=2.

The torso TT of (A∖Z,Q,Z)(A\setminus Z,Q,Z) spans a line and by Lemma 11.1, there are at least three elements in TT. One of those elements, say aa, is at the point where the spans of C∖{y,z}C\setminus\{y,z\} and {y,z}\{y,z\} meet. Thus {y,z,a}\{y,z,a\} is a triangle. Since (A∖Z,Q,Z)(A\setminus Z,Q,Z) is coupled, every point on TT must lie on one of the lines spanned by two of {x,y,z}\{x,y,z\}, and since Q∣AQ\mid A is connected, they cannot all lie on the line spanned by {y,z}\{y,z\}. Then TT must be a triangle and there exist elements b,c∈Tb,c\in T such that {b,x,y}\{b,x,y\} and {c,x,z}\{c,x,z\} are both triangles. Thus Q∣(T∪Z)Q\mid(T\cup Z) is isomorphic to M(K4)M(K_4). Now (Q∣A)/Z(Q\mid A)/Z is connected and has corank 2, so it contains a triad, say A′A'. Let WW be the matroid obtained from Q∣(A∪T)Q\mid(A\cup T) by contracting A∖A′A\setminus A'. Note that TT is a modular triangle in WW and A′A' is a triad. Now by contracting different elements of A′A', we see that any two-elements of TT is realizable, as required. □

The following result is the upgrade of Lemma 10.2 to patchworks.

Lemma 11.3. Let GG be the skeleton of a patchwork (M,Q,V)(M,Q,V), let TT be the attachment set of an element e∈E(Q)∖E(M)e\in E(Q)\setminus E(M) that is spanned by VV, and let X⊆VX\subseteq V. If GG is 2-connected and K(G,X)∣TK(G,X)\mid T has a three-point plane, then there is a circuit in M∪X∪{e}M\cup X\cup\{e\} that contains three or more elements of XX.

Proof. Let WW be the torso of (M,Q,V)(M,Q,V). By Lemma 11.2, there is a restriction W′W' of WW such that

(a) every pair of adjacent vertices in GG remain adjacent in the skeleton of (W′,Q,V)(W',Q,V), and

(b) every independent subset of W′W' is realizable in (M,Q,V)(M,Q,V). By Lemma 10.2, there is a circuit CC in X∪W′X \cup W' that contains at least three elements in XX. Since C∖XC \setminus X is realizable, there is a circuit in M∪X∪eM \cup X \cup e that contains at least three elements in XX. □\square

We now come to the main result of this section. The statement is a bit convoluted which is in part due to the intended application and in part due to the inductive proof. For a graph GG we write si⁡(G)\operatorname{si}(G) for the simplification of GG; that is we delete all loops and all but one edge from each parallel class.

Lemma 11.4. Let GG be the skeleton of a patchwork (M,Q,V)(M,Q,V), let TT be the attachment set of an element e∈E(Q)∖E(M)e \in E(Q) \setminus E(M) that is spanned by VV, and let X⊆VX \subseteq V. If

(i) κG(T,X)≥4\kappa_G(T,X) \ge4,

(ii) the vertices in XX are pairwise adjacent in GG,

(iii) GG is 22-connected and si⁡(G)\operatorname{si}(G) is a subdivision of a 33-connected graph, and

(iv) for each degree-two vertex vv in si⁡(G)\operatorname{si}(G), there is a 33-patch (B,Q,Z)(B,Q,Z) of (M,Q,V)(M,Q,V) such that v∈Zv \in Z and such that BB spans ZZ,

then there is a circuit in M∪X∪{e}M \cup X \cup\{e\} that contains three or more elements of XX.

Proof. Suppose not and consider a counterexample ((M,Q,V),e,T,X)((M,Q,V),e,T,X) with ∣V∣|V| minimum. Since GG is 22-connected, K(G,X)K(G,X) is simple. Moreover, since the attachments of any 33-patch are pairwise adjacent, by (iv), there are no two adjacent vertices of degree 22 in si⁡(G)\operatorname{si}(G). By Motzkin’s Lemma, K(G,X)∣TK(G,X)|T has an ordinary plane PP. By Lemma 11.3, PP is not a three-point plane, so PP is the union of a long line LL and a point {v}\{v\}. Consider an (L,X)(L,X)-separation (A,B)(A,B) of order 22 in GG such that V(A)V(A) is the closure of LL in K(G,X)K(G,X). Let xx and yy be the two vertices in A∩BA \cap B. Every other vertex in AA has degree-22 in si⁡(G)\operatorname{si}(G) and is adjacent to only xx and yy. Since LL is a long line, there are at least three vertices of TT in AA. It follows easily from minimality that every vertex in AA is in TT.

Consider a vertex z∈V(A)∖{x,y}z \in V(A) \setminus\{x,y\} and let (B,Q,Z)(B,Q,Z) be a 33-patch of (M,Q,V)(M,Q,V) such that z∈Zz \in Z and such that BB spans ZZ. Note that Z={x,y,z}Z = \{x,y,z\}. Our goal is to find a strand SS in (B,Q,Z)(B,Q,Z), whose base-point is not in the the line spanned by {x,y}\{x,y\}, such that the attachment set of ee in (M/S,Q//S,V∖{z})(M/S,Q//S,V\setminus\{z\}) is T−{z}T-\{z\}. In doing this, we may lose the edge connecting xx and yy, but that only happens in the case that ∣L∣=3|L|=3. In either case P∖{z}P\setminus\{z\} remains an ordinary plane. When ∣L∣≥4|L| \ge4 we have a contradiction to minimality and when ∣L∣=3|L| = 3, we end up with an ordinary plane and can apply Lemma 11.3.

Let ww be the image of ee in ZZ (recall that image was defined immediately before Lemma 10.1). Now consider the torso WW of (B,Q,Z)(B,Q,Z). Note that WW is a plane spanning ZZ and WW is round. Since WW is round, the set of points in WW outside the span of {x,y}\{x,y\} still span WW. Let II be a 3-element independent subset of WW outside the span of {x,y}\{x,y\}. Since (B,Q,Z)(B,Q,Z) is coupled, the elements of II lie on the two lines spanned by {x,z}\{x,z\} and {y,z}\{y,z\}. Up to symmetry, we may assume that two of the three elements in II lie on the line spanned by {x,z}\{x,z\}; one of these two, say uu, is not on the line spanned by {y,w}\{y,w\}. Now, {x,y,w}\{x,y,w\} is a triangle in Q//uQ//u. Thus (T∪{e})∖{z}(T \cup\{e\}) \setminus\{z\} is a circuit in Q//uQ//u. So we get the desired minor by taking a strand SS in (B,Q,Z)(B,Q,Z) with base point uu.

Connectivity in frameworks and patchworks

Let (M,Q,V)(M,Q,V) be a patchwork with skeleton GG and let XX and YY be subsets of V∩E(M)V \cap E(M). Our next goal is to show that the matroid connectivity κM(X,Y)\kappa_M(X,Y) is equal to the graph connectivity. Recall that our definition of κM(X,Y)\kappa_M(X,Y), in Section 5, allows XX and YY to intersect.

Lemma 12.1. Let (M,Q,V)(M,Q,V) be a framework with skeleton GG and let XX and YY be subsets of V∩E(M)V \cap E(M), then the connectivity from XX to YY in MM is equal to the connectivity from XX to YY in GG.

Proof. Let II be the edge set of kk disjoint paths from XX to YY in GG, and let X′X' be the ends in XX and Y′Y' be the ends in YY. Then X′X' and Y′Y' are point-wise equivalent independent sets in the planted matroid (M/I,Q//I)(M/I,Q//I), which implies that κM(X,Y)≥k\kappa_M(X,Y) \ge k. Conversely, if there is a separation (H1,H2)(H_1,H_2) of order kk in GG with X⊆V(H1)X \subseteq V(H_1) and Y⊆V(H2)Y \subseteq V(H_2), then no component in the projection M//V(H1∩H2)M//V(H_1 \cap H_2) contains both an element of XX and an element of YY, which implies that κM(X,Y)≤∣V(H1∩H2)∣=k\kappa_M(X,Y) \le|V(H_1 \cap H_2)| = k.

A separation in a rooted matroid (M,Q,V)(M,Q,V) is a pair ((M1,Q,V1),(M2,Q,V2))((M_1,Q,V_1),(M_2,Q,V_2)) of rooted matroids such that M=M1∪M2M = M_1 \cup M_2, V=V1∪V2V = V_1 \cup V_2, and each bridge of either (M1,Q,V1)(M_1,Q,V_1) or (M2,Q,V2)(M_2,Q,V_2) is also a bridge in (M,Q,V)(M,Q,V); the order of the separation is ∣V1∩V2∣|V_1 \cap V_2|. If (M,Q,V)(M,Q,V) is a patchwork with skeleton GG, and X,Y⊆VX,Y \subseteq V, then the connectivity from XX to YY in (M,Q,V)(M,Q,V) is the minimum order of a separation ((M1,Q,V1),(M2,Q,V2))((M_1,Q,V_1),(M_2,Q,V_2)) with X⊆V1X \subseteq V_1 and Y⊆V2Y \subseteq V_2. If GG is the skeleton of the patchwork (M,Q,V)(M,Q,V), then it is easy to see that the connectivity from XX to YY in GG is the same as the connectivity from XX to $Y i…

Lemma 12.2. Let (M,Q,V)(M,Q,V) be a patchwork and let XX and YY be subsets of V∩E(M)V \cap E(M), then the connectivity from XX to YY in the matroid MM is equal to the connectivity from XX to YY in the patchwork (M,Q,V)(M,Q,V).

Proof. Suppose that the connectivity from XX to YY in (M,Q,V)(M,Q,V) is kk, and let GG be the skeleton of (M,Q,V)(M,Q,V). Choose a set of kk disjoint paths having as few edges as possible and let II be the edge-set of those paths. By minimality, II contains at most one base point from each patch of (M,Q,V)(M,Q,V), therefore the subgraph G[V,I]G[V,I] is realizable, and hence, by Lemma 12.1, we have κM(X,Y)≥k\kappa_M(X,Y) \ge k. Conversely, there is a separation ((M1,Q,V1),(M2,Q,V2))((M_1,Q,V_1),(M_2,Q,V_2)) of order kk in (M,Q,V)(M,Q,V) with X⊆V1X \subseteq V_1 and Y⊆V2Y \subseteq V_2, and no non-loop component in the projection M//(V1∩V2)M//(V_1 \cap V_2) contains both an element of XX and an element of YY, which implies that κM(X,Y)≤∣V1∩V2∣=k\kappa_M(X,Y) \le|V_1 \cap V_2| = k.

It is implicit in the proofs of Lemmas 12.1 and 12.2 that the connectivity between XX and YY in a patchwork is obtained via paths in the skeleton, and that a path PP between distinct elements x∈Xx \in X and Y∈YY \in Y gives a circuit. This is made more precise in the following result, whose easy proof is omitted.

Lemma 12.3. Let (M,Q,V)(M,Q,V) be a patchwork and let XX and YY be subsets of V∩E(M)V \cap E(M). If the connectivity from XX to YY in MM is kk, then there is a restriction NN of MM such that X∪Y⊆E(N)X \cup Y \subseteq E(N), κN(X,Y)=k\kappa_N(X,Y) = k, and each component of NN is either a coloop or a circuit containing exactly one element of X∖YX \setminus Y and exactly one element of Y∖XY \setminus X.

In the rest of this section we consider a minimum order (X,Y)(X,Y)-separation in MM relative to the patchwork (M,Q,V)(M,Q,V). We show that we can “display” the separation in a patchwork but with a possibly different set VV. As a point of caution, the set VV can change in more wild ways than one might imagine upon first reading; for example, as with graphic matroids, one can create unpleasant examples via Whitney switching. With additional effort it is possible to describe the minimum order (X,Y)(X,Y)-separations in MM, without changing VV, but, fortunately, we do not need that.

Lemma 12.4. Let (M,Q,V)(M,Q,V) be a patchwork, let XX and YY be subsets of V∩E(M)V \cap E(M), and let (A,B)(A,B) be a minimum order (X,Y)(X,Y)-separation in MM. Then there exists V′⊆E(Q)V' \subseteq E(Q) and sets V1V_1 and V2V_2 such that

  1. (M,Q,V′)(M,Q,V') is a patchwork, and

  2. ((M∣A,Q,V1),(M∣B,Q,V2))((M|A,Q,V_1),(M|B,Q,V_2)) is a separation of order ⊓M(A,B)\sqcap_M(A,B) in (M,Q,V′)(M,Q,V') with X⊆V1X \subseteq V_1 and Y⊆V2Y \subseteq V_2.

Proof. Let Z=X∩YZ=X\cap Y and let k=⊓M(A,B)−∣Z∣k=\sqcap_{M}(A,B)-|Z|. By Lemma 12.3, there exist circuits C1,…,CkC_1,\ldots,C_k in M∖ZM\setminus Z such that r(C1∪⋯∪Ck∪Z)=r(C1)+⋯+r(Ck)+r(Z)r(C_1\cup\cdots\cup C_k\cup Z)=r(C_1)+\cdots+r(C_k)+r(Z) and each of the circuits C1,…,CkC_1,\ldots,C_k contains exactly one element from each of XX and YY. Now let FF be the rank-k+∣Z∣k+|Z| subspace of QQ that is spanned by both AA and BB. Note that no non-loop component of M//FM//F contains both an element of XX and an element of YY. Therefore, for each i∈{1,…,k}i\in\{1,\ldots,k\} there is a non-loop element vi∈Fv_i\in F that is spanned by CiC_i.

Since r(C1∪⋯∪Ck∪Z)=r(C1)+⋯+r(Ck)+r(Z)r(C_1\cup\cdots\cup C_k\cup Z)=r(C_1)+\cdots+r(C_k)+r(Z), the set {v1,…,vk}∪Z\{v_1,\ldots,v_k\}\cup Z is a basis of M∣FM|F and, hence, each of the circuits C1,…,CkC_1,\ldots,C_k spans exactly one element in FF. Therefore, for each i∈{1,…,k}i\in\{1,\ldots,k\}, the circuit CiC_i breaks into two circuits Ci∩AC_i\cap A and Ci∩BC_i\cap B in M//viM//v_i.

We will show that there exists a basis VBV_B of the the subspace spanned by BB such that (B,Q,VB)(B,Q,V_B) is a patchwork and, up to point-wise equivalence, VBV_B contains both {v1,…,vk}∪Z\{v_1,\ldots,v_k\}\cup Z and YY. By symmetry, this would also give a basis VAV_A of the the subspace spanned by AA such that (A,Q,VA)(A,Q,V_A) is a patchwork and, up to point-wise equivalence, VAV_A contains both {v1,…,vk}∪Z\{v_1,\ldots,v_k\}\cup Z and YY. Our result will then follow by taking a basis V′V' of VA∪VBV_A\cup V_B.

Consider the matroid MB:=B∪C1∪⋯∪CkM_B:=B\cup C_1\cup\cdots\cup C_k and the patchwork (MB,Q,V)(M_B,Q,V). Note that, for each i∈{1,…,k}i\in\{1,\ldots,k\}, the set Ci∖AC_i\setminus A is a series class in MBM_B having viv_i as its base point. Since VV is coupled in M∪VM\cup V, this series class contains exactly one element of VV and that element, say xix_i, is in XX. When we contract the other elements in the series class, xix_i lands in parallel with viv_i. By Lemma 9.3, we get a minor (B∪{x1,…,xk},Q′,VB′)(B\cup\{x_1,\ldots,x_k\},Q',V'_B) of the patchwork (B,Q,V)(B,Q,V) where VB′⊆VV'_B\subseteq V and, up to point-wise equivalence, VB′V'_B contains both {v1,…,vk}∪Z\{v_1,\ldots,v_k\}\cup Z and YY, as required. □

Extending a patchwork

Our first result of this section deals with extensions that belong in a patch.

Lemma 13.1. Let (M,Q,V)(M,Q,V) be a patchwork with skeleton GG, let X⊆VX\subseteq V, and let ee be an element of QQ in the span of M∪VM\cup V such that (M+e,Q,X)(M+e,Q,X) is coupled. If Z⊆VZ\subseteq V with κG(Z,X)=∣Z∣≤3\kappa_G(Z,X)=|Z|\le3, and the connectivity from Z∪{e}Z\cup\{e\} to XX in M∪Z∪X∪{e}M\cup Z\cup X\cup\{e\} is ∣Z∣|Z|, then there is a set V′V' in QQ, containing XX, such that (M+e,Q,V′)(M+e,Q,V') is a patchwork.

Proof. Let k=∣Z∣k=|Z|. Consider a (Z∪{e},X)(Z\cup\{e\},X)-separation (A′,B′)(A',B') of order kk in M∪Z∪X∪{e}M\cup Z\cup X\cup\{e\}. Note that (A′∖{e},B′)(A'\setminus\{e\},B') is a minimum order (Z,X)(Z,X)-separation in M∪Z∪XM\cup Z\cup X with ∣A′∣|A'| maximum. This uniquely determines A′A' and thus ee is in the span of A′A'. By Lemma 12.4 and possibly changing the set VV, we may assume that there is a separation ((A,Q,V1),(B,Q,V2))((A,Q,V_1),(B,Q,V_2)) of order kk in (M,Q,V)(M,Q,V) such that Q∣A′Q|A' is a restriction of A∪V1A \cup V_1 and Q∣B′Q|B' is a restriction of B∪V2B \cup V_2. Since k≤3k \le3, (M,Q,V2)(M,Q,V_2) is a patchwork. Furthermore, since ee is spanned by A∪V1A \cup V_1, each bridge of (M+e,Q,V2)(M+e,Q,V_2) has at most three attachments. To complete the proof it remains to show that each bridge (B,Q,W)(B,Q,W) of (M+e,Q,V2)(M+e,Q,V_2) is coupled, moreover it suffices to check the bridge containing ee which holds since, by construction, the connectivity from WW to XX in the skeleton is k=∣W∣k=|W|, so we can take a minor of (B,Q,V2)(B,Q,V_2) such that WW is point-wise equivalent to a subset of XX.

Roughly the next result says that, if we “block” a patch when extending a patchwork, and the extension remains coupled, then we can grow the vertex-set of our patchwork such that ee looks like an edge from the point of view of the patch.

Lemma 13.2. Let (M,Q,V)(M,Q,V) be a patchwork with skeleton GG, let X⊆VX \subseteq V, and let ee be an element of QQ in the span of M∪VM \cup V such that (M+e,Q,X)(M+e,Q,X) is coupled. Now, for k∈{2,3}k \in\{2,3\}, let (P,Q,Z)(P,Q,Z) be a patch, with κG(Z,X)=∣Z∣=k\kappa_G(Z,X)=|Z|=k, such that ee is not in the span of (E(M)∪V)∖E(P)(E(M)\cup V)\setminus E(P) and κM∪Z(P∪Z∪{e},X)=k+1\kappa_{M\cup Z}(P\cup Z\cup\{e\},X)=k+1. Then there exists vv in the span of P∪ZP\cup Z and ww in the span of (E(M)∪V)∖E(P)(E(M)\cup V)\setminus E(P) such that ee is on the line spanned by vv and ww in QQ and such that (P,Q,Z∪{v})(P,Q,Z\cup\{v\}) is coupled.

Proof. By Tutte’s linking theorem, there is a minor (P∪Z∪{e},Q′,X)(P\cup Z\cup\{e\},Q',X) of (M∪Z∪{e},Q,V)(M\cup Z\cup\{e\},Q,V) such that the local connectivity between P∪Z∪{e}P\cup Z\cup\{e\} and XX is k+1k+1 and the local connectivity between ZZ and XX is kk in Q′Q'. Since ZZ and XX are both contained in VV and VV is coupled in (M,Q,V)(M,Q,V), the set ZZ is point-wise equivalent with some subset X′X' of XX in Q′Q'. Let DD be a basis of P∪XP\cup X that contains XX. There is an element vv in Q′Q', in the span of P∪ZP\cup Z such that (D∖X′)∪{v}(D\setminus X')\cup\{v\} spans {e}\{e\}; moreover this point is unique, up to equivalence. Note that the span of P∪ZP\cup Z in Q′Q' contains the span of P∪ZP\cup Z in QQ, so we may assume that the element vv is in the span of P∪ZP\cup Z in QQ.

Now, up to equivalence, there is a unique point ww in Q′Q' that is spanned by X∖X′X\setminus X' such that ee is on the line spanned by vv and ww in Q′Q'. Note that Q′Q' contains the line spanned by vv and ee in QQ so we can choose ww on that line. Since Q′Q' is obtained from QQ by projecting out elements in E(M)∖E(P)E(M)\setminus E(P), the point ww is spanned by (E(M)∪Z)∖E(P)(E(M)\cup Z)\setminus E(P) in QQ. Since P∪ZP\cup Z is connected, we can contract vv into the span of X′X'. However, (P∪{e},Q′,X)(P\cup\{e\},Q',X) is coupled, so w′w' must be point-wise equivalent with an element of X∖X′X\setminus X' and, however, we contract vv into the span of X′X' it must land in parallel with an element of X′X'. Thus (P,Q′,Z∪{v})(P,Q',Z \cup\{v\}) is coupled, and hence, so is (P,Q,Z∪{v})(P,Q,Z \cup\{v\}). □\square

Resilient patchworks

In the proof of the main theorem, it is convenient to work with a patchwork (M,Q,V)(M,Q,V) such that

  1. for each patch (P,Q,Z)(P,Q,Z) with ∣Z∣=3|Z| = 3, the matroid P∪ZP \cup Z is vertically 3-connected, and

  2. the skeleton of (M,Q,V)(M,Q,V) is 3-connected.

We say that the patchwork is resilient if it satisfies these two properties.

Lemma 14.1. Let (P,Q,Z)(P,Q,Z) be a 3-patch in a patchwork (M,Q,V)(M,Q,V). If M∪VM \cup V is vertically 3-connected, but P∪ZP \cup Z is not vertically 3-connected, then there is an element vv in QQ that is spanned by P∪ZP \cup Z, but not by VV, such that (M,Q,V∪{v})(M,Q,V \cup\{v\}) is a patchwork.

Proof. Consider a vertical separation (A,B)(A,B) of order 1 in P∪ZP \cup Z. Since M∪VM \cup V is vertically 3-connected, there is an element z1∈E(A)∩Zz_1 \in E(A) \cap Z that is not spanned by BB and an element z2∈E(B)∩Zz_2 \in E(B) \cap Z that is not spanned by AA. Let vv be a non-loop element in QQ that is spanned by both AA and BB. Since (P,Q,Z)(P,Q,Z) is a patch, P/ZP/Z is connected, and hence vv is not spanned by ZZ. It is now easy to see that (M,Q,V∪{v})(M,Q,V \cup\{v\}) is a patchwork, as required. □\square

Therefore, if we are given a patchwork (M,Q,V′)(M,Q,V') such that M∪V′M \cup V' is vertically 3-connected, we can obtain (1) by adding vertices. If the skeleton of the resulting patchwork (M,Q,V)(M,Q,V) is not 3-connected, then we will get a separation ((A,Q,V1),(B,Q,V2))((A,Q,V_1),(B,Q,V_2)) of order at most 2 in (M,Q,V)(M,Q,V) with V1∖V2V_1 \setminus V_2 and V2∖V1V_2 \setminus V_1 both non-empty. Note that, (A,Q,V1)(A,Q,V_1) and (B,Q,V2)(B,Q,V_2) are both patchworks, and, moreover, if (M,Q,V)(M,Q,V) satisfies (1) then so do both (A,Q,V1)(A,Q,V_1) and (B,Q,V2)(B,Q,V_2).

We have proved the following result.

Lemma 14.2. Let (M,Q,X)(M,Q,X) be a rooted matroid such that M∪XM \cup X is vertically 3-connected and each pair of distinct elements in XX span a long-line in M∪XM \cup X. If there is a patchwork whose vertex-set contains XX, then there is a resilient patchwork whose vertex-set contains XX.

The main theorem

Our main result is:

Theorem 15.1. If (M,Q,X)(M,Q,X) is a coupled matroid, then there is a patchwork (M,Q,V)(M,Q,V) with X⊆VX \subseteq V.

Proof. We consider a counterexample (M,Q,X)(M,Q,X) such that r(M)−r(X)r(M)-r(X) is minimum, and, subject to that, the number of elements of MM that are not spanned by XX is minimum. We may further assume that: M∪VM \cup V is simple, X∩E(M)X \cap E(M) is empty, and each pair of distinct elements in XX span a long line in M∪XM \cup X. Note that ∣X∣≥4|X| \ge4, since otherwise (M,Q,X)(M,Q,X) is, itself, a patchwork. By Lemma 8.2, M∪XM \cup X is vertically 4-connected.

Let ee be an element of MM that is not in the span of XX. By minimality, there is an independent set VV in QQ, containing XX, such that (M∖e,Q,V)(M\setminus e,Q,V) is a patchwork. We choose VV such that (M∖e,Q,V)(M\setminus e,Q,V) is resilient (see Lemma 14.2) and, subject to that, with ∣V∣|V| is as large as possible. We extend VV to a basis II of (M∖e)∪V(M\setminus e) \cup V and let WW be a minimal subset of II that spans ee.

By Lemma 13.1, we have

15.1.1. For any set Z⊆VZ \subseteq V with ∣Z∣≤3|Z| \le3, the connectivity from Z∪{e}Z \cup\{e\} to XX in M∪Z∪X∪{e}M \cup Z \cup X \cup\{e\} is ∣Z∣+1|Z|+1.

We will call a patch (B,Q,Z)(B,Q,Z) of (M∖e,Q,V)(M\setminus e,Q,V) blocked if E(B)∩WE(B) \cap W is non-empty.

Our first non-trivial claim is:

15.1.2. If (B,Q,Z)(B,Q,Z) is a blocked patch of (M∖e,Q,V)(M\setminus e,Q,V), then ∣Z∣=2|Z|=2 and there exists an element vv in QQ that is spanned by B∪ZB \cup Z such that (M,Q,V∪{v})(M,Q,V \cup\{v\}) is a patchwork and such that ee is spanned by (W∖E(B))∪{v}(W \setminus E(B)) \cup\{v\}.

Proof of claim. By Lemma 13.1, we may assume that the connectivity from Z∪{e}Z \cup\{e\} to XX in M∪Z∪X∪{e}M \cup Z \cup X \cup\{e\} is ∣Z∣+1|Z|+1. Then, by Lemma 13.2, for each patch (B,Q,Z)(B,Q,Z) of (M∖e,Q,V)(M\setminus e,Q,V) there is an element v∈E(Q)v \in E(Q) that is spanned by B∪{Z}B \cup\{Z\} such that (B,Q,Z∪{v})(B,Q,Z \cup\{v\}) is coupled and ee is spanned by (W∖E(B))∪{v}(W \setminus E(B)) \cup\{v\}. If ∣Z∣=2|Z|=2, then (M∖e,Q,V∪{v})(M\setminus e,Q,V \cup\{v\}) is a patchwork, as required. Therefore, we may assume that ∣Z∣=3|Z|=3.

Let B+B^{+} be obtained from BB by adding elements so that the lines spanned by any two elements in Z∪{v}Z \cup\{v\} in B∪Z∪{v}B \cup Z \cup\{v\} are long. By minimality, there is a patchwork (B,Q,V′)(B,Q,V^{\prime}) with Z∪{v}⊆V′Z \cup\{v\} \subseteq V^{\prime} and we can choose V′V^{\prime} such that (B,Q,V′)(B,Q,V^{\prime}) is resilient. Now (M∪B′,Q,V∪V′)(M \cup B^{\prime},Q,V \cup V^{\prime}) is a resilient patchwork, but, by our choice of VV, the patchwork (M,Q,V∪V′)(M,Q,V \cup V^{\prime}) is not resilient. Now (M∪B′,Q,V∪V′)(M \cup B^{\prime},Q,V \cup V^{\prime}) and (M,Q,V∪V′)(M,Q,V \cup V^{\prime}) have the same non-trivial patches, so the issue is that the skeleton HH of (M,Q,V∪V′)(M,Q,V \cup V^{\prime}) is not 3-connected. However, since (M,Q,V)(M,Q,V) is resilient, B∪ZB \cup Z is vertically 3-connected, so the skeleton of (B,Q,V′)(B,Q,V^{\prime}) is 2-connected. Moreover, there are three disjoint paths from ZZ to XX in HH. So there are three internally-disjoint paths connecting any two vertices of ZZ in HH. Consider a separation (H1,H2)(H_1,H_2) of order 2 in HH with X⊆V(H1)X \subseteq V(H_1) and V(H2)∖V(H1)≠∅V(H_2) \setminus V(H_1) \ne\varnothing, and, subject to that take ∣V(H2)∣|V(H_2)| maximum. Note that Z⊆V(H1)Z \subseteq V(H_1) and v∈V(H2)∖V(H1)v \in V(H_2) \setminus V(H_1). Moreover V(H2)V(H_2) is the closure of the neighbour set of vv in HH in the matroid K(H,X)K(H,X). Now (M,Q,V(H1))(M,Q,V(H_1)) is a resilient patchwork with V⊆V′V \subseteq V', however, V≠V′V \ne V' since vv is in the span of a 3-patch (B,Q,Z)(B,Q,Z) in (M,Q,B)(M,Q,B), whereas in (M,Q,V(H1))(M,Q,V(H_1)) we can disconnect vv from XX by projecting out only two vertices, namely, V(H1∩H2)V(H_1 \cap H_2).

Applying Claim 15.1.2 to each blocked patch of (M∖e,Q,V)(M\setminus e,Q,V) we obtain a set V+V^+ such that

  • (a) (M∖e,Q,V+)(M\setminus e,Q,V^+) is a patchwork with V⊆V+V \subseteq V^+,

  • (b) V+V^+ spans ee,

  • (c) for each blocked patch (B,Q,Z)(B,Q,Z) of (M∖e,Q,V)(M\setminus e,Q,V), there is exactly one element of V+∖VV^+ \setminus V that is spanned by B∪ZB \cup Z, and

  • (d) for each v∈V+∖Vv \in V^+ \setminus V, there is a blocked patch (B,Q,Z)(B,Q,Z) of (M∖e,Q,V)(M\setminus e,Q,V) such that vv is spanned by B∪ZB \cup Z.

Since M∪XM \cup X is vertically 4-connected, each nontrivial patch (B,Q,Z)(B,Q,Z) of (M∖e,Q,V+)(M\setminus e,Q,V^+) has three attachments and BB spans ZZ. Let G+G^+ denote the skeleton of (M∖e,Q,V+)(M\setminus e,Q,V^+) and let TT be the attachment set of ee. Note that

  • (i) each vertex v∈V+∖Vv \in V^+ \setminus V is contained in TT and has exactly two neighbours in G+G^+,

  • (ii) any two distinct vertices in VV are adjacent in GG if and only if they are either adjacent in HH or they have a common neighbour in V+∖VV^+ \setminus V in HH.

This implies that si⁡(G+)\operatorname{si}(G^+) is a subdivision of a 3-connected graph. Now it follows from Lemma 11.4, that κG+(T,X)≤3\kappa_{G^+}(T,X) \le3. But then we get a contradiction by applying Lemma 13.1.

Statement of AI use

Microsoft Copilot was used to proofread the final draft and to complete the bibliographic citations.

Acknowledgements

The matroid minors papers are long overdue, and we are deeply grateful to Neil Robertson for giving us a gentle prod to resume writing. That prod was accompanied by a very generous personal financial donation from Neil to the University of Waterloo to assist with the writing.

References

  1. [1]K. Chakravarti and N. Robertson, Covering three edges with a bond in a non-separable graph, Annals of Discrete Math. 8 (1980), 247.
  2. [2]T. Gallai, Solution to Problem 4065. Amer. Math. Monthly 51 (1944), 169–171.
  3. [3]E. Melchior, Über vielseitige der projektiven ebene, Deutsche Mathematik, 5(1) (1941), 461–475.
  4. [4]T.S. Motzkin, The lines and planes connecting the points of a finite set, Trans. Am. Math. Soc. 70 (1951), 451–464.DOI
  5. [5]J.G. Oxley, Matroid Theory, Second edition, Oxford University Press, New York, 2011.
  6. [6]N. Robertson and P.D. Seymour, Graph Minors. XIII. The Disjoint Paths Problem, Journal of Combinatorial Theory, Series B 63 (1995), 65–110.DOI
  7. [7]N. Robertson and P.D. Seymour, Graph Minors. XVI. Excluding a Non-Planar Graph, Journal of Combinatorial Theory, Series B 89 (2003), 43–76.DOI
  8. [8]P.D. Seymour, Disjoint Paths in Graphs, Discrete Mathematics 29 (1980), 293–309.
  9. [9]P.D. Seymour, Triples in Matroid Circuits, European Journal of Combinatorics 7 (1986), 177–185.DOI
  10. [11]P.D. Seymour, Recognizing Graphic Matroids, Combinatorica 1 (1981), 75–78.DOI
  11. [12]J.J. Sylvester, Mathematical Question 11851. Educational Times 59 (1893) 98.
  12. [13]C. Thomassen, 2-Linked Graphs, European Journal of Combinatorics 1 (1980), 371–378.DOI
  13. [14]W.T. Tutte, Lectures on Matroids, Journal of Research of the National Bureau of Standards, Section B 69B (1965), 1–47.DOI
  14. [15]T. Zaslavsky, Biased Graphs. II. The Three Matroids, Journal of Combinatorial Theory, Series B 51 (1991), 46–72.DOI

Paper details

vlnc:W_9bfrxds7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents