Three classes of graphical matroids

Guest post by Daryl Funk.

Biased graphs, and the frame and lifted-graphic (or simply, lift) matroids associated with them, have been discussed several times already in The Matroid Union blog. Irene Pivotto introduced them in a series of posts, Biased graphs and their matroids I, II, and III. In part II, Irene offered to put money on the truth of the following two conjectures.

Conjecture 1. The class of frame matroids has only a finite number of excluded minors.

Conjecture 2. The class of lift matroids has only a finite number of excluded minors.

If anyone took her up on her offer, you may now collect on your bet. In [CG17], Rong Chen and Jim Geelen exhibit an infinite family of excluded minors for the class of frame matroids, and another for the class of lift matroids. (It is unfair of me to pick on Irene like this — last I heard, bookies were giving 10:1 odds on). These families of excluded minors belong to a third class of matroids having graphical-type structure. So before discussing Rong and Jim’s counter-examples to Conjectures 1 and 2, we had better learn about this new class.

Quasi-graphic matroids

In his post, Graphical representations of matroids, Jim Geelen discussed a preliminary formulation for a new class of “graphical” matroids, which he there called framework matroids. The goal was to define a single minor-closed class that contains both the classes of frame and lift matroids, and to do so in a way such that (1) the new class maintains or captures the fundamental underlying graphic structure of these matroids, and (2) recognising membership in the new class is tractable — that is, there should be a polynomial-time algorithm to test membership via a rank oracle.

Jim’s goal has largely been realised, with his introduction, along with Bert Gerards and Geoff Whittle, of the class of quasi-graphic matroids, in [GGW17]. There should certainly be a post wholly devoted to this wonderful class of matroids soon. Here, I will tantalise you with just the definition and an example.

Let $M$ be a matroid. A graph $G$ is a framework for $M$ if

  1. $E(G)=E(M)$,
  2. for each component $H$ of $G$, $r_M(E(H)) \leq |V(H)|$,
  3. for each vertex $v$ of $G$, \[\operatorname{cl}_M(E(G-v)) \subseteq E(G-v) \cup \{e: e\ \text{is a loop incident to}\ v\},\] and
  4. for each circuit $C$ of $M$, the subgraph $G[C]$ induced by $C$ has at most two components.

A matroid is quasi-graphic if it has a framework. The definition is motivated by the following theorem of Paul Seymour, which yields a polynomial-time algorithm to test, via a rank oracle, if a given matroid is graphic. A star of a graph $G$ is the set of edges incident to a vertex $v \in V(G)$ each of whose other endpoint is in $V(G)-v$ (so while $G$ may have loops, loops are not included in any star); $c(G)$ denotes the number of components of $G$.

Theorem 1 [S81]. Let $M$ be a matroid, and let $G$ be a graph. Then $M$ is the cycle matroid of $G$ if and only if

  1. $E(G)=E(M)$,
  2. $r(M) \leq |V(G)| – c(G)$, and
  3. every star of $G$ is a union of cocircuits of $M$.

One can readily see that the requirements for a framework are inspired by the conditions of Theorem 1. One can also see that generalising these conditions to encompass a larger minor-closed class that includes all frame and lift matroids, is not quite straightforward (hopefully, we may learn more about this in a future post). In [GGW17], Jim, Bert, and Geoff show (among other things) that the class of quasi-graphic matroids has the following nice properties:

  • It is minor-closed.
  • If $(G,\mathcal B)$ is a biased graph, then $G$ is a framework for the lift matroid $LM(G,\mathcal B)$, and $G$ is a framework for the frame matroid $FM(G,\mathcal B)$; thus all lift and all frame matroids are quasi-graphic.
  • Given a 3-connected matroid $M$ and a graph $G$, one can check in polynomial time whether $G$ is a framework for $M$.

Jim, Bert, and Geoff conjecture in [GGW17] that there is a polynomial-time algorithm to test, via a rank oracle, if a given matroid is quasi-graphic. In contrast, Rong Chen and Geoff Whittle have recently shown that for each of the classes of frame and lift matroids, testing for membership in the class is intractable [CW16]. More on this in a moment. But first, let us try to get a bit of a feel for what a typical quasi-graphic matroid might look like.

Let us recall some required preliminary concepts. Every frame and every lift matroid may be represented by a biased graph $(G,\mathcal B)$ with $E(G)=E(M)$. For clarity’s sake, I’ll reserve the word circuit for matroids, and use the word cycle for a 2-regular connected subgraph. Recall how the circuits of frame and lift matroids appear in their biased graph representations: they are precisely the edge sets of subdivisions of certain biased subgraphs. Recall, a cycle $C$ of a graph whose edge set is a circuit of the matroid is balanced; otherwise $E(C)$ is independent and $C$ is said to be unbalanced. The figures in Sections 2 and 3 of Irene’s first post on biased graphs, reproduced here for your convenience, illustrate these biased subgraphs.

