$P_{8}^{=}$ is not a gammoid

Guest post by Joe Bonin.

In his talk at the recent workshop in Eindhoven, Immanuel Albrecht noted that each matroid in the appendix of examples in James Oxley’s book Matroid Theory is designated as either being a gammoid or not, except for $P_8^=$. In this post, we show that $P_8^=$ is not a gammoid. The ideas used may apply more widely.

Transversal and cotransversal matroids

Gammoids are minors of transversal matroids, so in this section, we sketch the items about transversal matroids and their duals that we use. Those who know the characterization of transversal and cotransversal matroids in Theorems 2 and 3 might prefer to omit this introductory section.

We start with a bipartite graph with vertex classes $S$ and $T$. We will use the example below, with $S=\{a,b,c,d,s,t,u\}$.

Figure 1

A partial transversal is a subset of $S$, such as $\{a,b,u\}$ above, that can be matched with a subset of the vertices in $T$ via edges in the graph. The partial transversals are the independent sets of the resulting transversal matroid.

For $X\subseteq S$, let $N_G(X)$ denote the set of neighbors of $X$ in $G$, that is,
$$N_G(X) = \{v\in T\,:\, v \text{ is adjacent to at least one } x\in X\}.$$ A set $X$ in a matroid $M$ is cyclic if $X$ is a union of circuits, that is, $M|X$ has no coloops. The cyclic flats in the example are $\emptyset$, $\{a,c,s,t\}$, $\{b,d,t,u\}$, $\{a,d,s,u\}$, $\{b,c,s,u\}$, and $S$. In this example, the rank of each cyclic flat ($0$, $3$, $3$, $3$, $3$, and $4$, respectively) is its number of neighbors. This illustrates the lemma below.

Lemma 1. Let $G$ be a bipartite graph on $S\cup T$ that represents $M$. If $X$ is a cyclic set of rank $k$ in $M$, then $|N_G(X)|=k$.

Proof. A basis of $X$ can be matched to the vertices in some $k$-element subset $T’$ of $T$. Let $G’$ be the induced subgraph of $G$ on $S\cup T’$, so $G’$ gives a rank-$k$ transversal matroid $M’$ on $S$, and $r_{M’}(X)=k$.

We first show that $M’|X=M|X$. Independent sets in $M’|X$ are independent in $M|X$. If the converse failed, then some circuit $C$ of $M’|X$ would be independent in $M|X$. Since $C$ can be matched in $G$ but not in $G’$, some $a\in C$ is adjacent to a vertex $v\in T-T’$. Extend $C-a$ to a basis $B$ of $M’|X$. Now $r_{M’}(X)=k$, so matching $B$ with the vertices in $T’$ and $a$ with $v$ gives the contradiction $r_M(X)>k$. Thus, $M’|X=M|X$.

We now get that $N_G(X)=T’$, for if instead some $b\in X$ were adjacent to some vertex $v\in T-T’$, then the same type of matching argument, using a basis $B$ of $M|X$ with $b\not\in B$ (which exists since $b$ is not a coloop of $M|X=M’|X$), would yield a contradiction. Thus, $|N_G(X)|=k$. $\square$

This proof adapts to show that we can always choose $G$ so that $|T|=r(M)$.

The bipartite graph $G$ on $S\cup T$ is an induced subgraph of a bipartite graph $G’$ on $S’\cup T$ in which, for each $x\in T$, there is a $y\in S’$ with $N_{G’}(y)=\{x\}$. Such an extension of our example above is shown below; the red vertices have been added.

The bipartite graph $G$ on $S\cup T$ is an induced subgraph of a bipartite graph $G’$ on $S’\cup T$ in which, for each $x\in T$, there is a $y\in S’$ with $N_{G’}(y)=\{x\}$. Such an extension of our example above is shown below; the red vertices have been added.

Figure 2

The resulting matroid $M’$ is an extension of $M$.

Pick a subset $B$ of $S’$ (for example, the red and green vertices above) for which, for each $x\in T$, there is one $y\in B$ with $N_{G’}(y)=\{x\}$. Clearly $B$ is a basis of $M’$. Moreover, if $X$ is a cyclic flat of $M’$, then $X\cap B$ is a basis of $X$ since $r(X) = |N_{G’}(X)|$ by Lemma 1, so the flat $X$ must contain the elements of $B$ that are adjacent to the vertices in $N_{G’}(X)$. Thus, $r_{M’}(X) = |X\cap B|$. It is not hard to show, more generally, that for any cyclic flats $X_1,X_2,\ldots,X_n$ of $M’$,
r_{M’}(X_1\cup X_2\cup \cdots \cup X_n )= \bigl|B\cap (X_1\cup X_2\cup
\cdots \cup X_n)\bigl|
r_{M’}(X_1\cap X_2\cap \cdots \cap X_n) = \bigl|B\cap (X_1\cap X_2\cap
\cdots \cap X_n)\bigr|.
From these equations and inclusion/exclusion, it follows that
r_{M’}(X_1\cap X_2\cap \cdots \cap X_n) =
\sum_{J\subseteq[n]} (-1)^{|J|+1}r_{M’}\bigl(\bigcup_{j\in J}X_j\bigr).

A transversal matroid might not have the type of basis that we used to derive the equalities above, but we do get the inequality in Theorem 2 below. To see this, delete $S’-S$ to get the original transversal matroid $M$. The rank of unions of cyclic flats of $M$ are the same as for their closures in $M’$, but the rank of intersections may be less. This proves the half of Theorem 2 that we will use. (For a proof of the converse, see [1].) John Mason proved this result for cyclic sets and Aubrey Ingleton refined it to cyclic flats. We let $\cup\mathcal{F}$ denote the union of a family of sets, and we use $\cap\mathcal{F}$ similarly.

Theorem 2. A matroid $M$ is transversal if and only if for all nonempty sets $\mathcal{A}$ of cyclic flats of $M$,
r(\cap\mathcal{A})\leq \sum_{\mathcal{F}\subseteq \mathcal{A}} (-1)^{|\mathcal{F}|+1} r(\cup\mathcal{F}).

We will use the dual of this result, which we state next. Duals of transversal matroids are called cotransversal matroids or strict gammoids.

Theorem 3. A matroid $M$ is cotransversal if and only if for all sets $\mathcal{A}$ of cyclic flats of $M$,
r(\cup \mathcal{A}) \leq \sum_{\mathcal{F}\subseteq \mathcal{A}\,:\,\mathcal{F}\ne\emptyset}
(-1)^{|\mathcal{F}|+1}r(\cap \mathcal{F}).\qquad\qquad (1)

Gammoids and $P_8^=$

Restrictions of transversal matroids are transversal, so any gammoid (a minor of a transversal matroid) is a contraction of a transversal matroid. The set we contract can be taken to be independent since $M/X =M\backslash (X-B)/B$ if $B$ is a basis of $M|X$, so any gammoid is a nullity-preserving contraction of a transversal matroid. The class of gammoids is closed under duality, so we get Lemma 4 below.

