Here I am again, discussing frame and lift matroids. As in my previous post, I’ll denote by $FM(\Omega)$ and $LM(\Omega)$ respectively the frame and lift matroid of $\Omega$.

Following on Jim Geelen’s post on framework matroids, I’ll discuss recognition algorithms (or lack thereof) for some classes of lift and frame matroids. Jim’s post starts with Seymour’s beautiful theorem (in [S81], Theorem 1 in Jim’s post) which, for a given matroid $M$ and graph $G$, allows one to check whether $M=M(G)$ in polynomial time. In [G92], del Greco proved the following analogue to Seymour’s theorem for frame matroids. (In the next theorem, the star of a vertex $v$ is the set of edges incident with $v$ which are not balanced loops.)

Theorem 1: Let M be a matroid and let $\Omega=(G,\mathcal{C})$ be a biased graph where $G$ is connected and has at least two vertices. Then $M=FM(\Omega)$ if and only if the following hold:

1. the star of every vertex of $G$ is a union of cocircuits of $M$,
2. every vertex-disjoint union of unbalanced cycles of $\Omega$ is not a circuit of $M$,
3. no balanced cycle of $\Omega$ is properly contained in a circuit of $M$, and
4. $r(M)\leq r(FM(\Omega))$.

Unfortunately, this theorem doesn’t lead to a polynomial time algorithm for checking if $M=FM(\Omega)$, since the number of cycles in a graph may be exponential in the number of edges. This seems to support Conjectures 1 and 2 in Jim’s post.

One may hope that the recognition algorithm problem may be more tractable when turning our attention to specific classes of frame and lift matroids. Alas, even for the well behaved class of bicircular matroids, a polynomial-time recognition algorithm does not exist, unless $P=NP$. In fact it is shown in [CCW85] that it is NP-hard to determine whether a matroid $M$ is bicircular, even if $M$ is representable and a matrix representation is given. I couldn’t actually get hold of this reference, but a strengthening of this result may be found in [CGW93]. This paper also contains a polynomial-time algorithm to determine whether a matroid (given as an independence set oracle) is the bicircular matroid of a graph that belongs to a certain family of graphs.

Rudi Pendavingh and Stefan van Zwam have devised a recognition algorithm for a special class of signed-graphic matroids. This is the class of sixth-roots-of-unity graphic matroids, i.e. matroids representable by a sixth-roots-of-unity matrix with at most two nonzero entries per column. This corresponds to the class of signed graphs with no $-K_4$- and no $\pm K_3$-minor (where $-K_4$ is $K_4$ with all cycles unbalanced and $\pm K_3$ is a $K_3$ with all edges doubled, where every pair of parallel edges forms an unbalanced cycle). Musitelli’s algorithm for recognizing binet matrices  [M07] “almost” works for the whole class of signed-graphic matroids. That is, given a real matrix representation of a matroid $M$, Musitelli’s algorithm would recognize if $M$ is signed graphic as long as the columns of the matrix have already been scaled correctly, so only row operations are needed to get a matrix with two nonzeroes entries per column (these entries being $\pm 1$).

Aside from graphic matroids, I don’t know of any other polynomial-time recognition algorithm for classes of frame matroids. The situation is just as bad for lift matroids. This lack of algorithms suggests some obvious open problems:

Problem 1: find a polynomial-time algorithm that, given a binary matroid $M$, determines whether $M$ is an even cycle matroid.

Problem 2: find a polynomial-time algorithm that, given a ternary matroid $M$, determines whether $M$ is a signed-graphic matroid.

By “given a matroid $M$” I mean that $M$ is given as a rank oracle, or a matrix or pretty much in any reasonable form. Even though I believe these problems may be solved, I’m certainly not claiming that such algorithms would be easy to find, or to implement. Let me  elaborate a bit.

Since both these classes of matroids have a finite list of excluded minors (as implied by the Matroid Minor Project), one may think of using the excluded minors to solve Problems 1 and 2. However, finding the excluded minors for these classes seems an even harder problem than finding a recognition algorithm. What about a more direct approach?