Circuits of frame matroids are subdivisions of these graphs. Unlabelled cycles are unbalanced.

Circuits of lift matroids are subdivisions of these graphs. Unlabelled cycles are unbalanced.

Let us call a subdivision of one of these five biased subgraphs (1), (2), (3F), (3L), (4), a circuit-subgraph. Note that the frame and lift matroids associated with a given biased graph differ on just one pair of these circuit-subgraphs, namely, (3F) and (3L) — a pair of vertex disjoint unbalanced cycles forms a circuit of the lift matroid, but is independent in the frame matroid. As Irene has explained in her previous posts, given a biased graph, we get a frame matroid by taking as circuits just circuit-subgraphs of the forms (1), (2), (3F), and (4), we get a lift matroid by taking as circuits just circuit-subgraphs of the forms (1), (2), (3L), and (4), and Tom Zaslavsky has shown that in fact all frame matroids, and all lift matroids, are obtained this way.

What about quasi-graphic matroids? Here is an example. The Vámos matroid (shown below left as a cube, in which the only 4-circuits are the 4 “sides” and just the one “diagonal” plane 2468) is neither a frame matroid, nor a lift matroid, but it is quasi-graphic, with the graph below right providing a framework. (Check that it satisfies the definition!)

Consider the 4-circuits of Vámos, and the subgraphs they form in the framework graph.
The four planes given by the front, back, and sides of the cube each form a circuit-subgraph of type (2), which is a circuit-subgraph for both frame and lift matroids. But together the circuit 2468 and the independent set 1357 prevent this graph from being either a frame or a lift representation for Vámos: circuit 2468 appears as a type (3L) circuit-subgraph, but so does the independent set 1357.

It turns out that (here I’m summarising results of [GGW17]), just as with biased graph representations of frame and lift matroids, the edge set of every cycle in a framework $G$ for a quasi-graphic matroid $M$ is either a circuit of $M$ or is independent in $M$. Further, declaring each cycle of $G$ to be balanced or unbalanced accordingly, just as for frame and lift matroids, yields a biased graph $(G,\mathcal B)$, where $\mathcal B$ denotes the collection of balanced cycles of $G$ (that is, the collection of balanced cycles satisfies the theta property: no theta subgraph contains exactly two balanced cycles). Moreover, every circuit of $M$ appears in $G$ as one of our five circuit-subgraphs (1), (2), (3F), (3L), (4). Conversely, the edge set of each circuit-subgraph of $G$ of one of the forms (1), (2), or (4) is a circuit of $M$, and each of the form of (3F) is either a circuit or contains a circuit of the form (3L).

Thus frameworks for matroids behave very much like biased graph representations for frame and lift matroids. Given a biased graph, taking $\{(1),(2),(3$F$),(4)\}$ as our circuit-subgraphs gives us a frame matroid, taking $\{(1),(2),(3$L$),(4)\}$ as our circuit-subgraphs gives us a lift matroid; and allowing all of $\{(1), (2), (3$F$), (3$L$), (4)\}$ as circuit-subgraphs gives the class of quasi-graphic matroids. This phenomenon is illustrated in the framework for the Vámos matroid above: 2468 is a (3L) circuit-subgraph, while each of the four circuits $1357 \cup e$ for $e \in \{2,4,6,8\}$ are (3F) circuit-subgraphs. Put another way, if a matroid $M$ has a framework having no circuit-subgraphs of type (3F), then we have a biased graph representation for $M$ as a lift matroid; if $M$ has a framework with no circuit-subgraphs of type (3L), then we have a biased graph representation for $M$ as a frame matroid; the Vámos matroid shows that (3F) and (3L) type circuit-subgraphs can coexist in a framework.

Recognition of frame, and of lift matroids, is intractable

As mentioned above, Rong and Geoff have shown that there can be no algorithm that can determine, via a rank oracle, in time polynomial in the size of the ground set, whether or not a given matroid is a frame matroid. They also show no such algorithm can exist for recognising lift matroids. They do so using two particular families of quasi-graphic matroids, one for frame and one for lift, arising from the same infinite family of framework graphs. More precisely, they prove the following two theorems.

Theorem 2 [CW16]. For any polynomial $p(\cdot)$, there is a frame matroid $M$ such that, for any collection $\mathcal A$ of subsets of $E(M)$ with $|\mathcal A| \leq p(|E(M)|)$, there is a quasi-graphic matroid $N$ that is not frame, such that $E(N)=E(M)$ and for each $A \in \mathcal A$, $r_k(A) = r_M(A)$.