Lemma 4. Any gammoid has a rank-preserving extension to a cotransversal matroid.

Because of this lemma, below we focus exclusively on extensions that are rank-preserving.

We will also use the corollary below of the following theorem of Ingleton and Piff [2].

Theorem 5. A matroid of rank at most three is a gammoid if and only if it is cotransversal.

Corollary 6. Let $M$ be a rank-$r$ matroid with $r\geq 3$. If $H_1$, $H_2$, $H_3$, and $H_4$ are cyclic hyperplanes, any two of which intersect in a flat of rank $r-2$, and each set of three or four intersects in a flat $X$ of rank $r-3$, then $M$ is not a gammoid.

Proof. In $M/X$, the sets $H_i-X$, for $1\leq i\leq 4$, are cyclic lines. (Contraction does not create coloops.) The rank of the union of these four cyclic lines is $3$, but the alternating sum in inequality (1) is $4\cdot 2 – 6\cdot 1 = 2$, so $M/X$ is not cotransversal by Theorem 3. Thus, since $r(M/X)=3$, it is not a gammoid by Theorem 5, so $M$ is not a gammoid. $\square$

To show that $P_8^=$ is not a gammoid, we focus on a particular failure of inequality (1) in $P_8^=$ and show that between $P_8^=$ and any extension $M’$ of $P_8^=$ in which the counterpart of that particular inequality holds, we have a single-element extension of $P_8^=$ to which Corollary 6 applies. Thus, any such $M’$ has a restriction that is not a gammoid, so $M’$ is not cotransversal, and so $P_8^=$ is not a gammoid by Lemma 4.

To define $P_8^=$, we first briefly discuss $P_8$, which we get by placing points at the vertices of a cube and twisting the top of the cube an eighth turn. Label the points in the top and bottom planes of $P_8$ as shown below (the second diagram shows the view from above). We get $P_8^=$ by from $P_8$ by relaxing the circuit-hyperplanes $\{a,b,c,d\}$ and $\{s,t,u,v\}$.

Figure 3

From this, we see that the cyclic flats of $P_8^=$, besides the empty set and the whole set, are the following planes. In each, we put what we call its diagonal in bold.
\quad\{\mathbf{a},\mathbf{c},s,t\} \quad

Observe that each cyclic plane $X$ intersects five others in exactly two points (this includes all four cyclic planes that are not in the same row as $X$), and the remaining two cyclic planes in one point each (and those are different points). Thus, the number of sets of two cyclic planes that intersect in two points is $8\cdot 5/2 = 20$, and the number of sets of two cyclic planes that intersect in a single point is $8\cdot 2/2 = 8$. No triple of cyclic planes intersects in two points. Also, each point is in exactly four cyclic planes, so the number of sets of three planes that intersect in a singleton is $8\cdot 4=32$, and the number of sets of four points that intersect in a singleton is $8$.

Let $\mathcal{A}$ be the set of all eight cyclic planes. The term on the left side of inequality (1) is $4$. On the right side, the counting in the previous paragraph gives $$8\cdot 3 – 20\cdot 2 -8 + 32 -8 = 0.$$ Thus, inequality (1) fails.

Let $M’$ be a rank-preserving extension of $P_8^=$ in which the counterpart of this instance of inequality (1) holds. (If there is no such $M’$, then $P_8^=$ is not a gammoid, as we aim to show.) Think of constructing $M’$ by a sequence of single-element extensions. If each of these single-element extensions added a point to at most two of the cyclic planes of $P_8^=$, or parallel to a point of $P_8^=$, then the counterpart of this instance of inequality (1) would fail; thus, not all extensions are of these types. Focus on one point, say $e$, that is added to at least three cyclic planes of $P_8^=$ and not parallel to an element of $P_8^=$, and consider the single-element extension of $P_8^=$ formed by restricting $M’$ to $E(P_8^=)\cup e$. We show that, up to symmetry, there are only two such single-element extensions of $P_8^=$. As we see below, in both options, $e$ is added to exactly three cyclic planes, not more.

First consider adding $e$ to two cyclic planes that have the same diagonal, say, by symmetry, $\{a,c,u,v\}$ and $\{a,c,s,t\}$. We cannot add $e$ to $\{a,b,t,v\}$ since this plane intersects the other two in lines that share a point: adding $e$ to all three planes would give $r(\{a,v,e\})=2=r(\{a,t,e\})$, so either $e$ is parallel to $a$ (which we discarded) or $\{a,t,v\}$ would be a $3$-circuit, contrary to the structure of $P_8^=$. Similar reasoning eliminates adding $e$ to any plane in the second row. The only candidates left are $\{b,d,s,v\}$ and $\{b,d,t,u\}$, and we cannot add $e$ to both since then $\{a,c,e\}$ and $\{b,d,e\}$ would be lines that intersect in $e$, but $a,b,c,d$ are not coplanar.

Now assume that no two planes to which we add $e$ have the same diagonal. We must have a pair of sets in the same row but with different diagonals; by symmetry, we can use $\{a,c,u,v\}$ and $\{b,d,s,v\}$. An argument like the one above shows that the only other planes to which we can add $e$ are $\{a,d,s,u\}$ or $\{b,c,s,u\}$, and we cannot add $e$ to both since they have the same diagonal.

Thus, between $P_8^=$ and $M’$ we have a single-element extension $M$ of $P_8^=$ in which a point $e$ is added to exactly three of the original cyclic planes. By the argument above, up to symmetry, there are two cases to consider: the extended cyclic planes are either

  1. $\{a,c,u,v,e\}$,  $\{a,c,s,t,e\}$,  and $\{b,d,s,v,e\}$,  or
  2. $\{a,c,u,v,e\}$, $\{b,d,s,v,e\}$, and $\{a,d,s,u,e\}$.

In either case, the cyclic planes of $M$ that contain $v$, that is, $$\{a,c,u,v,e\}, \quad \{b,d,s,v,e\},\quad \{a,b,t,v\}, \quad\{c,d,t,v\},$$ satisfy the hypothesis of Lemma 6, so $M$ is not a gammoid. Thus, no coextension of $M$ is cotransversal, so $P_8^=$ is not a gammoid. Indeed, we have the result below.

Proposition 7. The matroid $P_8^=$ is an excluded minor for the class of gammoids.

To prove this, first check that $P_8^=$ is self-dual. With that and the symmetry of $P_8^=$, it suffices to check that $P_8^=\backslash v$ is a gammoid. One can check that it is the transversal matroid in our example in the introductory section.


[1] J. Bonin, J.P.S. Kung, and A. de Mier, Characterizations of transversal and fundamental transversal matroids, Electron. J. Combin. 18 (2011) #P106.