Say that you want to decide whether a given matroid $M$ is an even cycle matroid. Maybe you’d like to decompose $M$ into smaller, 3-connected pieces (as for graphic or regular matroids). Here is the first difficulty: even cycle matroids are not even closed under 1-sums. It seems reasonable to restrict our attention to 3-connected matroids, since most algorithms for recognising graphic matroids work because a 3-connected graphic matroid has only one graphical representation. This is very much not the case for even cycle and signed-graphic matroids. Thus the need for some new ideas.

One approach could be the following:

1. take a small minor $N$ of $M$;
2. since $N$ is small we can check if it is an even cycle matroid and find all of its signed graph representations;
3. we can try to “grow” each of these graphical representations of $N$ into representations of $M$.

Step 3. is not hard, as long as you keep track of the deletions and contractions to go from $M$ to $N$. The problem is that this algorithm is not polynomial in the size of $M$. The reason is that in general we cannot bound the number of signed graph representations of an even cycle matroid, so starting from the few representations of $N$ we may grow into a lot of representations of an intermediate matroid. This happens when some signed graph representation of $N$ has blocking pairs, i.e. sets of two vertices intersecting every unbalanced cycle. More precisely, suppose that $N’$ is a one-element coextension of $N$ and $N$ has a signed-graph representation $\Omega$ with a blocking pair. Then it is possible that $(G,S)$ grows into signed graphs $\Omega_1$ and $\Omega_2$ which are both representations of $M$ (by “grows into” I mean that contracting the edge in $E(N’)-E(N)$ in any of these two signed graphs produces $\Omega$). When this happens, the two new signed graphs still have blocking pairs, so this doubling of representations may happen over and over again. Similar problems arise when trying this approach on signed-graphic matroids.

References

[CCW85] V. Chandru, C.R. Coullard, and D.K. Wagner, On the complexity of recognizing a class of generalized networks, Oper. Lett. 4 (1985), 75-78.

This post continues the discussion from my last post. I’m going to continue using the same notation: in particular, if $w$ is a permutation on the set $[n]=\{1,\ldots, n\}$, and $k\in \{0,\ldots, n\}$, then $\leq^{w}$ is a partial order on the $k$-element subsets of $[n]$. Gale’s Theorem states that if $\mathcal{B}$ is a collection of $k$-element subsets of $[n]$, then $\mathcal{B}$ is the collection of bases of a matroid if and only if, for every permutation, $w$, of $[n]$, there exists a subset $B\in\mathcal{B}$ such that $A\leq^{w} B$ for every $A\in \mathcal{B}$.

Symplectic matroids

Symplectic matroids can be seen as a generalization of ordinary matroids obtained by removing the full symmetric group that implicitly appears in Gale’s Theorem, and replacing it with another group, namely the hyperoctahedral group, $BC_{n}$. This group consists of permutations of the set $\{-n,-(n-1),\ldots,-1,1,\ldots,n-1,n\}$. Let $J$ denote this set. The permutation $w$ belongs $BC_{n}$ if and only if $w(-i)=-w(i)$, for every $i \in J$. We can see $BC_{n}$ as the group of symmetries of the hypercube in $\mathbb{R}^{n}$. The hypercube is the set of vectors $\mathbf{v}\in\mathbb{R}^{n}$ where every entry of $\mathbf{v}$ lies in the interval $[-1,1]$. The vertices of the hypercube are the vectors having every entry equal to $1$ or $-1$. Thus, for every $i\in\{1,\ldots, n\}$, $BC_{n}$ contains the reflection through the hyperplane consisting of all vectors with the $i$th entry equal to zero. We may also apply an arbitrary permutation of the entries. In fact, permutations of these two types generate the entire hyperoctahedral group. You might recognise that this means that $BC_{n}$ is the wreath product of the full symmetric group $\mathrm{Sym}(n)$ and the group of order two, $\mathrm{Sym}(2)$.