Theorem 3 [CW16]. For any polynomial $p(\cdot)$, there is a lift matroid $M$ such that, for any collection $\mathcal A$ of subsets of $E(M)$ with $|\mathcal A| \leq p(|E(M)|)$, there is a quasi-graphic matroid $N$ that is not lift, such that $E(N)=E(M)$ and for each $A \in \mathcal A$, $r_k(A) = r_M(A)$.

The proofs go like this. Construct an infinite family of biased graphs $(W_k, \emptyset)$. Relaxation of a particular circuit-hyperplane of the lift matroid $LM(W_k,\emptyset)$ yields a quasi-graphic matroid that is no longer lift, but which agrees with $LM(W_k,\emptyset)$ on almost all subsets. Performing the reverse tweak to the frame matroid $FM(W_k, \emptyset)$ yields a quasi-graphic matroid that is no longer frame, but which agrees with $FM(W_k,\emptyset)$ on almost all subsets. The operation reverse to relaxation of a circuit-hyperplane is that of tightening a free basis. A free basis of a matroid is a basis $B$ such that $B \cup e$ is a circuit for each $e \in E(M)-B$. If $B$ is a free basis of $M$, then removing $B$ from the set of bases of $M$ results in a matroid, which we say is obtained by tightening $B$.

Here is the family of biased graphs. For each even integer $k \geq 4$, let $W_k$ be the graph consisting of 4 edge-disjoint $k$-cycles on vertices $u_1, \ldots, u_k, v_1, \ldots, v_k$: one cycle on the $u_i$’s, one cycle on the $v_i$’s (the vertex disjoint pair of blue cycles in the drawing of $W_6$ at below left), and two cycles (red and green in figure) alternating between $u_i$’s and $v_i$’s hitting every second vertex of the blue cycles as shown (below left).

Call a green edge and a red edge that cross in this drawing a crossing pair. Observe that $W_k$ has $k$ crossing pairs, and that for every collection $S$ of an even number of crossing pairs, there is a pair of disjoint cycles $C_S^1, C_S^2$ which use precisely these crossing pairs, each of which has length $k$, and which between them traverse all vertices of $W_k$. (See figure below: choosing the 2nd and 4th crossing pair defines the pair of cycles highlighted green and yellow.)

The graph $W_k$ has exponentially many collections of crossing pairs: there are $2^{k-1}$ collections consisting of an even number of crossing pairs. Hence $W_k$ has $2^{k-1}$ pairs of disjoint cycles, each pair having the property that together they contain all vertices of $W_k$. Each such pair of cycles is a circuit-hyperplane of the lift matroid $LM(W_k,\emptyset)$, and a free basis of the frame matroid $FM(W_k,\emptyset)$. Let $Z$ be the edge set of a pair of cycles obtained as above from a chosen set of crossing pairs of even cardinality. Let $M_L^Z$ be the matroid obtained from $LM(W_k,\emptyset)$ by relaxing the circuit-hyperplane $Z$. Let $M_F^Z$ be the matroid obtained from $FM(W_k,\emptyset)$ by tightening the free basis $Z$. To distinguish $LM(W_k,\emptyset)$ from $M_L^Z$, and to distinguish $FM(W_k,\emptyset)$ from $M_F^Z$, requires checking the rank of $2^{k-1}$ subsets. This, of course, will be greater than any polynomial in $|E(W_k)|$ for sufficiently large $k$. Since $W_k$ remains a framework for both $M_L^Z$ and $M_F^Z$, both these matroids are quasi-graphic. The proofs are completed by showing that $M_L^Z$ is not a lift matroid, and that $M_F^Z$ is not frame (which takes just another couple of pages in Rong and Geoff’s paper).

The Chen-Whittle graph’s usefulness does not stop here.

Excluded minors

To disprove Conjectures 1 and 2, Rong and Jim exhibit an infinite family of quasi-graphic matroids, each of which is minor-minimally not frame, and another infinite family of quasi-graphic matroids, each of which is minor-minimally not lifted-graphic. As in Rong and Geoff’s proofs of Theorems 2 and 3, these two families share a common framework. In fact, they again use the Chen-Whittle graphs!

Here is Rong and Jim’s construction. For each odd positive integer $k \geq 5$, let $G_k$ be the graph obtained from the Chen-Whittle graph $W_{k+1}$ defined above by deleting exactly one crossing pair (at right in figure above is shown the Chen-Geelen graph $G_5$). It is convenient to describe the collection of balanced cycles of $G_k$ by group-labelling (group-labelled graphs are described in Irene’s first post on biased graphs, Section 1, 4th bullet point).