[2] A.W. Ingleton and M.J. Piff, Gammoids and transversal matroids, J. Combinatorial Theory Ser. B 15 (1973) 51-68.

Delta-matroids: Origins.

Guest post by Carolyn Chun.

In a previous post, Dr. Pivotto posted about multimatroids.  Her post includes a definition of delta-matroid, and a natural way that delta-matroids arise in the context of multimatroid theory.  I recommend her post to readers interested in multimatroids, which generalize delta-matroids.  I will discuss delta-matroids in this post, their discovery and natural ways that a mathematician may innocently stumble into their wonderful world.

Delta-matroids were first studied by Andre Bouchet [BG].  I use $X\bigtriangleup Y$ to denote symmetric difference of sets $X$ and $Y$, which is equal to $(X\cup Y)-(X\cap Y)$. To get a delta-matroid, take a finite set $E$ and a collection of subsets $\mathcal{F}$, called feasible sets, satisfying the following.

I) $\mathcal{F}\neq \emptyset$.

II) If $F,F’\in \mathcal{F}$ and $e\in F\bigtriangleup F’$, then there exists $f\in F\bigtriangleup F’$ such that $F\bigtriangleup \{e,f\}$ is in $\mathcal{F}$.

Then $D=(E,\mathcal{F})$ is a delta-matroid.

It is worth noting that the feasible sets of a delta-matroid can have different cardinalities.  Taking all of the feasible sets of smallest cardinality gives the bases of a matroid, namely the lower matroid for $D$.  Likewise the feasible sets with maximum cardinality give the bases of the upper matroid of $D$.  No other collections of feasible sets of a given size are guaranteed to comprise the bases of a matroid.

Taking minors in delta-matroids is modeled well by considering the bases of a matroid minor.  Take $e\in E$.  As long as $e$ is not in every feasible set (that is, $e$ is not a coloop), the deletion of $e$ from $D$, written $D\backslash e$, is the delta-matroid $(E-e,\{F \mid F\in\mathcal{F}\text{ and }e\notin F\}).$  As long as $e$ is not in no feasible set (that is, $e$ is not a loop), then contracting $e$ from $D$, written $D/e$,  is the delta-matroid $(E-e,\{F-e \mid F\in \mathcal{F}\text{ and }e\in F\})$.  If $e$ is a loop or coloop, then $D\backslash e=D/e$.

There are several natural ways to get to delta-matroids.  They keep showing up, like the page where you die in a choose-your-own-adventure book.  The stairs grow dimmer and dimmer as you walk down the stone staircase into darkness.  You hear what may be screams in the distance.  You finally reach a closed door and hold your candle up to read the label, scrawled in blood.  The label on the door in this metaphor is “delta-matroids,” and they are not as scary as I portrayed them in that story.


0) Choose your own adventure by preceding to the appropriate section.

1) “I studied embedded graphs and now I see delta-matroids everywhere.”

2) “Partial duality brings me to delta-matroids.”

3) “I left out a basis axiom when defining matroids.  Ahoy, delta-matroids!”

4) “Circle graphs seemed like fun.  Until they hatched into delta-matroids.”

5) “C’mon, skew symmetric matrices.  This can’t end in delta-matroids.  Or can it?”

6) “DNA recombination in ciliates is my cup of tea.  Who knew I was brewing delta-matroids?”

7) “I abandon this quest and run away.”


1) “I studied embedded graphs and now I see delta-matroids everywhere.”

One way to arrive at delta-matroids is by considering cellularly embedded graphs, which I like to think of as ribbon graphs, following [EMM].

To get a cellularly embedded graph, start with a surface (compact, connected 2-manifold), then put vertices (points) and edges (curves between vertices) onto the surface so that no edges cross and each face (unbroken piece of the surface enclosed by edges and vertices) is basically a disk.  That is, no face contains a handle or cross-cap.

The particular embedding of a graph encodes more information than the abstract graph, which just encodes adjacencies.  There’s an order to the edges incident with a vertex as you circumnavigate the vertex in the embedding, but not in the abstract graph.  If you take the matroid of an embedded graph, then you lose the extra information stored in the embedding and you wind up with the matroid of the abstract graph.  For example, a pair of loops is indistinguishable from a pair of loops, even though the first pair of loops are embedded in a sphere so that the graph has three faces, and the second pair of loops is embedded in a torus so that the graph has one face.  By looking at the matroid of an embedded graph, you can’t even tell if the graph is embedded in an orientable surface or a non-orientable surface.  So matroids are the wrong object to model embedded graphs.   

image001Here is a figure by Steven Noble, where $\mathcal{R}$ is the set of ribbon graphs.  The correspondence between graphs and matroids is akin to the correspondence between ribbon graphs and question mark.  Likewise, graphs are to embedded graphs as matroids are to question mark. Andre Bouchet showed that delta-matroids are the question mark.

To get a ribbon graph, begin with a cellularly embedded graph, cut around the vertices and edges, and throw away the faces.  The vertices have become disks, and the edges have become ribbons connecting disks. Each missing face counts as a boundary component in the ribbon graph.  We have not lost any of the information from our embedding, since the faces were just disks and can be glued back along the boundary components to return to the original presentation.  Spanning forests in a ribbon graph are exactly what you expect, and the edge sets of spanning forests of a ribbon graph give the bases of a matroid.  To get a quasi-tree, we are allowed to delete edges (remove ribbons) from our ribbon graph so that we leave behind a ribbon graph with exactly as many boundary components as the original graph had connected components.  Note that each spanning forest is a quasi-tree.  The edge sets of quasi-trees are the feasible sets of a delta-matroid.  The reader may take a break to draw a ribbon graph with quasi-trees of multiple sizes.  For more information along these lines, I refer you to [CMNR1] or [CMNR2].

You may be familiar with the mutually enriching relationship between graphs and matroids.  There appears to be a similar mutually enriching relationship between ribbon graphs and delta-matroids.  Tutte said, “If a theorem about graphs can be expressed in terms of edges and circuits only it probably exemplifies a more general theorem about matroids.”  To alter this quote for our purposes, we say, “If a theorem about ribbon graphs can be expressed in terms of edges and quasi-trees only it probably exemplifies a more general theorem about delta-matroids.”

Protip:  Not every delta-matroid can be represented by a ribbon graph.  Geelen and Oum gave an excluded minor characterization for ribbon-graphic delta-matroids in [GO].


2) “Partial duality brings me to delta-matroids.”