With the group definition out of the way, let’s define symplectic matroids. A subset of $J=\{-n,-(n-1),\ldots,-1,1,\ldots,n-1,n\}$ is admissible if it does not contain $\{i,-i\}$ for any $i\in \{1,\ldots,n\}$. If $A$ and $B$ are admissible $k$-element subsets, and $w\in BC_{n}$, then we write $A\leq^{w} B$ if, for every $i$, the $i$th element of $A$ appears no later than the $i$th element of $B$ in the sequence $w(-n),\ldots, w(-1),w(1),\ldots,w(n)$. Let $\mathcal{B}$ be a collection of admissible $k$-element subsets of $J$. If, for every permutation $w\in BC_{n}$, there is a subset $B\in\mathcal{B}$ such that $A\leq^{w}B$ for every $A\in \mathcal{B}$, then we call the set system $(J,\mathcal{B})$ a symplectic matroid.

Example 1. This example comes from an exercise in the book Coxeter Matroids. Let $\mathcal{B}$ be a family of bases of an ordinary matroid on the ground set $[n]$. If we consider $\mathcal{B}$ as a family of subsets of $J=\{-n,\ldots,1,1,\ldots, n\}$, then $(J,\mathcal{B})$ is a symplectic matroid. To see this, let $w$ be an arbitrary permutation in $BC_{n}$. Let $a_{1},\ldots, a_{s}$ be the members of $[n]$ that are fixed by $w$, and let $b_{1},\ldots, b_{t}$ be the members that are taken to their negation, where $a_{1} < a_{2} < \cdots < a_{s}$ and $b_{1}< b_{2} <\cdots < b_{t}$. Now let $w'$ be the permutation of $[n]$ that takes $1,\ldots, n$ to $b_{t},b_{t-1},\ldots, b_{1},a_{1},a_{2},\ldots, a_{s}$. By Gale's Theorem, there is a subset $B\in \mathcal{B}$ such that $A\leq^{w'} B$ for all $A\in \mathcal{B}$. It is not difficult to see that $A\leq^{w} B$ for all $A\in \mathcal{B}$, so $(J,\mathcal{B})$ is a symplectic matroid, as claimed. Example 2. Let $\mathcal{B}$ be the collection of bases of a matroid on the ground set $\{1,\ldots, n\}$. Add the elements $\{-n,\ldots, -1\}$ to this matroid in such a way that $-i$ is either a loop, or parallel to $i$, for every $i$. Let’s say that the resulting matroid is $M$. If $\mathcal{B}$ is the set of bases of $M$, then obviously every member of $\mathcal{B}$ is admissible, considered as a subset of $J$. Because every permutation in $BC_{n}$ is also a permutation in the symmetric group of $J$, Gale’s Theorem implies that $(J,\mathcal{B})$ is a symplectic matroid.

Actually, a converse to the previous example holds. If $(J,\mathcal{B})$ is a symplectic matroid, and $\mathcal{B}$ is also the family of bases of an ordinary matroid with ground set $J=\{-n,\ldots, -1,1,\ldots, n\}$, then every basis is admissible, which means that no basis can contain a set of the form $\{i,-i\}$. Thus every set $\{i,-i\}$ is dependent, so if a symplectic matroid is also an ordinary matroid, then it arises from that ordinary matroid in the way illustrated by Example 2.

Example 3. How about an example of a symplectic matroid that can not be interpreted as a matroid? Let $J$ be $\{-2,-1,1,2\}$, and let $\mathcal{B}$ be the admissible collection $\{\{1,-2\},\{2,-1\},\{-1,-2\}\}$. This is not the set of bases of a matroid; if it were, then $\{1,2\}$ and $\{1,-1\}$ would be parallel pairs, and $\{2,-1\}$ would be a basis. Next we check that $\mathcal{B}$ is the set of bases of a symplectic matroid. Let $w$ be an arbitrary permutation of $\{-2,-1,1,2\}$ from $BC_{2}$ and consider $\{w(1),w(2)\}$. It must be one of the sets $\{1,2\}$, $\{1,-2\}$, $\{2,-1\}$, or $\{-1,-2\}$. Since $A\leq^{w}\{w(1),w(2)\}$ for every $2$-element admissible subset $A$, we are done if $\{w(1),w(2)\}$ is in $\mathcal{B}$. Therefore let us assume that $\{w(1),w(2)\}=\{1,2\}$. Now $w(-1)=-w(1)$, so $\{w(-1),w(2)\}$ is in $\mathcal{B}$, and $A\leq^{w}\{w(-1),w(2)\}$ for every $A\in \mathcal{B}$. Therefore $(\{-2,-1,1,2\},\mathcal{B})$ is a symplectic matroid, as claimed.

The authors of Coxeter Matroids define a Lagrangian matroid to be a symplectic matroid on $\{-n,\ldots,-1,1,\ldots,n\}$ consisting of $n$-element subsets. So Example 3 gave an instance of a Lagrangian matroid. In that example, $\{-1,-2\}$ is an $n$-element admissible set. The intersections of $\{-1,2,\}$ with the members of $\mathcal{B}$ are $\{\}$, $\{-1,2\}$, and $\{-1\}$. If we complete this collection downwards, by including all subsets of those listed, then we generate the family of independent sets of a matroid. This is a particular case of a theorem that appears in Coxeter Matroids: if $\mathcal{B}$ is a collection of $n$-element admissible subsets, then the set system $(J,\mathcal{B})$ is a Lagrangian matroid if and only if, for every $n$-element admissible set, $T$, the downwards completion
\[\{I\subseteq J\mid \text{there exists}\ B\in \mathcal{B}\ \text{such that}\ I\subseteq T\cap B\}\]
is the family of independent subsets of an ordinary matroid. The proof of this equivalence only seems to appear in hard-to-find sources, so I’m not sure how complicated it is. It would be interesting to see a proof; I wonder if the equivalence holds when we relax the constraint that $(J, \mathcal{B})$ is a Lagrangian matroid, and instead ask only that it is a symplectic matroid.

Next time I’ll wrap up by talking about Coxeter matroids and their connections to algebraic geometry.

Following up on my first post on biased graph, this time I’m going to discuss some problems related to frame and lift matroids. Some of these problems have already been discussed in Jim Geelen’s intriguing post on framework matroids. Following Jim’s notation, I’ll denote by $FM(\Omega)$ and $LM(\Omega)$ respectively the frame and lift matroid of $\Omega$. As usual, $M(G)$ denotes the graphic matroid of a graph $G$.

I should first explain why the classes of frame and lift matroids are minor closed. Let’s define minor operations for biased graphs. Given a biased graph $\Omega=(G,\mathcal{B})$, we define the deletion of an edge $e$ as $\Omega \backslash e = (G \backslash e, \mathcal{B}’)$, where $\mathcal{B}’$ is the set of cycles in $\mathcal{B}$ not using $e$. Contraction is a little trickier to define. If $e$ is not a loop of $G$, then  $\Omega/e=(G/e,\mathcal{B}’)$, where $\mathcal{B}’$ is the set of cycles in $\{C-\{e\}:C \in \mathcal{B}\}$. If $e$ is a balanced loop of $\Omega$, then $\Omega/ e = \Omega \backslash e$. The fun part comes when $e$ is an unbalanced loop of $\Omega$ (at some vertex $v$): in this case $\Omega/ e=(G’,\mathcal{B}’)$, where $G’$ is obtained from $G$ by replacing every edge $vw$ with an unbalanced loop at $w$ (for $w \neq v$) and $\mathcal{B’}$ is obtained from $\mathcal{B}$ by adding all loops at $v$.

With this definition, $FM(\Omega) \backslash A / B=FM(\Omega \backslash A /B)$ (as proved in [Zas91]). Things are slightly different with lift matroids. Deletion still works, so $LM(\Omega) \backslash e= LM(\Omega \backslash e)$. For contractions we need to be a bit careful; if $e$ is not an unbalanced loop of $\Omega$, then $LM(\Omega) / e =LM(\Omega /e)$. However, if $e$ is an unbalanced loop then $LM(\Omega)/e = M(G\backslash e)$. These minor operations work so well that in fact all the subclasses of frame and lift matroids discussed in my last post are minor closed.

When dealing with minor closed classes of matroids it’s natural to ask whether the class has a finite list of excluded minors, and if so, what the excluded minors are. The amazing structure theorem for matroids representable over a finite field, by Geelen, Gerards and Whittle, implies that, for example, even cycle matroids and signed graphic matroids have a finite list of excluded minors (since these matroids are, respectively, binary and ternary). Outside of the implications of the Matroid Structure Theorem, almost nothing is known about excluded minors of classes of frame and lift matroids, not because of lack of trying, but because stepping “just outside” the class of graphic matroids everything becomes way more difficult. Still, since frame matroids and lift matroids arise from graphs I would put some money on the validity of the following conjectures.

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

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

These conjectures are extremely difficult to approach. The reason is that frame and lift matroids are not well behaved in terms of graphical representations. By that I mean that we may have very different-looking biased graphs $\Omega_1$ and $\Omega_2$ with, say, $FM(\Omega_1)=FM(\Omega_2)$. More on this later.

There is still hope for some other classes of frame and lift matroids. For example, Matt DeVos, Luis Goddyn, Dillon Mayhew and Gordon Royle proved the following.

Theorem 1: Any excluded minor for the class of bicircular matroids has less than 16 elements.

The proof of this theorem has yet to be published; the theorem should eventually include the complete list of excluded minors. So far there is a list of 27 excluded minors (of size up to 9 elements) and this list is believed to be complete, but there are still a few possible sizes to check. For size 11 and higher the number of matroids is just too big to be checked by a computer without some quite sophisticated ideas.

The proof of Theorem 1 was made possible by a complete description of the behaviour of graphs representing the same bicircular matroid. Basically, if $FM(G_1,\emptyset)=FM(G_2,\emptyset)$, then $G_1$ and $G_2$ are related by simple, very localised operations. See [Wag85], [CGW91] and [Neu02]. It seems natural that bicircular matroids should be better behaved than, say, signed graphic matroids. The reason is the following surprising result by Dan Slilaty in [Sli06].

Theorem 2: Let $\Omega$ be a 3-connected biased graph with no balanced loops. If $\Omega$ has three vertex-disjoint unbalanced cycles, at most one of which is a loop, then $\Omega$ is the only biased graph representation of $FM(\Omega)$.

Since bicircular matroids have only unbalanced cycles, either they have a unique representation or they have a very special structure. The equivalent of Theorem 2 for lift matroids is unfortunately false. For example, it is possible to construct even cycle matroids with two representations, each with as many disjoint unbalanced cycles as you like. However I do believe that lift matroids of biased graphs with no balanced cycles should be better behaved than the average lift matroid. Let $BL$ denote the class of lift matroids of biased graphs with no balanced cycles. This class is not minor closed, since contracting an unbalanced cycle in a lift matroid produces a graphic matroid. But the union of $BL$ and the class of graphic matroids is a minor closed class. Let $\bar{BL}$ denote this class. Then the analogue of Theorem 1 for lift matroids is the following.

Conjecture 3: The class $\bar{BL}$ has a finite list of excluded minors.

To solve Conjecture 3 we would need to solve the following.

Problem 1: Describe the relation between graphs $G_1$ and $G_2$ such that $LM(G_1, \emptyset)=LM(G_2,\emptyset)$.

I think that Problem 1 is more tractable than the analogous problems for other classes of lift matroids (like even cycle matroids). The reason may be stated in another conjecture.

Conjecture 4: There is a constant $c$ such that any $3$-connected matroid in $\bar{BL}$ has at most $c$ biased graph representations.

As far as I know, no one has worked on this class of matroids.

References