For each odd positive integer $k \geq 5$, we obtain a quasi-graphic excluded minor for the class of frame matroids, with framework $G_k$, as follows. Label $G_k$ using the multiplicative group of $\mathbb R$. Referring to the drawing of $G_5$ above: orient each of $e_1$ and $e_2$ “up” from the bottom vertex to the top vertex of the vertical path making up its “side” of the crossing ladder, and assign to both $e_1$ and $e_2$ the label 2. Orient all remaining edges arbitrarily, and assign each label 1. Let $\mathcal B_k$ be the collection of balanced cycles defined by this labelling (that is, ${\mathcal B}_k$ consists of those cycles $C$ for which the product of edge labels, taken while traversing $C$ in a cyclic order, is 1, where we take the multiplicative inverse of each label whose edge is traversed against its orientation). Let $P$ be the paths forming the two vertical sides of the ladder, so $P \cup \{e_1, e_2\}$ is the pair of blue disjoint cycles in the figure, and let $Q$ be the union of the red and green paths. Then $P \cup \{e_1, e_2\}$ and $Q \cup \{e_1, e_2\}$ are free bases of $FM(G_k, \mathcal B_k)$. Let $M_k^F$ be the matroid obtained from $FM(G_k, \mathcal B_k)$ by tightening $P \cup \{e_1, e_2\}$ and $Q \cup \{e_1, e_2\}$. Then $M_k^F/\{e_1, e_2\}$, while quasi-graphic (with framework $G_k/\{e_1,e_2\}$), is an excluded minor for the class of frame matroids.

An excluded minor for the class of lift matroids is obtained in a similar manner. Again orient $e_1$ and $e_2$ up from the bottom to the top vertex of the vertical paths of the ladder. This time, label $G_k$ using elements of the additive group of integers, labelling $e_1$ with $1$, $e_2$ by $-1$, and all remaining edges with $0$. Let $\mathcal B_k$ be the collection of balanced cycles defined by this labelling (that is, $C \in \mathcal B_k$ if and only if when traversing $C$ in a chosen cyclic direction, taking the sum of the labels on its edges, subtracting the label on each edge traversed against its orientation, yields $0$). Let $P$ and $Q$ be as before. Then $P \cup \{e_1,e_2\}$ and $Q \cup \{e_1, e_2\}$ are circuit-hyperplanes of $LM(G_k, \mathcal B_k)$. Let $M_k^L$ be the matroid obtained from $LM(G_k, \mathcal B_k)$ by relaxing $P \cup \{e_1, e_2\}$ and $Q \cup \{e_1, e_2\}$. Then $M_k^L / \{e_1, e_2\}$, while quasi-graphic, is an excluded minor for the class of lift matroids.

Rong and Jim make the following conjecture.

Conjecture 3 [CG17]. The class of quasi-graphic matroids has only a finite number of excluded minors.

Dillon Mayhew and I have recently proved the following three theorems.

Theorem 4 [FM17]. The class of frame matroids has only a finite number of excluded minors of any fixed rank.

Theorem 5 [FM17]. The class of lift matroids has only a finite number of excluded minors of any fixed rank.

Theorem 6 [FM17]. The class of quasi-graphic matroids has only a finite number of excluded minors of any fixed rank.

Rong and Jim’s counterexamples to Conjecture 1 and 2 are both infinite families of excluded minors of ever increasing, arbitrarily large rank (if $G$ is a connected framework for a non-graphic quasi-graphic matroid $M$, then the rank of $M$ is $|V(G)|$). Theorems 4 and 5 say that any such collections of excluded minors for these classes must have this property. Theorem 6 provides evidence toward Conjecture 3 — though no more evidence than Theorems 4 and 5, respectively, provide toward Conjectures 1 and 2! What is perhaps interesting about Theorems 4, 5, and 6 is that — in contrast to what we’ve just seen in the results of Rong, Geoff, and Jim above — the same strategy works for all three classes. Dillon and I set out to prove Theorem 4, and having done so, realised that essentially the same proof also gives us Theorems 5 and 6. Perhaps we can take a look at this strategy in a subsequent post.

References

[CG17] Rong Chen and Jim Geelen. Infinitly many excluded minors for frame matroids and for lifted-graphic matroids. arXiv:1703.04857

[CW16] Rong Chen and Geoff Whittle. On recognising frame and lifted-graphic matroids. arXiv:1601.01791

[FM17] Daryl Funk and Dillon Mayhew. On excluded minors for classes of graphical matroids. Forthcoming.

[GGW17] Jim Geelen, Bert Gerards, and Geoff Whittle. Quasi-graphic matroids. arXiv:1512.03005