A planar graph has a nice, well-defined dual.  Not all graphs have well-defined duals.  A graph that is not planar that is cellularly embedded in a surface has a well-defined dual, but the dual depends on the surface.  The matroid of a graph has a well-defined dual, as do all matroids.  Matroids are nice and general in that sense.  The notion of partial duality was developed by Chmutov [CG] in the context of embedded graphs, which can be viewed as ribbon graphs, as discussed in ending (1).  To get the dual from a ribbon graph, replace the boundary components with vertices, and the vertices with boundary components.  Now the ribbons still link up the vertices, but they are short and thick, rather than being long and ribbony.  In fact, one way to look at taking a dual is to focus on the ribbon edges, and simply switch the parts of each edge that are incident with vertices with the parts of the edge that are incident with boundary components.  Furthermore, there’s nothing particularly special about switching parts of the ribbon edges for the entire ribbon graph, rather than just a subset of the edges.  We use $G^A$ to denote the partial dual of a ribbon-graph, $G$, with respect to the edge set $A$.

Here is a drawing of a partial dual for a ribbon graph that Iain Moffatt drew.  Actually, it is a slide from a talk by Steven Noble using Iain Moffatt’s figures, with a dash of copyright infringement.  Luckily, this is being used for educational purposes and I’m not being paid for this.  Unless Spielberg buys the movie rights to this.  Then I will cut Noble and Moffatt in on the profits.


Partial duality is also natural enough in matroids, but the partial dual of a matroid is rarely a matroid.  Recall that $X\bigtriangleup Y$ denotes symmetric difference of sets $X$ and $Y$, which is equal to $(X\cup Y)-(X\cap Y)$.  A matroid $M=(E,\mathcal{B})$ defined in terms of its bases has a dual that may be written $(E,\{E\bigtriangleup B \mid B\in\mathcal{B}\})$.  The dual of a matroid is a matroid.  Now, for a set $A\subseteq E$, the entity $(E,\{A\bigtriangleup B\mid B\in\mathcal{B}\}):=M*A$ is the partial dual with respect to $A$.  There is a way to make sure that the partial dual with respect to $A$ is a matroid.  The following result is Theorem 3.10 in [CMNR2].

Theorem.  Let $M=(E,\mathcal{B})$ be a matroid and $A$ be a subset of $E$.  Then $M*A$ is a matroid if and only if $A$ is separating or $A\in\{\emptyset,E\}$.

Whenever $A$ is not empty or the ground set of a component of the matroid, then the partial dual with respect to $A$ is (scrawled in blood) a delta-matroid!  Matroids may be too abstract for most human beings, but they are not quite abstract enough to accommodate partial duality, which is a natural notion generalizing from ribbon graphs.  Delta-matroids are the right object, and we tend to view the set of partial duals of a delta-matroid as all belonging to the same equivalence class, just as matroid theorists often view a matroid and its dual as belonging to one equivalence class.


3) “I left out a basis axiom when defining matroids.  Ahoy, delta-matroids!”

For a set $E$ and a collection $\mathcal{B}$ of subsets of $E$, the set $\mathcal{B}$ form the bases of matroid $(E,\mathcal{B})$ exactly when the following hold.

I) $\mathcal{B}\neq \emptyset$.

II) If $B,B’\in \mathcal{B}$ and $e\in B\bigtriangleup B’$, then there exists $f\in B\bigtriangleup B’$ such that $B\bigtriangleup \{e,f\}$ is in $\mathcal{B}$.

III) The sets in $\mathcal{B}$ are equicardinal.

Omit (III) and hello, sailor!  You have the definition of a delta-matroid!  Just change the word “bases” to the phrase “feasible sets.”


4) “Circle graphs seemed like fun.  Until they hatched into delta-matroids.”

You approach the nest full of circle graphs with the stealth and speed of a mongoose, only to discover they are cracking open, each containing an even delta-matroid, where even will be defined in a moment.  You should have known that a circle graph is a ribbon-graph in disguise, and a ribbon-graph is, in turn, just a dressed-up delta-matroid.  Geelen and Oum used this relationship in [GO] to find an excluded-minor characterization for ribbon-graphic delta-matroids.

A delta-matroid is even exactly when all of its feasible sets have the same parity.  They do not all have to have even parity, odd parity is also fine in an even delta-matroid, as long as the parity is exclusive.  Maybe a better title would be a monogamous delta-matroid, but maybe not.  A circle graph is easy to view as a ribbon-graph.  To get a circle graph, you start with a circle, and draw chords (straight lines) across it, and then you check to see which ones cross each other.  Your circle graph has a vertex for each chord, and an edge between each pair of vertices corresponding to chords that cross.  Go back to the chord diagram and fatten up your chords into ribbons, which cross each other.  Where two chords cross, just let one ribbon go over the other, we don’t restrict ourselves to two-dimensions.  It doesn’t matter which ribbon is higher than the other, but don’t put any twists into the edges.  Now view the circle as a big vertex.  Your chord diagram has become a ribbon-graph.  It is worth noting that the ribbon-graph corresponds to a graph embedded in an orientable surface.

The edges in your circle graph now correspond to pairs of intertwined loops in your ribbon-graph.  By intertwined, I mean that two loops, $a$ and $b$, incident with a single vertex so that, when you circumnavigate the vertex they share, you hit $a$, $b$, $a$, and then $b$; rather than $a$, $a$, $b$, and $b$.  Now the feasible sets of your delta-matroid include the empty set (because your vertex has a single boundary component), no single-element sets, and each pair $\{v,w\}$ where $vw$ is an edge in your circle graph.  Check this by drawing a big vertex and two interlaced ribbon-graph loops and tracing around the boundary components.  You will find there’s only one boundary component.  The rest of the feasible sets of the delta-matroid come from the remaining quasi-trees in the ribbon-graph, but you’ll find that, mysteriously, there are no quasi-trees with an odd number of edges.  Ribbon-graphs from orientable surfaces give even delta-matroids.  Bouchet showed that even ribbon-graph delta-matroids also come naturally from 4-regular directed graphs.  For more information along these lines, see Section 4.2 and Section 5.2 of [CMNR1].

Bouchet and Duchamp showed in [BD] that ribbon-graphs correspond to a subset of binary delta-matroids, which will be considered in (5).  They did this by giving an excluded minor characterization for binary delta-matroids.  In [GO], Geelen and Oum built on the work of Bouchet [BC] in the area of circle graphs and found pivot-minor-minimal non-circle-graphs. As an application of this they obtained the excluded minors for ribbon-graphic delta-matroids.


5) “C’mon, skew symmetric matrices.  This can’t end in delta-matroids.  Or can it?”

A lot of matroid theorists enjoy representable matroids, which have matrix representations.  Delta-matroids do not disappoint.  Take an $E$x$E$ skew-symmetric matrix over your favorite field.  For $A\subseteq E$, consider the $A$x$A$ submatrix obtained by restricting to the rows and columns labeled by elements in $A$.  If this submatrix is non-singular, then put $A$ into the collection $\mathcal{F}$.  Guess what $(E,\mathcal{F})$ is.  A delta-matroid!  Every ribbon-graphic delta-matroid has a partial dual that has a binary matrix representation.  If you pick a field with characteristic other than two, then your delta-matroids representable over that field will be even.  This follows from the nature of skew-symmetric matrices.  For more information along these lines, see Section 5.7 in [CMNR1]


