WorksMathematics
Triples in matroid circuits
Abstract
We prove that, if is a four-element independent set in a vertically -connected representable matroid , then either there is a circuit of that contains at least three elements of , or there is a representation of such that each column of has at most two non-zero elements and each of the columns indexed by 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 is represented by a frame matrix and is the set of elements in that index unit columns, then no circuit in can contain three or more elements in . We prove the following partial converse. Here two matrices are row-equivalent if they have the same row-space.
Theorem 1.1. Let be a vertically 5-connected matroid represented by a matrix . If is an independent set, with , then either there is a circuit of that contains at least three elements of , or is row-equivalent to a frame matrix and each element of indexes a unit column of .
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 is an independent set, with , 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 and there is no circuit containing three or more elements of , then 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 of elements in a matroid coupled if there is no circuit in that contains three of more elements of . Note that is coupled if and only if there is no -minor of with . Therefore, if is coupled in then it is also coupled in any minor of that contains .
Given three distinct elements , , and in a matroid , the three-elements problem is the problem of determining whether or not 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 is a coupled set in a vertically 4-connected, binary matroid , then is the cycle-matroid of a graph and , , and are incident with a common vertex in .
Note that if is the vertex of that is incident with , , and and is the matrix obtained from a signed incidence matrix of representing by deleting the row indexed by , then is a frame matrix and each of , , and indexes a unit column of .
Theorem 2.1 provides an efficient algorithm for solving the three-elements problem in a binary matroid . Note that, adding points to the lines spanned by , , and does not affect whether or not is coupled; therefore we may assume that has an -restriction containing , , and . In the case that is vertically 4-connected, we can test whether or not is coupled by simply testing whether is graphic. Indeed, if is graphic, then the minor will force , , and to be incident with a common vertex. In the case that is not vertically 4-connected, there is a vertical 3-separation with . Now we can construct a binary extension of by adding (all possible) points spanned by both and , then deleting . It is routine to show that this does not affect whether or not 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 by coextending by a new element so that is a cocircuit in . In binary matroids any circuit meets any cocircuit in an even number of elements. Therefore, is coupled in if and only if is coupled in . It still requires some additional work to obtain Theorem 2.1, but the key observation is that, since is a cocircuit, the decomposition given by Theorem 15.1 will not involve 4-sums.
Intractability for general matroids. If is a triangle in a 3-connected non-binary matroid, then there is a -minor containing ; see Theorem 6.3. Note that will be a cocircuit in such a minor. Dually this gives the following result.
Theorem 2.2. If is a triad in a 3-connected matroid , then is coupled in if and only if 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 , we take to be a rank- “binary spike with tip and co-tip”. Specifically, is a binary matroid with ground-set where is a basis, each of is a triangle, and each of is a triad. It is easy to check that, has at least circuit-hyperplanes and that relaxing any one of these circuit-hyperplanes will result in a non-binary matroid. Now is not contained in a circuit in , but it is in each of the relaxations. Therefore we cannot safely conclude that 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 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 represented by the following matrix over any field with characteristic different from 2,
Note that
(a) is isomorphic to ,
(b) is a cocircuit in and every pair of elements in spans an element in ,
(c) every element in is spanned by two elements in , and
(d) is the dual of the non-Fano.
Using (c), the set is coupled in and, by (b), it remains coupled in . Moreover, is vertically 5-connected, since is spanned by . We leave it to the reader to check that 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 that does not extend to a frame representation of , so we can take a 4-sum of a frame representation and such that the resulting matroid is not a frame representation. More generally, we can do the same thing for , when . There are other constructions, but a complete characterization, in the representable case, still looks achievable.
The two-linkage problem. Given distinct vertices , , , in a graph , the two-linkage problem is the problem of deciding whether or not there exist two disjoint paths, one connecting to and the other connecting to . This is in fact a special case of the three-elements problem for binary matroids. We may add edges , , and 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 , , and are contained in a circuit in . 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 , , , be disjoint vertices in a 4-connected graph . If there do not exist two disjoint paths one connecting to
and the other connecting to , then admits a planar embedding with , , , 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 , given a -grid-minor in a graph with no -minor, there is a subgraph of such that embeds in the plane “up to 3-separations”, includes a -sub-grid of our grid minor, and there is a set of at most vertices such that no vertex of outside and is connected to any vertex of 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 on a set is a gammoid if there is a directed graph , with , and a set such that the rank of each is equal to the maximum number of disjoint directed paths from to in . 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 and of a graph , we can define and , naturally, by taking intersections or unions of both the vertex sets and edge sets. A separation in a graph is a pair of subgraphs of such that ; the order of the separation is . We call a separation proper if and are both non-empty. For sets and of vertices, an -separation is a separation with and . We define to be the minimum order of an -separation. Note that we do not require and to be disjoint.
Let be a set of vertices in a graph . As discussed above, there is a gammoid on such that the rank of a set is .
Tight sets. Let be an edge in a graph . We write to denote the graph obtained from by contracting to a vertex . Let and be sets of vertices in a graph . We say that is -tight, if, for each vertex , the connectivity from to is . In terms of the connectivity matroid, , this says that is both independent set and a flat. In particular, an -tight triple is a three-point plane in .
The notion of -tightness is very useful in matroid minors. For example, one can show that, if is a graft and is an -tight subset of , then we can contract all of down to keeping the -set of size at least . 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 . There is a companion result, below, for removing edges incident with .
Lemma 4.1. Let and be sets of vertices in a graph , let be an edge of with . If is -tight in , then is -tight in at least one of or .
Proof. Let . If is not -tight in , then there is a -separation of order in such that . If is not -tight in , then there is a -separation of order in such that and . Note that
are both -separations in and, by submodularity, the sum of the orders of these separations is at most . Since ,
are both -separations in and the sum of the orders of these separations is at most . However, since is a vertex in both and , this contradicts the fact that is -tight in . □
Next we show we can reduce the degree of each vertex in to two.
Lemma 4.2. Let and be sets of vertices in a graph , and let . If is -tight and has degree at least 3, then there is an edge incident with such that is -tight in .
Proof. Let . Consider constructing a new graph by adding a twin of to . Since is -tight in , there exist disjoint -paths in . Therefore there are -paths such that are disjoint and . Suppose that is an edge incident with that is in neither nor . We claim that is -tight in . Suppose otherwise and consider an -separation of order in with . Since is -tight in , neither nor can contain both ends of . Thus and . This is not possible, since the paths must each intersect 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 and in a matroid is defined as
The Tutte connectivity of a set is
A separation is a pair of sets in such that ; the order of the separation is . For two sets and in a matroid , an -separation is a separation with and . The connectivity between two sets and , denoted by , is defined as the minimum order of an -separation in . Note that this differs from the definition on Oxley [5 page 320] since we do not require that and are disjoint. Our definition is tantamount to making and 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 is a separation of such that neither nor is spanning. We say that is vertically -connected if it has no vertical separation of order less than .
Note that, Oxley’s “-separations” are separations of order at most here. Nevertheless, our usage of “-connected” and “vertically -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 is an element in a connected matroid , then or is connected.
Theorem 5.2 (Tutte’s linking theorem; see Oxley [5 Theorem 8.5.2]). If and are disjoint sets of elements in a matroid and , then
Strands. Let be a restriction of a matroid . We call a set a strand for if and each pair of elements in is in series in . 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 is a restriction of a matroid and is such that the component of that contains also contains at least one element of , then there is a strand for in that contains .
Proof. Suppose otherwise, and consider a counterexample with minimum. Let be a circuit of that contains and at least one element of . We may assume that is not spanned by , since otherwise is already a strand. Thus there is some element, say that is not spanned by . By minimality, there is a strand for in that contains . But then, either or is a strand for in . □
Modular flats
A pair of subsets of is modular if . A set of elements is modular if is a modular pair for each flat of . 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 is a modular flat and , then is modular in both and . Moreover, if , then is also modular in , but deleting elements of need not preserve modularity. The following result is well-known.
Lemma 6.1. For a set of elements in a matroid , the following are equivalent:
(1) is a modular set in ,
(2) for each minor of containing as a spanning restriction, each element of is either a loop or is in parallel with an element of .
(3) each strand of in spans a non-loop element of .
Proof. If (1) fails, then there is a flat of such that is not a modular pair. Let be a maximal independent set of and let . Note that is contained in the closure of in and so there is an element that is not in parallel with any element of , so (2) fails.
If (2) fails, there is a maximal independent set of and an element , such that, in , is not a loop and is not in parallel with any element of . Let . Then $\Pi_M(F,Y) = 1 and yet does not span a non-loop element of . Since , there is a circuit of that contains an element of and an element of . By Lemma 5.3, contains a strand for and, hence, (3) fails.
If (3) fails and is a strand of in that does not span any non-loop element of , then 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 be a modular set of elements in a matroid and let be a component of . If is the set of elements in that are spanned by in , then is round.
Proof. Suppose that the result fails, and consider a counterexample with minimum. By minimality, we have , , and is simple and connected. Since is a counterexample, there exist hyperplanes and of such that . Note that and are disjoint since otherwise we could contract the intersection. Consider an element in . By minimality is not connected, so, by Theorem 5.1, is connected. Again applying minimality, cannot span an element in both and , so, up to symmetry, . But then and hence . Since and are both hyperplanes of , we also have . Since is connected there is a circuit that contains both elements of . Now is a strand for , but spans no element of , contrary to the fact that 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 is 2-rounded; see Oxley [5 Proposition 12.3.8].
Theorem 6.3. If a triangle in a 3-connected matroid is modular, then is binary.
Proof. Let . If is not binary, has a -minor. Then, by the 2-roundedness of , there is a -minor that contains . We may assume that also contains ; to see this consider what happens when is the last element removed when constructing . But then, by Lemma 6.1, is not modular in .
Here is an even more striking example, which is just Seymour’s Theorem 2.1 in disguise.
Theorem 6.4. Let be a restriction of a vertically 4-connected matroid . If is modular in , then is graphic.
Proof. Each triangle in is modular in , so, by Theorem 6.3, is binary. Now we obtain the result by applying Theorem 2.1 to a triad of . □
Modular sums. The following result is easy and well-known; we omit the proof. Here, we are primarily interested in the case that .
Lemma 6.5. Let be a matroid and let be a modular pair of flats in a matroid with . If , then is a minor of if and only if is a minor of .
The matroid is a generalized parallel connection (or modular sum) of and ; see Oxley [5 Section 11.4]. The lemma shows that we can use modular sums to build up matroids that avoid as minor. We assume that is connected, since otherwise we could construct via a series of modular sums, treating the components one at a time.
Note that, by Lemma 6.2, the matroid is round. The cycle matroid of a graph is round if and only if 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 we can extend by a non-loop element in the span of both and . 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 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 where is a modular space and is a finite restriction of . To avoid ambiguity, we will call the flats of subspaces and the closure in of a set of elements will be called the span of , whereas within we will use the more familiar terms flat and closure. We say that two finite sets and in are point-wise equivalent if there is a bijection such that for each either , or is a parallel pair, or and are both loops.
If and are planted matroids on a common ambient space then we can define the intersection and union of and naturally as
For a planted matroid and we denote by and when we simply write .
Minors behave nicely for planted matroids. For , the deletion of is and the contraction of is . Sometimes we will contract an element , but we do not consider this a minor. We denote by , and we call this a projection. For an element , we define the projection, , to be the matroid obtained from by adding 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 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 be a planted matroid. For a matroid with we want to determine whether has as a minor. Further suppose that we have a separation of order in with . In this section we discuss the issues that arise in decomposing across the separation . For notational reasons it is convenient to assume that and are disjoint. If this is not the case, we will replace the elements of that are also in with parallel copies, and leave unchanged. Let and .
Let be the rank- subspace of containing the points in the span of both and and let be a minimal spanning subset of such that is modular in . By Lemma 6.1, each strand of in spans exactly one element in and, by minimality, each element in is spanned by some strand of in . Thus is finite and uniquely determined up to point-wise equivalence. We call the matroid a torso of in . Moreover, since it is uniquely determined up to point-wise equivalence we may also call it the torso of in .
Suppose that is the torso of in and consider decomposing into and . Note that is a modular sum of and . It follows from Lemma 6.5 that, if does not contain as a minor, then neither does . The converse is, however, not as clear-cut.
As noted above, each element in the torso is in the span of some strand for . We say that is a base-point for the strand . In , the set is a series-class and when we contract all but one element, say , the pair will be parallel. Thus an element in the torso of is any point in the span of onto which we can contract elements of , without reducing the rank of .
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 of the torso is realizable if there are disjoint sets and in such that , and is point-wise equivalent with in .
Due to the issues raised by realizability, it is possible that contains as a minor whereas does not. Nevertheless, we can decompose across separations of order at most .
Lemma 8.1. Let be the torso of a separation of order at most in a planted matroid and let be a matroid with . Then is a minor of if and only if is a minor of .
Proof. Let . For the non-trivial direction, suppose that is a minor of and let be a partition of such that is a minor of . We need to prove that is a minor of . Since singletons are realizable, we may assume that contains at least two elements in . But then spans and, hence, . So is a minor of , as required. □
We are, of course, interested in the case that , for which we can immediately draw the following conclusion.
Lemma 8.2. Let be the torso of a separation of order at most 2 in a planted matroid and let . Then is coupled in if and only if is coupled in .
Rooted matroids
A rooted matroid is a triple such that is a planted matroid, and is an independent set in ; we refer to as the vertex-set of the rooted matroid. Note that the vertices need not be contained in . We say that a rooted matroid is coupled if is coupled in . To avoid ugly terminology, we will abbreviate “coupled rooted matroid” to coupled matroid.
We say that a rooted matroid is a minor of a rooted matroid if is a minor of and .
Bridges. A bridge of is a rooted matroid such that is the ground-set of a component of and is a minimal subset of such that . Since is independent, the set is uniquely determined; is the set of elements in such that is a component of . We call the set of attachments of the bridge. We say that a bridge is trivial if it is spanned by ; if is a trivial bridge, then .
Torsos of rooted matroids. The torso of a rooted matroid is the torso of the separation in . If is the torso of then we call the rooted torso of . The following lemma is an immediate consequence of Lemma 6.2.
Lemma 9.1. If is the torso of a bridge of a rooted matroid , then is round.
We view a rooted matroid as way of building via modular sums. Let be the bridges of and let be the torso. Now let be the torsos of the bridges . To avoid ambiguities caused by point-wise equivalence, we take as restrictions of . Now the rooted matroid is obtained from by attaching the “extended bridges” using modular sums; finally, we obtain as a restriction of .
Frameworks and patchworks. A framework is a rooted matroid such that each element of is spanned by a set of at most two elements of . Equivalently, is a framework if and only if spans in and is coupled. More generally, a rooted matroid is coupled if and only if the rooted torso of is a framework. Frameworks are maintained under taking minors.
Lemma 9.2. If is a framework, and are disjoint sets in , and is a maximal independent subset of in , then is a framework.
Proof. Inductively it suffices to consider the case that , which we leave to the reader. □
We say that a bridge of a rooted matroid is a patch or a -patch if and the rooted torso of is a framework. A rooted matroid is a patchwork if each of its bridges is a patch. Patchworks are also maintained under taking minors.
Lemma 9.3. If is a patchwork, and are disjoint sets in , and is a maximal independent subset of in , then is a patchwork.
Proof. Again it suffices to consider the case that , which we leave to the reader. □
Our main result, Theorem 15.1, says that: if a rooted matroid is coupled, then there is an independent set in containing such that is a patchwork.
Extending a framework
The results in this section prove our main theorem (Theorem 15.1) in the special case that is a one-element extension of a framework. For a rooted matroid and an element in that is spanned by , the attachment-set of is the minimal subset of that spans ; since is independent, this is well-defined.
Skeletons. Let be a framework. The skeleton of a framework is the graph defined as follows: is the set of non-loop elements of and the set of ends of an edge is the attachment-set of in the framework. It is common practice to add the loops of as loop edges of at arbitrary vertices, but we choose to omit them.
Let be the skeleton of . A cycle of is called balanced if is a cycle of . Let denote the set of all balanced cycles of . The pair is a biased graph and is the frame matroid determined by ; see Zaslavsky [15]. We assume that the reader is familiar with these notions, but we will review some of the highlights.
Let be a subgraph of and let . We say that is balanced if each cycle of is balanced. If is balanced then is graphic, but the converse need not hold. The rank of in is , where is the number of balanced components of .
We note that any element of that is contained in will be both a vertex of and a loop at that vertex. This causes some ambiguity when we write , but the meaning will be clear from the context.
As we have already seen, frameworks are preserved under taking minors. For any element of , the deletion is a framework with skeleton . When is an edge with distinct ends and in , in the contraction the elements and will be parallel. So will be a framework whose skeleton is obtained from by deleting any loops of . Finally consider the case that is a non-balanced loop at a vertex . Then is a framework; the skeleton is obtained from by first deleting any loops of , then we remove the vertex from the vertex-set and from the end-set of any edge. (So the non-loop edges that are incident with in become loop edges in .)
For a framework , let be the attachment set of an element that is spanned by . For any non-empty subset of with , we have , so, up to point-wise equivalence, there is a non-loop unique element that is spanned by both and . Note that, and are parallel in . We call the image of on . If , then and will be point-wise equivalent, otherwise, when , the set is a circuit.
Now, consider effect, on the attachment set, of contracting an edge of the skeleton of ; here we are allowing . Let be the attachment set of in . If , then . Consider the alternative case that . If does not contain both and , then remains a circuit in and hence . This leaves the more interesting case that , which depends on the location of the image of on the line . If is point-wise equivalent with , then is a circuit in , so . Otherwise, when is independent, remains a circuit in and become a parallel pair. Thus .
Our first result uses the definition of “-tight” from Section 4.
Lemma 10.1. Let be the skeleton of a framework , let be the attachment set of an element that is spanned by , and let . If is connected, and there is a set of vertices in that is -tight, then there is a circuit in that contains or more elements of .
Proof. Consider a counterexample with minimum; thus no two vertices in are adjacent. Let be a complete graph on . It is easy to see that cannot have a cut-edge, since such an element could be contracted. Then, by Lemma 4.1, every edge of is incident with . Moreover, since is -tight, we have . Furthermore, by minimality, no two vertices of are adjacent in . Finally, by Lemma 4.2, each vertex in has degree 2. We may assume that is not contained in since otherwise the result clearly holds. Moreover, since is -tight, there is no circuit in . Let be a degree-1 vertex of , let be its neighbour, and let be the other neighbour of . Let and be the edges with ends and respectively.
Note that is -tight in . If , then we obtain a contradiction by contracting . On the other hand, when , then we obtain a contradiction by contracting . □
The following result connects tightness with our earlier Sylvester-Gallai-type results. We recall that is the matroid on such that the rank of a set is the connectivity from to .
Lemma 10.2. Let be the skeleton of a framework , let be the attachment set of an element that is spanned by , and let . If is 2-connected and has a three-point plane, then there is a circuit in that contains three or more elements of .
Proof. Since is 2-connected, is simple. Let be a three-point plane in . Now let be a -separation in of order 3 such that is the flat of that is spanned by . Note that is -tight in and, since is a three-point
plane in , we have . Therefore, we can contract onto 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 be the skeleton of a framework , let be the attachment set of an element that is spanned by , and let . If is 3-connected and , then there is a circuit in that contains three or more elements of .
Proof. Since is 3-connected and , the gammoid has no triangles and has rank at least 4. Since , the restriction has rank at least 4. Then, by Motzkin’s Lemma, 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 extends to a patchwork. We prove the theorem via induction, resulting in the case that, for some element in , there is a patchwork such that is spanned by . At that point, it is easy to imagine 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 of a coupled matroid is a framework. We refer to the skeleton of as the skeleton of .
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 is the skeleton of a coupled matroid and is a bridge of , then the vertices in are pairwise adjacent in .
Proof. Suppose that there are two distinct non-adjacent vertices in . Let be the torso of . By the definition of the attachment set there is an element of that is not spanned by and there is an element of that is not spanned by . However, is a framework. Thus we can cover by two proper flats (those spanned by and ), 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 is a 3-patch in a patchwork , then there is a triangle in the torso of such that is isomorphic to and each two-element subset of is realizable.
Proof. Let . Since is connected, there is a circuit in that contains and . Since is coupled, . Since and are both connected, so is . By Lemma 5.3, there is a strand for in that contains . Let . Note that
(i) is independent in ,
(ii) is a circuit in
(iii) is connected and has corank 2, and
(iv) .
The torso of spans a line and by Lemma 11.1, there are at least three elements in . One of those elements, say , is at the point where the spans of and meet. Thus is a triangle. Since is coupled, every point on must lie on one of the lines spanned by two of , and since is connected, they cannot all lie on the line spanned by . Then must be a triangle and there exist elements such that and are both triangles. Thus is isomorphic to . Now is connected and has corank 2, so it contains a triad, say . Let be the matroid obtained from by contracting . Note that is a modular triangle in and is a triad. Now by contracting different elements of , we see that any two-elements of is realizable, as required. □
The following result is the upgrade of Lemma 10.2 to patchworks.
Lemma 11.3. Let be the skeleton of a patchwork , let be the attachment set of an element that is spanned by , and let . If is 2-connected and has a three-point plane, then there is a circuit in that contains three or more elements of .
Proof. Let be the torso of . By Lemma 11.2, there is a restriction of such that
(a) every pair of adjacent vertices in remain adjacent in the skeleton of , and
(b) every independent subset of is realizable in . By Lemma 10.2, there is a circuit in that contains at least three elements in . Since is realizable, there is a circuit in that contains at least three elements in .
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 we write for the simplification of ; that is we delete all loops and all but one edge from each parallel class.
Lemma 11.4. Let be the skeleton of a patchwork , let be the attachment set of an element that is spanned by , and let . If
(i) ,
(ii) the vertices in are pairwise adjacent in ,
(iii) is -connected and is a subdivision of a -connected graph, and
(iv) for each degree-two vertex in , there is a -patch of such that and such that spans ,
then there is a circuit in that contains three or more elements of .
Proof. Suppose not and consider a counterexample with minimum. Since is -connected, is simple. Moreover, since the attachments of any -patch are pairwise adjacent, by (iv), there are no two adjacent vertices of degree in . By Motzkin’s Lemma, has an ordinary plane . By Lemma 11.3, is not a three-point plane, so is the union of a long line and a point . Consider an -separation of order in such that is the closure of in . Let and be the two vertices in . Every other vertex in has degree- in and is adjacent to only and . Since is a long line, there are at least three vertices of in . It follows easily from minimality that every vertex in is in .
Consider a vertex and let be a -patch of such that and such that spans . Note that . Our goal is to find a strand in , whose base-point is not in the the line spanned by , such that the attachment set of in is . In doing this, we may lose the edge connecting and , but that only happens in the case that . In either case remains an ordinary plane. When we have a contradiction to minimality and when , we end up with an ordinary plane and can apply Lemma 11.3.
Let be the image of in (recall that image was defined immediately before Lemma 10.1). Now consider the torso of . Note that is a plane spanning and is round. Since is round, the set of points in outside the span of still span . Let be a 3-element independent subset of outside the span of . Since is coupled, the elements of lie on the two lines spanned by and . Up to symmetry, we may assume that two of the three elements in lie on the line spanned by ; one of these two, say , is not on the line spanned by . Now, is a triangle in . Thus is a circuit in . So we get the desired minor by taking a strand in with base point .
Connectivity in frameworks and patchworks
Let be a patchwork with skeleton and let and be subsets of . Our next goal is to show that the matroid connectivity is equal to the graph connectivity. Recall that our definition of , in Section 5, allows and to intersect.
Lemma 12.1. Let be a framework with skeleton and let and be subsets of , then the connectivity from to in is equal to the connectivity from to in .
Proof. Let be the edge set of disjoint paths from to in , and let be the ends in and be the ends in . Then and are point-wise equivalent independent sets in the planted matroid , which implies that . Conversely, if there is a separation of order in with and , then no component in the projection contains both an element of and an element of , which implies that .
A separation in a rooted matroid is a pair of rooted matroids such that , , and each bridge of either or is also a bridge in ; the order of the separation is . If is a patchwork with skeleton , and , then the connectivity from to in is the minimum order of a separation with and . If is the skeleton of the patchwork , then it is easy to see that the connectivity from to in is the same as the connectivity from to $Y i…
Lemma 12.2. Let be a patchwork and let and be subsets of , then the connectivity from to in the matroid is equal to the connectivity from to in the patchwork .
Proof. Suppose that the connectivity from to in is , and let be the skeleton of . Choose a set of disjoint paths having as few edges as possible and let be the edge-set of those paths. By minimality, contains at most one base point from each patch of , therefore the subgraph is realizable, and hence, by Lemma 12.1, we have . Conversely, there is a separation of order in with and , and no non-loop component in the projection contains both an element of and an element of , which implies that .
It is implicit in the proofs of Lemmas 12.1 and 12.2 that the connectivity between and in a patchwork is obtained via paths in the skeleton, and that a path between distinct elements and gives a circuit. This is made more precise in the following result, whose easy proof is omitted.
Lemma 12.3. Let be a patchwork and let and be subsets of . If the connectivity from to in is , then there is a restriction of such that , , and each component of is either a coloop or a circuit containing exactly one element of and exactly one element of .
In the rest of this section we consider a minimum order -separation in relative to the patchwork . We show that we can “display” the separation in a patchwork but with a possibly different set . As a point of caution, the set 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 -separations in , without changing , but, fortunately, we do not need that.
Lemma 12.4. Let be a patchwork, let and be subsets of , and let be a minimum order -separation in . Then there exists and sets and such that
is a patchwork, and
is a separation of order in with and .
Proof. Let and let . By Lemma 12.3, there exist circuits in such that and each of the circuits contains exactly one element from each of and . Now let be the rank- subspace of that is spanned by both and . Note that no non-loop component of contains both an element of and an element of . Therefore, for each there is a non-loop element that is spanned by .
Since , the set is a basis of and, hence, each of the circuits spans exactly one element in . Therefore, for each , the circuit breaks into two circuits and in .
We will show that there exists a basis of the the subspace spanned by such that is a patchwork and, up to point-wise equivalence, contains both and . By symmetry, this would also give a basis of the the subspace spanned by such that is a patchwork and, up to point-wise equivalence, contains both and . Our result will then follow by taking a basis of .
Consider the matroid and the patchwork . Note that, for each , the set is a series class in having as its base point. Since is coupled in , this series class contains exactly one element of and that element, say , is in . When we contract the other elements in the series class, lands in parallel with . By Lemma 9.3, we get a minor of the patchwork where and, up to point-wise equivalence, contains both and , as required. □
Extending a patchwork
Our first result of this section deals with extensions that belong in a patch.
Lemma 13.1. Let be a patchwork with skeleton , let , and let be an element of in the span of such that is coupled. If with , and the connectivity from to in is , then there is a set in , containing , such that is a patchwork.
Proof. Let . Consider a -separation of order in . Note that is a minimum order -separation in with maximum. This uniquely determines and thus is in the span of . By Lemma 12.4 and possibly changing the set , we may assume that there is a separation of order in such that is a restriction of and is a restriction of . Since , is a patchwork. Furthermore, since is spanned by , each bridge of has at most three attachments. To complete the proof it remains to show that each bridge of is coupled, moreover it suffices to check the bridge containing which holds since, by construction, the connectivity from to in the skeleton is , so we can take a minor of such that is point-wise equivalent to a subset of .
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 looks like an edge from the point of view of the patch.
Lemma 13.2. Let be a patchwork with skeleton , let , and let be an element of in the span of such that is coupled. Now, for , let be a patch, with , such that is not in the span of and . Then there exists in the span of and in the span of such that is on the line spanned by and in and such that is coupled.
Proof. By Tutte’s linking theorem, there is a minor of such that the local connectivity between and is and the local connectivity between and is in . Since and are both contained in and is coupled in , the set is point-wise equivalent with some subset of in . Let be a basis of that contains . There is an element in , in the span of such that spans ; moreover this point is unique, up to equivalence. Note that the span of in contains the span of in , so we may assume that the element is in the span of in .
Now, up to equivalence, there is a unique point in that is spanned by such that is on the line spanned by and in . Note that contains the line spanned by and in so we can choose on that line. Since is obtained from by projecting out elements in , the point is spanned by in . Since is connected, we can contract into the span of . However, is coupled, so must be point-wise equivalent with an element of and, however, we contract into the span of it must land in parallel with an element of . Thus is coupled, and hence, so is .
Resilient patchworks
In the proof of the main theorem, it is convenient to work with a patchwork such that
for each patch with , the matroid is vertically 3-connected, and
the skeleton of is 3-connected.
We say that the patchwork is resilient if it satisfies these two properties.
Lemma 14.1. Let be a 3-patch in a patchwork . If is vertically 3-connected, but is not vertically 3-connected, then there is an element in that is spanned by , but not by , such that is a patchwork.
Proof. Consider a vertical separation of order 1 in . Since is vertically 3-connected, there is an element that is not spanned by and an element that is not spanned by . Let be a non-loop element in that is spanned by both and . Since is a patch, is connected, and hence is not spanned by . It is now easy to see that is a patchwork, as required.
Therefore, if we are given a patchwork such that is vertically 3-connected, we can obtain (1) by adding vertices. If the skeleton of the resulting patchwork is not 3-connected, then we will get a separation of order at most 2 in with and both non-empty. Note that, and are both patchworks, and, moreover, if satisfies (1) then so do both and .
We have proved the following result.
Lemma 14.2. Let be a rooted matroid such that is vertically 3-connected and each pair of distinct elements in span a long-line in . If there is a patchwork whose vertex-set contains , then there is a resilient patchwork whose vertex-set contains .
The main theorem
Our main result is:
Theorem 15.1. If is a coupled matroid, then there is a patchwork with .
Proof. We consider a counterexample such that is minimum, and, subject to that, the number of elements of that are not spanned by is minimum. We may further assume that: is simple, is empty, and each pair of distinct elements in span a long line in . Note that , since otherwise is, itself, a patchwork. By Lemma 8.2, is vertically 4-connected.
Let be an element of that is not in the span of . By minimality, there is an independent set in , containing , such that is a patchwork. We choose such that is resilient (see Lemma 14.2) and, subject to that, with is as large as possible. We extend to a basis of and let be a minimal subset of that spans .
By Lemma 13.1, we have
15.1.1. For any set with , the connectivity from to in is .
We will call a patch of blocked if is non-empty.
Our first non-trivial claim is:
15.1.2. If is a blocked patch of , then and there exists an element in that is spanned by such that is a patchwork and such that is spanned by .
Proof of claim. By Lemma 13.1, we may assume that the connectivity from to in is . Then, by Lemma 13.2, for each patch of there is an element that is spanned by such that is coupled and is spanned by . If , then is a patchwork, as required. Therefore, we may assume that .
Let be obtained from by adding elements so that the lines spanned by any two elements in in are long. By minimality, there is a patchwork with and we can choose such that is resilient. Now is a resilient patchwork, but, by our choice of , the patchwork is not resilient. Now and have the same non-trivial patches, so the issue is that the skeleton of is not 3-connected. However, since is resilient, is vertically 3-connected, so the skeleton of is 2-connected. Moreover, there are three disjoint paths from to in . So there are three internally-disjoint paths connecting any two vertices of in . Consider a separation of order 2 in with and , and, subject to that take maximum. Note that and . Moreover is the closure of the neighbour set of in in the matroid . Now is a resilient patchwork with , however, since is in the span of a 3-patch in , whereas in we can disconnect from by projecting out only two vertices, namely, .
Applying Claim 15.1.2 to each blocked patch of we obtain a set such that
(a) is a patchwork with ,
(b) spans ,
(c) for each blocked patch of , there is exactly one element of that is spanned by , and
(d) for each , there is a blocked patch of such that is spanned by .
Since is vertically 4-connected, each nontrivial patch of has three attachments and spans . Let denote the skeleton of and let be the attachment set of . Note that
(i) each vertex is contained in and has exactly two neighbours in ,
(ii) any two distinct vertices in are adjacent in if and only if they are either adjacent in or they have a common neighbour in in .
This implies that is a subdivision of a 3-connected graph. Now it follows from Lemma 11.4, that . 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]K. Chakravarti and N. Robertson, Covering three edges with a bond in a non-separable graph, Annals of Discrete Math. 8 (1980), 247.
- [2]T. Gallai, Solution to Problem 4065. Amer. Math. Monthly 51 (1944), 169–171.
- [3]E. Melchior, Über vielseitige der projektiven ebene, Deutsche Mathematik, 5(1) (1941), 461–475.
- [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]J.G. Oxley, Matroid Theory, Second edition, Oxford University Press, New York, 2011.
- [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]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]P.D. Seymour, Disjoint Paths in Graphs, Discrete Mathematics 29 (1980), 293–309.
- [9]P.D. Seymour, Triples in Matroid Circuits, European Journal of Combinatorics 7 (1986), 177–185.DOI
- [11]P.D. Seymour, Recognizing Graphic Matroids, Combinatorica 1 (1981), 75–78.DOI
- [12]J.J. Sylvester, Mathematical Question 11851. Educational Times 59 (1893) 98.
- [13]C. Thomassen, 2-Linked Graphs, European Journal of Combinatorics 1 (1980), 371–378.DOI
- [14]W.T. Tutte, Lectures on Matroids, Journal of Research of the National Bureau of Standards, Section B 69B (1965), 1–47.DOI
- [15]T. Zaslavsky, Biased Graphs. II. The Three Matroids, Journal of Combinatorial Theory, Series B 51 (1991), 46–72.DOI