[S81] Paul Seymour. Recognizing graphic matroids. Combinatorica (1981). MR602418

A Taste of Tangles

Guest post by Tara Fife

This semester, I’ve been doing a reading course with Stefan van Zwam, the bulk of which involved reading interesting papers about tangles. This post highlights some of my favorite ideas so far. We start with an example that essentially comes from Reinhard Diestel and Geoff Whittle’s paper “Tangles and the Mona Lisa” [1]. The goal is to illustrate the intuition behind some of the definitions related to tangles. Precise definitions for connectivity systems and tangles as related to pictures can be found in [1]. Here is a picture of my brother Daniel and me on a ferry outside Seattle.

MeAndDan

If this picture were printed out and cut into two pieces, then we could sometimes decide that one piece was less important than the other. For instance, if we cut along the red lines below, it is clear that the center piece, while missing some of the beautiful scenery, is the important part of the picture from the perspective of capturing the human subjects of the picture.

MeAndDan2

If, however, we cut the picture with a squiggly cut, as below, then perhaps neither piece is unimportant. A connectivity system $K=(E(K),\lambda_K)$ consists of a finite set, $E(K)$, together with a connectivity function $\lambda _K:2^{E(K)}\rightarrow\mathbb{R}$ that gives us a way to rank the size of cuts. As such, we expect $\lambda_K(X)=\lambda_K(E(K)-X)$, for all subsets $X$ of $E(K)$. That is, we expect $\lambda_K$ to be symmetric. We also want our connectivity function to be submodular, that is, $\lambda_K(X)+\lambda_K(Y)\geq \lambda_K(X\cap Y)+\lambda_K(X\cup Y)$ for all subsets $X$ and $Y$ of $E(K)$. Any function which is symmetric and submodular is a connectivity function.

MeAndDan5

If $\lambda_1$ and $\lambda_2$ are connectivity functions on the same set, then it is straightforward to check that so is $\lambda_1+\lambda_2$ and, for a positive constant $c$, both $c\cdot\lambda_1$and $\lambda_1+c$. If $K=(E,\lambda_K)$ and $K’=(E,\lambda_{K’})$ are connectivity systems, then we say that $K’$ is a tie breaker if $\lambda_{K’}(X)\leq \lambda_{K’}(Y)$ whenever $\lambda_K(X)\leq \lambda_K(Y)$ and $\lambda_{K’}(X)\not=\lambda_{K’}(Y)$ unless $X=Y$ or $X=E-Y$. Geelen, Gerards, and Whittle’s “Tangles, tree-decompositions and grids in matroids” [2] proves the following.

Lemma 1 All connectivity functions have tie breakers.

Proof. Let $K=(E,\lambda)$ be a connectivity function. We can assume that $E=\{1, 2, \ldots, n\}$ Define $\lambda_L$ by $\lambda_L(X)=\sum_{i\in X}2^i$ for $X\subseteq {1, 2,\ldots, n-1}$, and $\lambda(X)=\lambda(E-X)$ for $X$ containing $n$. We need to show that $\lambda_L$ is submodular. If $X,Y\subseteq\{1, 2,\ldots, n-1\}$, then
\begin{align*}
\lambda(X)+\lambda(Y) & =\sum_{i\in X}2^i+\sum_{i\in Y}2^i=\sum_{i\in X\cap Y}2^i+\sum_{i\in X-Y}2^i+\sum_{i\in Y}2^i=\sum_{i\in X\cap Y}2^i+\sum_{i\in X\cup Y}2^i\\
& =\lambda_L(X\cap Y)+\lambda_L(X\cup Y).
\end{align*}

If $X\subseteq\{1,2,\ldots,n-1\}$ and $n\in Y$, then
\begin{align*}
\lambda(X)+\lambda(Y) & =\sum_{i\in X}2^i+\sum_{i\not\in Y}2^i=\sum_{i\in X\cap Y}2^i+\sum_{i\in X-Y}2^i+\sum_{i\not\in Y\cup X}2^i+\sum_{i\not\in X-Y}2^i\\
& \geq\sum_{i\in X\cap Y}2^i+\sum_{i\not\in X\cap Y}2^i=\lambda_L(X\cap Y)+\lambda_L(X\cup Y).
\end{align*}

If $n\in X$ and $n\in Y$, then
\begin{align*}
\lambda_L(X)+\lambda_L(Y) & =\lambda_L(E-X)+\lambda_L(E-Y)\\
& =\lambda_L((E-X)\cap(E-Y))+\lambda_L((E-X)\cup(E-Y))\\
& =\lambda_L(E-(X\cup Y))+\lambda_L(E-(X\cap Y)).
\end{align*}