6) “DNA recombination in ciliates is my cup of tea.  Who knew I was brewing delta-matroids?”

The title to this section may sound like a good pick-up line, but I have had no success with it.  Ciliates (phylum Ciliophora) are single-celled organisms that experience nuclear dimorphism.  Their cells each contain two nuclei, which contain different, but related, genomes. The DNA reconstruction in ciliates has something to do with 4-regular graphs, which can be thought of as medial graphs of ribbon graphs.  I’m out of my depth here, so I will refer you to the amazing work of people who know more about this subject.  Jonoska and Saito put together a book on biomathematics that is on my reading list.  I’ll highlight in particular an article by Brijder and Hoogeboom [BH] in this book for more delta-matroids.  While you’re waiting for your local library to order that book, I suggest checking out [AJS] by Angeleska, Jonoska, and Saito.


7) “I abandon this quest and run away.”

Very well, you decide to abandon this quest and run away.  You drop your axe.  You put down your boomerang.  You throw away your ninja stars.  You retire the commander of your armies, and donate your blowtorches to charity.  You turn from the Siren-like call of the delta-matroids, but what is that sound?  Is the song growing stronger even as you run away?  Yes, delta-matroids seem to be in front of you every direction you face.  After a meltdown or two, you pull yourself together and return to (0), resolved to pick a different course of action.


[AJS] A. Angeleska, N. Jonoska, and M. Saito. DNA recombination through assembly graphs. Discrete Applied Mathematics. 157:14 (2009) 3020–3037.

[BC] A. Bouchet, Circle graph obstructions, J. Combin. Theory Ser. B. 60 (1994) 107–144.

[BG] A. Bouchet, Greedy algorithm and symmetric matroids, Math. Program. 38 (1987) 147– 159.

[BD] A. Bouchet and A. Duchamp, Representability of delta-matroids over GF(2), Linear Algebra Appl. 146 (1991) 67–78.

[BH] R. Brijder and H. Hoogeboom, The algebra of gene assembly in ciliates.  In: N. Jonoska and M. Saito (eds.) Discrete and Topological Models in Molecular Biology. Natural Computing Series, Springer, Heidelberg (2014) 289—307.

[CG] S. Chmutov, Generalized duality for graphs on surfaces and the signed Bollobás–Riordan polynomial, J. Combin. Theory Ser. B. 99 (2009) 617–638.

[CMNR1] C. Chun, I. Moffatt, S. Noble, and R. Rueckriemen, Matroids, delta-matroids, and embedded graphs, arXiv:1403.0920.

[CMNR2] C. Chun, I. Moffatt, S. Noble, and R. Rueckriemen, On the interplay between embedded graphs and delta-matroids, arXiv:1602.01306.

[EMM] J. Ellis-Monaghan and I. Moffatt, Graphs on surfaces: Dualities, Polynomials, and Knots, Springer, (2013).

[GO] J. Geelen, S. Oum, Circle graph obstructions under pivoting. J. Graph Theory. 61 (2009) 1–11.

Matroids representable over the Hydra-5 and 2-regular partial fields.

Guest post by Ben Clark.

1. Introduction

This post is an informal discussion of an ongoing project to find the excluded minors for the classes of matroids that arise from two partial fields, the Hydra-5 partial field and the 2-regular partial field. Stefan’s earlier posts on partial fields and stabilizers are highly recommended as background.

2. The Classes

The Hydra-5 partial field, $\mathbb{H}_5$, was introduced by Pendavingh and Van Zwam [PZ10]. The class of $\mathbb{H}_5$-representable matroids can essentially be thought of as the class of matroids having six inequivalent representations over $\text{GF}(5)$. The excluded minors for this class of matroids are the first step in a 5-step process to find the excluded minors for the class of $\text{GF}(5)$-representable matroids, as described in [MWZ12].

The 2-regular partial field, $\mathbb{U}_2$, was introduced by Semple [S97]. Representations over this partial field are the natural generalisation of `totally unimodular’ and `totally near-unimodular’ representations over the regular and near-regular partial fields. It is therefore natural to ask if $\mathbb{U}_2$ captures the class of matroids representable over all fields of size at least four, but sadly that’s not the case. However, we do expect the excluded minors for the class of $\mathbb{U}_2$-representable matroids will shed light on the following problem.

Problem 1. Find the partial field $\mathbb{P}$ such that the set of $\mathbb{P}$-representable matroids is exactly the set of matroids representable over $\text{GF}(4)$ and all larger fields.

The classes of matroids that arise from $\mathbb{H}_5$ and $\mathbb{U}_2$ are closely related (the latter is a subset of the former), and it seems that any differences in the excluded-minor analyses can be confined to finite case checks.

3. Inequivalent representations

Broadly speaking, we follow the strategy used in Geelen, Gerards and Kapoor’s excluded-minor characterisation of the $\text{GF}(4)$-representable matroids [GGK00]. The first step is to construct a candidate matrix for an excluded minor $M$. That is, a candidate for a representation of $M$ that we construct by piecing together representations for some of its minors, say $M\backslash a$ and $M\backslash b$. The construction of this candidate representation is complicated by the possibility of inequivalent representations, that is, the minors $M\backslash a$ and $M\backslash b$ could have representations that we cannot piece together.

The way around the problem of inequivalent representations is to keep a certain minor and sufficient connectivity. We have a class of $\mathbb{P}$-representable matroids for some fixed partial field $\mathbb{P}$. A matroid $N$ is called a strong stabilizer for the class of $\mathbb{P}$-representable matroids if every $\mathbb P$-representation of $N$ extends uniquely to a $\mathbb{P}$-representation of any 3-connected $\mathbb{P}$-representable matroid having $N$ as a minor. In [GGK00], the strong stabilizer is $U_{2,4}$. For the partial fields $\mathbb{U}_5$ and $\mathbb{U}_2$, the strong stabilizer is $U_{2,5}$ (and its dual $U_{3,5}$).

We can therefore construct a candidate matrix $A$ for the excluded minor $M$. Since $M$ is an excluded minor, there must be some difference between the subdeterminants of $A$ and the corresponding subsets of $M$. In fact, we can choose $A$ so that this difference is certified by a $2\times 2$ subdeterminant of $A$ (see [MWZ12]). We call the corresponding set of elements an incriminating set for $(M,A)$.

4. Fragility

Since an excluded minor $M$ is minimal with respect to being non-representable, we deduce that there are no elements that can be removed (in the right way relative to the candidate matrix $A$) keeping all three of: the strong stabilizer $N$ minor, sufficient connectivity, and the incriminating set. Considering only the elements that are required to keep the $N$-minor, it follows that $M$ has some minor $M’$ with the property that $M’\backslash e$ or $M’/e$ has no $N$-minor for every element $e$ of $M’$. Matroids with this property are said to be $N$-fragile, and we can think of them as the foundation for building excluded minors.