Thus $\lambda_L$ is a connectivity function. Now let $\lambda'(X)=2^n\cdot\lambda(X)+\lambda_L(X)$. It is straightforward to check that $K’=(E,\lambda’)$ is a tie breaker for $K$.

$\square$

A tangle can be thought of as a collection $\mathcal{T}$ of less important (or small ) pieces. So far, we expect that the tangle should only make decisions about relatively simple cuts, and that the tangle should make a decision for all of the simple cuts. If we decide that the two pieces cut out of the picture below are both small, then we don’t want the part of the picture that is left to be contained in a small piece. More precisely, if $K$ is a connectivity system, then a collection $\mathcal{T}$ is a tangle of order $\theta$ in $K$ if

(T1)
$\lambda_K(A) < \theta$, for all $A \in \mathcal{T}$.
(T2)
For each separation $(A,B)$ of order less that $\theta$, either $A\in\mathcal{T}$ or $B\in\mathcal{T}$.
(T3)
If $A,B,C\in\mathcal{T}$, then $A\cup B\cup C \not=E(K)$.
(T4)
$E(K)-e$ is not in $\mathcal{T}$, for each $e\in E(K)$.

MeAndDan6

For some types of cuts, there might be different opinions about which part is less important. For instance, in the following picture, the matroid community would probably say that the part containing my brother was slightly less important, because the other half contains someone who at least knows the definition of a matroid, while my brother’s company would probably say that the part that contains me is slightly less important.

MeAndDan3

My mother would not consider either part unimportant, as we are both somewhat meaningful to her. Since the tangle induced by the opinion of the matroid community disagrees with the one induced by the opinion of Daniel’s company about which half of the separation above is less important, that separation is called a distinguishing separation. Since the tangle induced by my mother’s opinions (that is, a piece is only unimportant if it avoids me and avoids Daniel) is a subset of the matroid community tangle (where a piece is unimportant if it avoids me) and a subset of the company tangle (where a piece in unimportant if it avoids Daniel), it is called a truncation of either of them. That is, $\mathcal{T}’$ is a truncation of $\mathcal{T}$ if $\mathcal{T}’\subseteq\mathcal{T}$. If a tangle is not a proper truncation of another tangle, then it is a maximal tangle.

The above definition of a connectivity function includes the usual connectivity function of a matroid $M$, namely, $\lambda(X)=r(X)+r(E-X)-r(M)$. One of the main results of [2] gives us information about maximal tangles in a matroid. Before we state the theorem, we need to introduce a bit more notation. If $K=(E,\lambda)$ is a connectivity system, $T$ is a tree, and $\mathcal{P}$ a function from $E$ to $V(T)$, then we say that $(T,\mathcal{P})$ is a tree decomposition of $E$. For a subset $X$ of $V(T)$, we define $\mathcal{P}(X)=\{e:P(e)\in X\}$, and for a subtree $T’$ of $T$, we define $\mathcal{P}(T’)=\mathcal{P}(V(T’))$. We say that a separation $(A,B)$ of $K$ is displayed by $(T,\mathcal{P})$ if $A=\mathcal{P}(T’)$ for some subtree $T’$ of $V(T)$ obtained by deleting an edge of $T$ and letting $T’$ be one of the resulting connected components.The order if a separation $(A,B)$ is $\lambda(A)=\lambda(B)$.

Theorem 1

Let $K$ be a connectivity system, and let $\mathcal{T}_1,\mathcal{T}_2,\ldots,\mathcal{T}_n$ be maximal tangles in $K$. Then there is a tree decomposition $(T,\mathcal{P})$ of $E(K)$ with $V(T)=[n]$ such that the following hold.

  1. For each $i\in V(T)$ and $e\in E(T)$, if $T’$ is the component of $T-e$ containing $i$, then $\mathcal{P}(T’)$ is not in $\mathcal{T}_i$.
  2. For each pair of distinct vertices $i$ and $j$ of $T$, there is a minimum-order distinguishing separation for $\mathcal{T}_i$ and $\mathcal{T}_j$ displayed by $T$.

Before we sketch a proof of this theorem, we give an example that illustrates the statement of the theorem.

Alien2Consider the matroid, $M=([12],\mathcal{I})$ illustrated above. We first need to determine what the maximal tangles are. Let $S_1=\{9,10\}$, $S_2=\{11,12\}$, and $S_3=[8]$. We will show that an order-1 tangle of $M$ has the form the union of $\{S_i,S_j,(S_i\cup S_j)\}$ together with the set of singletons, where $i$ and $j$ are distinct members of $\{1,2,3\}$.

Let $\mathcal{T}$ be an order-1 tangle of $M$. The sets with connectivity 1 consist of the 12 singletons, their complements, and $S_1$, $S_2$, $S_3$, and their complements. By (T3), at most two of $S_1, S_2, S_3$ are in $\mathcal{T}$. Assume that $\{i,j,k\}=\{1,2,3\}$, and that $S_k$ is not in $\mathcal{T}$. Since $(S_i\cup S_j,S_k)$ is an order-1 separation of $M$, by (T2) $S_i\cup S_j$ is in $\mathcal{T}$. By (T3) (and the fact that there are at least 3 elements of $\mathcal{T}$), we get that neither $S_j\cup S_k$ nor $S_i\cup S_k$ is in $\mathcal{T}$, so by (T2), $S_i$ and $S_j$ are in $\mathcal{T}$.
Since singletons must all be in every tangle of order at least 1, the result follows.

The sets with connectivity 2 either contain $\{1,2,3,4\}$ and avoid $\{5,6,7,8\}$ or contain $\{5,6,7,8\}$ and avoid $\{1,2,3,4\}$. Arguing as above, we get that that the order-2 tangles of $M$ are $\{X:\lambda(X)\leq 2 \text{ and } S\not\subseteq X\}$ for $S\in\{\{1,2,3,4\}, \{5,6,7,8\}\}$. We note that the order-1 tangle where $\{S_i,S_j\}=\{\{1,2,3,4\},\{5,6,7,8\}\}$ is a truncation of both of the order-2 tangles, and that the other order-1 tangles can be represented as $\{X:\lambda(X)\leq 1 \text{ and } \{1,2, 3, 4\}\not\subseteq X\}$ and $\{X:\lambda(X)\leq 1 \text{ and } \{5,6, 7, 8\}\not\subseteq X\}$. Since there are no separations of order-3 or more in $M$, the four maximal tangles of $M$ are $\mathcal{T}_S=\{X:\lambda(X)\leq \lambda(S) \text{ and } S\not\subseteq X\}$, for $S\in\{\{1,2,3,4\},\{5,6,7,8\},\{9,10\},\{11,12\}\}$. For $S \in \{\{1,2,3,4\}, \{9,10\},\{11,12\}\}$, a minimum-order distinguishing separation for $\mathcal{T}_S$ and $\mathcal{T}_{S’}$ is $(S,[12]-S)$, which is displayed by the tree, $T$, below.

AlienTree1The above argument showing that if $S_i\cup S_j$ is in $\mathcal{T}$, then each of $S_i$ and $S_j$ are in $\mathcal{T}$, can be generalized to show the following.

Lemma 2

If $A$ is in a tangle, $\mathcal{T}$ of $K$ of order $\theta$, and $B\subseteq A$ with $\lambda_K(B)\leq\theta$, then $B\in\mathcal{T}$.

To prove Theorem 1, we actually prove the following slightly stronger result also from [2].

Theorem 2

Let $K$ be a connectivity system, and let $\mathcal{T}_1,\mathcal{T}_2,\ldots,\mathcal{T}_n$ be tangles in $K$, none a truncation of another. Then there is a tree decomposition $(T,\mathcal{P})$ of $E(K)$ with $V(T)=[n]$ such that the following hold.

  1. For each $i\in V(T)$ and $e\in E(T)$, if $T’$ is the component of $T-e$ containing $i$, then $\mathcal{P}(T’)$ is not in $\mathcal{T}_i$.
  2. For each pair of distinct vertices $i$ and $j$ of $T$, there is a minimum-order distinguishing separation for $\mathcal{T}_i$ and $\mathcal{T}_j$ displayed by $T$.

Proof Sketch
If $K$ is a connectivity system and $K’$ is a tie breaker for $K$, then it is easy to see that a tangle $\mathcal{T}$ of $K$ is also a tangle of $K’$, so it is safe to assume that $K$ is its own tie breaker.

Since $K$ is its own tie breaker, for each distinct $i$ and $j$ in $[n]$, there is a minimum-order separation $(X_{ij},Y_{ij})$ of $K$ distinguishing $\mathcal{T}_i$ and $\mathcal{T}_j$, where $X_{ij}\in\mathcal{T}_i$. Using some well known results (whose statements require terminology which we haven’t introduced), it can be show that there is a tree decomposition $(T,\mathcal{P})$ of $E(K)$ such that each separation $(X_{ij},Y_{ij})$ is displayed by $(T,\mathcal{P})$, that these are the only separations displayed by $(T,\mathcal{P})$, and that each edge of $T$ displays a proper and distinct separation. It remains to show that there is a bijection from $\{\mathcal{T}_1,\ldots,\mathcal{T}_n\}$ to the vertices of $T$ satisfying the conclusion of Theorem 2.