In [GGK00], it is shown that the $\text{GF}(4)$-representable $U_{2,4}$-fragile matroids are whirls. Here, we are interested in the structure of the $\mathbb{H}_5$- and $\mathbb{U}_2$-representable $\{U_{2,5}, U_{3,5}\}$-fragile matroids.

A matroid has path width $3$ if there is an ordering $(e_1, e_2, \ldots, e_n)$ of its ground set such that $\{e_1, \ldots, e_t\}$ is $3$-separating for all $t$. Gluing a wheel to $M$ is the process of taking the generalized parallel connection of $M$ with $M(\mathcal{W}_n)$ along a triangle $T$, and deleting any subset of $T$ containing the rim element. We proved the following.

Theorem 1. [CMWZ16] Let $\mathbb{P} \in \{\mathbb{H}_5, \mathbb{U}_2\}$. Let $M$ be a $3$-connected $\{U_{2,5}, U_{3,5}\}$-fragile $\mathbb{P}$-representable matroid with $|E(M)| \geq 10$. Then either

  1. $M$ or $M^*$ can be obtained by gluing up to three wheels to $U_{2,5}$; or
  2. $M$ has path width $3$.

In fact, we can describe the structure of the matroids in this class in much more detail, using the concept of generalized $\Delta$-$Y$ exchange.

The idea of the proof of Theorem 1 is to bound the size of a minimal counterexample to at most 12 elements, then obtain a contradiction by finding all of the $\mathbb{H}_5$-representable $\{U_{2,5}, U_{3,5}\}$-fragile matroids up to 12 elements and showing they have the right structure. The exhaustive search was made feasible by the development of Sage Matroid.

5. Further work

The foremost issue is another fragility problem. We would like to use Theorem 1 to determine the minimal $\{U_{2,5}, U_{3,5}\}$-fragile $\mathbb{P}$-representable matroids that could be used to build an excluded minor. This is relatively simple for whirls in the GF$(4)$ case, and also for the matroids in the first case of Theorem 1, using the structure to find `pivots’ in all but the smallest cases. However, there are families of fragile matroids of path width $3$ where these pivoting arguments are unsuccessful. These families of matroids have a `flan’-type path of $3$-separations.

Beyond that, there is an intertwining problem to solve to bridge the gap from the fragile minor to the incriminating set. This is attacked using blocking sequences in [GGK00]. An approach that we hope will simplify the problem is to make stronger connectivity assumptions on $M\backslash a,b$. We proved the following.

Theorem 2. [COSW16] Let $M$ be a sufficiently large excluded minor for the class of matroids representable over $\mathbb{H}_5$ or $\mathbb{U}_2$. Then $M$ has a $\{U_{2,5}, U_{3,5}\}$-minor, and if $M$ has a pair of elements $a,b$ such that $M\backslash a,b$ is $3$-connected with a $\{U_{2,5}, U_{3,5}\}$-minor, then $M\backslash a,b$ is a $\{U_{2,5}, U_{3,5}\}$-fragile matroid.

Roughly, the strategy for proving Theorem 2 is to assume there are elements that are `not fragile’, that is, elements we can remove to keep the stabilizer minor and the incriminating set. Removing such elements must destroy the $3$-connectivity, so we are able to deduce that $M\backslash a,b$ has a certain path of $3$-separations. Analysing this structure we find pivots if $M\backslash a,b$ is sufficiently large.

To date, we have no guarantee that a $3$-connected deletion pair exists, but progress towards finding such a pair is happening. Williams [W15] proved the following theorem. We say that a pair $a,b$ of elements of a 3-connected matroid $M$ is detachable if either $M\backslash a,b$ of $M/a,b$ is 3-connected.

Theorem 3. [W15] Let $M$ be a $3$-connected matroid with $|E(M)|\geq 12$. Then one of the following holds.

  1. $M$ is a spike; or
  2. $M$ contains a detachable pair; or
  3. There is a matroid obtained by performing a single $\Delta$-$Y$ operation on$M$ that contains a detachable pair.

The next step in this direction is to obtain a `splitter’ analogue of Theorem 3 that preserves a copy of a minor $N$.


[COSW16] B.Clark, J. Oxley, C. Semple, G. Whittle. Excluded minors are almost fragile. Submitted.

[CMWZ16] B.Clark, D. Mayhew, G. Whittle, S.H.M. van Zwam. The structure of $\{U_{2,5}, U_{3,5}\}$-fragile matroids. SIAM J. Discrete Math., to appear.

[GGK00] J. Geelen, A.M.H. Gerards, A. Kapoor. The Excluded Minors for GF(4)-Representable Matroids. J. Combin. Theory Ser. B, 79, 247-299, 2000.

[MWZ12] D. Mayhew, G. Whittle, S.H.M. van Zwam. Stability, Fragility, and Rota’s Conjecture. J. Combin. Theory Ser. B, 102(3):760-783, 2012.

[PZ10] R.A. Pendavingh, S.H.M. van Zwam. Confinement of matroid representations to subsets of partial fields. J. Combin. Theory Ser. B, 100(6):510-545, 2010.

[S99] C. Semple. On maximum-sized k-regular matroids. Graphs Combin., 15, 441-462, 1999.

[W15] A. Williams. Detachable pairs in 3-connected matroids.. PhD thesis, Victoria University of Wellington, 2015.

The complexity of the matching polytope and ear-decompositions of matroids

Guest post by Yohann Benchetrit.


The topic of this post is to introduce a new parameter $\beta$ measuring the complexity of the facets of the matching polytope of a graph, which also extends to binary matroids. We give a simple efficient algorithm deciding whether a binary matroid satisfies $\beta\leq 1$. This is the first non-trivial case after bipartiteness, which is equivalent to $\beta=0$. The results presented here are joint work with András Sebő, and appeared in [1].

The matching polytope of a graph plays an important role in Graph Theory and Combinatorial Optimization. The methods involved in the study of its structure and properties initiated many relations between polyhedra, min-max theorems and polynomial-time algorithms.

A matching of a graph is a set of pairwise non-incident edges. The incidence vector of a matching $M$ of a graph $G$ is the 0-1 vector $\chi^{M}$ of $\mathbb{R}^{E(G)}$ defined for every $e\in E(G)$ by: $\chi^{M}(e)=1$ if and only if $e\in M$. The matching polytope of $G$, denoted by $\mathsf{MATCH}(G)$, is the convex hull of the incidence vectors of the matchings of $G$. As a polyhedron, it is the set of solutions of a finite number of linear inequalities over $\mathbb{R}^{E(G)}$. Basically, information on the inequalities describing this polytope is useful as it allows applying linear programming tools (for example the duality theorem, the Ellipsoid method, etc.).