For $i\in[n]$, let $\chi_i$ be the set of subsets $X$ of $V(T)$ such that $E(K)-\mathcal{P}[X]\in\mathcal{T}_i$ and such that $(E(K)-\mathcal{P}[X],\mathcal{P}[X])$ is displayed by $(T,\mathcal{P})$. Each member of $\chi_i$ induces a sub-tree of $T$, and, by (T3), each two members of $\chi_i$ intersect, so the intersection of the members of $\chi_i$ is non-empty. Call this intersection $V_i$. Each edge of $T$ that leaves $V_i$ displays a separation $(A,B)$ with $\mathcal{P}[V_i]\subseteq A$ and $B\in\mathcal{T}_i$. The proof concludes by showing that the $V_i$’s partition the vertices of $T$ into singletons, since this shows that $|V(T)|=n$, and since vertices in $V_i$ satisfy the condition (1) of the theorem.

For each $i\not=j$, the set $\mathcal(V_i)$ is in $Y_{ij}$ and the set $\mathcal(V_j)$ is in $Y_{ji}=X_{ij}$, so the sets $V_1, \ldots, V_n$ are disjoint.

Suppose that $w\in V_i$. We need to show that $\{w\}=V_i$. Choose the edge $e$ incident with $w$ that displays the separation $(X_{ij},Y_{ij})$ of strictly largest order. Since we are assuming that $K$ is its own tie breaker, there is a strictly largest order. Now, each of the other edges incident with $w$ displays a separation of order less than the order displayed by $e$, and hence, less than the orders of $\mathcal{T}_i$ and $\mathcal{T}_j$. Then, by the definition of $(X_{ij},Y_{ij})$, none of these separations distinguish $\mathcal{T}_i$ and $\mathcal{T}_j$. By the definition of $V_i$ and the fact that $X_{ij}$ is in $\mathcal{T}_i$, we know that $\mathcal{P}(w)$ is not a subset of $X_{ij}$ so it is a subset of $Y_{ij}$. Then by Lemma 2, for each of the separations induced by edges other than $e$ incident to $w$, the set not containing $\mathcal{P}(w)$ is in $\mathcal{T}_j$, and hence it is in $\mathcal{T_i}$. Thus, $V_i=\{w\}$.
$\square$

The complete details of the last proof can be found in [2] along with a corollary which bounds the number of maximal tangles.

As hinted at in the example, tangles can end up pointing to “highly” connected regions of the matroid. This is useful in structure theory because the highly connected regions usually contain the structure that we care about, and a tangle can be used to identify where deletions and contractions can be made while preserving the structure. This idea is utilized, for example, in [3, 4]. Tangles in general grew out of a definition for tangles of graphs, which were used to prove that finite graphs are well quasi ordered.

References

[1] R. Diestel, and G. Whittle, Tangles and the Mona Lisa, arXiv:1603.06652v2 [math.CO]

[2] J. Geelen, B. Gerards, and G. Whittle, Tangles, tree-decompositions and grids in matroids, J. Combin. Theory Ser. B 99 (2009) 657-667

[3] J. Geelen, and S. van Zwam, Matroid 3-connectivity and branch width, arXiv:1107.3914v2 [math.CO]

[4] P. Nelson, and S. van Zwam, Matroids representable over fields with a common subfield, arXiv:1401.7040v1 [math.CO]

[5] N. Robertson and P. D. Seymour, Graph minors, X. Obstructions to tree-decomposition. J. Combin. Theory Ser. B, 52(2):153-190, 1991.

$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’$,
\begin{equation*}
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|
\end{equation*}
and
\begin{equation*}
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|.
\end{equation*}
From these equations and inclusion/exclusion, it follows that
\begin{equation*}
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).
\end{equation*}

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$,
\begin{equation*}
r(\cap\mathcal{A})\leq \sum_{\mathcal{F}\subseteq \mathcal{A}} (-1)^{|\mathcal{F}|+1} r(\cup\mathcal{F}).
\end{equation*}

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$,
\begin{equation}
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)
\end{equation}

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.
$$\{\mathbf{a},\mathbf{c},u,v\}
\quad\{\mathbf{a},\mathbf{c},s,t\} \quad
\{\mathbf{b},\mathbf{d},s,v\}\quad
\{\mathbf{b},\mathbf{d},t,u\}$$
$$\{a,b,\mathbf{t},\mathbf{v}\}
\quad\{c,d,\mathbf{t},\mathbf{v}\}\quad
\{a,d,\mathbf{s},\mathbf{u}\}\quad
\{b,c,\mathbf{s},\mathbf{u}\}$$

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.

References

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

image003

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.