The following result, due to Edmonds and Pulleyblank [5], gives a complete description of the matching polytope using linear inequalities. A graph $H$ is factor-critical if for every $v\in V(H)$, the graph obtained from $H$ by deleting $v$ and every edge incident to $v$ has a perfect matching (a matching covering every vertex).

Theorem 1.  For every graph $G$:
x\geq 0, & \\
\displaystyle \sum_{\text{e incident to $v$}}x_e\leq 1 & \forall v\in V(G), \\
\displaystyle \sum_{e\in E(H)}x_e\leq \frac{|V(H)|-1}{2} & \text{$\forall H$ 2-connected factor-critical } \\
& \text{induced subgraph of $G$}

Furthermore, Edmonds [4] shows that each inequality associated with a 2-connected factor-critical induced subgraph $H$ appears in every description of $ \mathsf{MATCH}(G)$.

An ear-decomposition of a graph $G$ is a sequence $(P_0,\ldots,P_k)$ of a circuit $P_0$ and paths (with two distinct ends) $P_1,\ldots,P_k$ of $G$ such that $E(G)=E(P_0)\cup\ldots\cup E(P_k)$ and for every $i\in\left\{
1,\ldots,k\right\}$, $P_i$ meets $P_0\cup\ldots\cup P_{i-1}$ exactly on its two ends; the $P_i$ are the ears of the decomposition (notice that we do not allow an ear to attach on a single vertex). The decomposition is odd if all ears have an odd number of edges. Lovász proved:

Theorem 2.  A graph is 2-connected and factor-critical if and only if it has an odd ear-decomposition.

It follows from Menger’s theorem that a graph admits an ear-decomposition if and only if it is 2-connected. In addition, all ear-decompositions of a 2-connected graph $G$ have the same number $|E(G)|-|V(G)|+1$ of ears (indeed, deleting a single edge from each ear of an arbitrary ear-decomposition yields a spanning tree), hence the number of ears of $G$ is well-defined.

This and Lovász’s result suggest the following measure of complexity of the matching polytope:

Definition 3.  For each graph $G$, let $\beta(G)$ denote the largest number of ears of a 2-connected factor-critical subgraph of $G$.

For example, $\beta(G)=0$ if and only if $G$ is a bipartite graph, and $\beta(G)\leq 1$ if and only if $G$ does not contain three pairwise internally-disjoint paths with the same ends, such that exactly two of them have an odd number of edges.

The Parity Minor Algorithm [6] implies that for each fixed $k$, determining whether a graph $G$ satisfies $\beta(G)\geq k$ can be done in polynomial-time.  However, the proof in [6] is built upon elaborate techniques of the Graph Minor Project, and is oriented towards generality. This suggests searching for more adapted algorithms. In this direction, Bruhn and Schaudt [2] provided a direct solution to test $\beta\leq 1$ efficiently for graphs with maximum degree 3.

In the rest of this post, we extend $\beta$ to binary matroids and characterize those which satisfy $\beta\leq 1$. As a consequence, we obtain an elementary polynomial-time algorithm for testing whether a binary matroid $M$ satisfies $\beta(M)\leq 1$ or finding an obstruction, only using ear-decompositions and basic computations in the cycle space (mod 2). This completely avoids Graph Minors and implies a rather simple algorithm deciding $\beta\leq 1$ in graphs, with no restriction on the degree.

Also, applying our result to the co-graphic case yields an unexpected consequence: determining whether a graph has two odd bonds meeting on an even number of edges can be carried out efficiently.

Our motivation in studying $\beta$ comes from the recognition problem for $h$-perfect graphs. A graph is $h$-perfect if the convex hull of the incidence vectors of its stable sets (sets of pairwise non-adjacent vertices) is completely described by non-negativity and rank-inequalities of cliques and odd circuits.  The class of $h$-perfect graphs are a superclass of perfect graphs, and share a number of similar properties with the latter (see the second volume of Schrijver’s Combinatorial Optimization for further details).

Whereas perfection can be checked in polynomial-time, it is still open whether the same holds for $h$-perfection. Testing the $h$-perfection of a line graph $L(G)$ is essentially equivalent to checking $\beta(G)\leq 1$, and thus our results on $\beta$ directly imply a simple algorithm recognizing $h$-perfect line graphs.

Testing $\beta\leq 1$ in Binary Matroids

An ear-decomposition of a matroid $M$ is a sequence $(C_1,\ldots,C_k)$ of circuits of $M$ such that: $C_1\cup \ldots \cup C_k=E(M)$ and for each $i\in\left\{2,\ldots,k \right\}$, $C_i$ meets both $\cup_{j<i}C_j$ and its complement, and $C_i\setminus (\cup_{j<i}C_j)\neq\emptyset$ is a circuit of the contraction $M/(\cup_{j<i}C_j)$. The ear-decomposition is odd if the sets $C_i\setminus (\cup_{j<i}C_j)$ (the ears) all have odd cardinality (for $i\in\left\{1,\ldots,k\right\}$).

A matroid is factor-critical if it has an odd ear-decomposition.  It is easy to check that a matroid has an ear-decomposition if and only if it is connected, and that all the ear-decompositions of a connected binary matroid have the same number $|E(M)|-\mathsf{rk}(M)$ of ears. Hence, for each binary matroid $M$,  we may define $\beta(M)$ as the largest number of ears of a factor-critical restriction of $M$. It is straightforward to check that the values of $\beta$ for a graph and its circuit matroid are equal.

For algorithmic considerations, we assume that binary matroids are given by a linear representation or an independence oracle; complexity refers to the number of required calls to this oracle.

The first important observation is the following (see [1] for a proof).

Lemma 4.  A connected binary matroid $M$ satisfies $\beta(M)\geq 2$ if and only if it has two odd circuits which meet in an even number of elements.  Furthermore, a factor-critical restriction of $M$ with two ears can be constructed from two such odd circuits in polynomial-time.

This states that we have to check the parity of the intersection of every pair of odd circuits of $M$ to certify that $\beta(M)\leq 1$. In fact, we need only to check it for pairs of a certain basis of the cycle space of $M$.

A cycle of a matroid is a union of disjoint circuits, and it is odd if it has odd cardinality.  The set of (incidence vectors of) cycles of a binary matroid $M$ is a subspace of $\mathbb{F}_2^{E(M)}$ (this characterizes binary matroids), called the cycle space of $M$ and denoted by $\mathcal{C}(M)$. Clearly, $\mathcal{C}(M)$ is spanned by the circuits of $M$ and $\dim \mathcal{C}(M)=|E(M)|-\mathsf{rk}(M)$ (consider the set of fundamental circuits of a basis). A set $S$ of cycles of $M$ is a cycle basis of $M$ if the incidence vectors of the elements of $S$ form a basis of $\mathcal{C}(M)$.
A cycle basis $B$ is odd if all its cycles are odd, and it is totally odd if moreover all the cycles of $B$ pairwise-intersect on an odd number of elements.

We now prove the main ingredient of our characterization. The fact that we have only circuits in the basis obtained is crucial.

Lemma 5.  Each connected non-bipartite binary matroid has an odd cycle basis formed by circuits only. It can be constructed in polynomial time.

Proof. Let $M$ be a connected and non-bipartite binary matroid. Let $M_p$ be the binary matroid obtained by adding successively an all-0 column and an all-1 line to a matrix representation of $M$, and let $p$ be the new element of $M_p$.
Lehman’s matroid-port theorem easily implies that each element of $M$ belongs to an odd circuit (see [8]). It follows straightforwardly that $M_p$ is a connected matroid.
Furthermore, a theorem of Coullard and Hellerstein states that for each connected matroid $N$ and every $e\in E(N)$, there exists an ear-decomposition of $N$ whose circuits all contain $e$ and which can be found in polynomial-time [3].

Now, consider an ear-decomposition $\left\{C_1,\ldots,C_k \right\}$ of $M_p$ such that all the $C_i$ contain $p$. It is easy to check that $\left\{C_1\setminus \left\{p\right\},\ldots,C_k\setminus \left\{p\right\}\right\}$ is an odd cycle basis of $M$, formed by circuits only. $\blacksquare$

The following statement is a direct consequence of the well-known fact that, for two subsets $S_1,S_2$ of a set $S$: the sum of the incidence vectors of $S_1$ and $S_2$ in $\mathbb{F}_2^{S}$ is the incidence vector of $S_1\Delta S_2$ and their product is the parity of $ |S_1\cap S_2|$ (with respect to the standard bilinear form on $\mathbb{F}_2^{S}$).

Lemma 6. If a binary matroid has a totally odd cycle basis, then all its odd cycles pairwise-intersect in an odd number of elements.

We can finally prove our characterization.

Theorem 7.  Let $M$ be a connected non-bipartite binary matroid. The following statements are equivalent.

  1. $\beta(M)\leq 1$,
  2. $M$ has a totally odd cycle basis formed by circuits only,
  3. each odd cycle basis of $M$ is totally odd.

Proof.  We first prove that $ (1)\Rightarrow (2) $. Since $\beta(M)\leq 1$ and as $M$ is connected and non-bipartite, Lemma 5 shows that $M$ has an odd cycle basis $B$ whose elements are circuits. Lemma 4 implies that the elements of $B$ pairwise-intersect in an odd number of elements. That is, $B$ is totally odd.

The implication $ (2)\Rightarrow (3) $ straightforwardly follows from Lemma 6.

We finally prove $ (3)\Rightarrow (1) $. Suppose that each odd cycle basis of $M$ is totally odd.  Since $M$ is connected and non-bipartite, Lemma 5 shows that $M$ has an odd cycle basis $B$. Since $B$ is totally odd, Lemma 6 implies that all odd cycles, and in particular all odd circuits of $M$, pairwise-intersect in an odd number of elements. By Lemma 4, we get $\beta(M)\leq 1$. $\blacksquare$

Now, testing whether a connected non-bipartite binary matroid $M$ satisfies $\beta(M)\leq 1$ can be done as follows: build an odd cycle basis $B$ of $M$ formed by circuits only (with Lemma 5), and compute the parities of the intersections of pairs of elements of $B$; there is only a polynomial number of such pairs, since $|B|=\dim \mathcal{C}(M)=|E(M)|-\mathsf{rk}(M)$.
If two elements of $B$ meet in an even number of elements, then Lemma 4 shows $\beta(M)\geq 2$ and a factor-critical restriction of $M$ with exactly two ears. Otherwise, $B$ is totally odd and Theorem 7 implies that $\beta(M)\leq 1$.

Clearly, a binary matroid $M$ satisfies $\beta(M)\leq 1$ if and only if every non-bipartite block of $M$ satisfies this condition. The blocks of $M$ can be easily found in polynomial-time, and hence we need only one more subroutine to finish the algorithm: deciding in polynomial-time whether a connected binary matroid is bipartite. This can be carried out using the following straightforward proposition, which generalizes the bipartiteness test of graphs.

Proposition 8.  Let $M$ be a connected binary matroid. The following statements are equivalent.

  1.  $M$ is bipartite,
  2. There exists a cycle basis of $M$ containing only even circuits,
  3. Each cycle basis of $M$ contains only even cycles.

Hence, testing bipartiteness only requires building a cycle basis formed by circuits (from the fundamental circuits of a basis of $M$, for example) and checking whether all its circuits are even. If so, the matroid is bipartite and otherwise we find an odd circuit.

Open Problems

$\beta$ can be used as a parameter to separate on, for properties of the matching polytope (for example, the integer decomposition property [1]).  The complexity of computing $\beta$ for graphs is apparently not known.

Clearly, the property $\beta(G)\geq k$ is in $\mathsf{NP}$ (as factor-criticality can be tested using a maximum-matching algorithm), but we do not know if it belongs to $\mathsf{co}$-$\mathsf{NP}$. Also, it is not clear whether the Parity Minor algorithm can be circumvented to check efficiently, for fixed $k\geq 3$, whether a graph $G$ satisfies $\beta(G)\geq k$.

For binary matroids, the situation is even less clear: results of Szegedy and Szegedy [9] show that testing whether a binary matroid is factor-critical can be done in randomized polynomial-time, but a deterministic algorithm is still missing, even for co-graphic matroids. Finally, it is not clear whether $\beta\leq 1$ can be decided efficiently for other interesting classes of matroids (our approach does not directly extend to anything else).


[1] Y. Benchetrit and A. Sebő. Ear-decompositions and the complexity of the matching polytope. arXiv preprint, 2015.

[2] H. Bruhn and O. Schaudt. Claw-free t-perfect graphs can be recognised in polynomial time. In Jon Lee and Jens Vygen, editors, IPCO, volume 8494 of LNCS, pages 404–415. 2014.

[3] C. Coullard and L. Hellerstein. Independence and port oracles for matroids, with an application to computational learning theory. Combinatorica, 16(2):189–208, 1996.

[4] J. Edmonds. Maximum matching and a polyhedron with 0, 1 vertices. J. of Res. the Nat. Bureau of Standards, 69 B:125–130, 1965.

[5] J. Edmonds and W. Pulleyblank. Facets of 1-matching polyhedra. In Hypergraph Seminar of Columbus, 1974.

[6] K. Kawarabayashi, B. Reed, and P. Wollan. The graph minor algorithm with parity conditions. In FOCS, 2011 IEEE 52nd Annual Symposium, pages 27–36. IEEE, 2011.

[7] L. Lovász. A note on factor-critical graphs. Studia Sci. Math. Hungar., 7:279–280, 1972.

[8] James Oxley. Matroid Theory. 1992.

[9] B. Szegedy and C. Szegedy. Symplectic spaces and ear-decomposition of matroids. Combinatorica, 26(3):353–377, 2006.