Biased graphs and their matroids III

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.


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

[CGW93] C.R. Coullard, J.G. del Greco, and D.K. Wagner, Recognising a class of bicircular matroids, Discrete Appl. Math. 43 (1993), 197-215.

[G92] J.G. del Greco, Characterizing bias matroids, Discrete Math. 103 (1992), 153-159.

[M07] A. Musitelli, Recognition of generalized network matrices, Thèse EPFL n° 3938, École Polytechnique Fédérale de Lausanne (2007).

[S81] P.D. Seymour, Recognizing graphic matroids, Combinatorica 1 (1981), 75-78.

Non-matroidal matroids II

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.

Matroid Computation with Sage

October 7, 2013, marked a day that I have long been looking forward to: the release of Sage 5.12. This is the first version of Sage to support matroid theory!

This is the culmination of 2 1/2 years of work by Rudi Pendavingh and myself, with further help from Michael Welsh and Gordon Royle. In this post I’m going to demonstrate why you should be as excited as we are.

What is Sage?

From the Sage homepage:

Sage is a free open-source mathematics software system licensed under the GPL. It combines the power of many existing open-source packages into a common Python-based interface.
Mission: Creating a viable free open source alternative to Magma, Maple, Mathematica and Matlab.

There are several ways to interact with Sage:

  • Download and install it on your own computerThere are plenty of installation instructions available.
  • Use Sage online, through the Sage Notebook (runs version 5.11, without the matroids, and is down at the time of writing).
  • Use Sage online, through the SageMathCloud .

The third option is the fastest way to get started. To get an idea what Sage is capable of, look at the considerable documentation on the Sage website (including a tour, a tutorial, and much more).

Matroids in Sage

Matroid computation is not new. I have a list of previous efforts on these slides, and currently the most widely used software is Petr Hliněný’s MACEK. It is very powerful when it can already do what you want, but its functionality has its bounds, and it is very hard to teach it new tricks. Moreover, the original author no longer supports it.

To avoid ending up with the same fate, we wanted to tie our efforts in with other open-source software. GAP and Sage were the obvious candidates, with Sage winning out because 1) it includes GAP, and 2) Sage appeared to have a more suitable programming language.

Sage gives us a big developer community, regular updates that are tested on many different systems, a bug tracker, a question-and-answer site (be sure to add the “matroid” tag to your questions), a support newsgroup, and did I mention extensive documentation? Like the Matroid Theory part of the Reference Manual.

Some examples

The best way to get to work with the software is to “get your hands dirty”: install it, run it, and experiment, with the Reference Manual at hand. To get you going, I include a few examples of the capabilities below. Lines starting with “sage: ” or “….:” are input, and other lines are output. Anything from a # symbol to the end of the line is a comment. Let’s get started with a theorem:

Theorem. The Fano matroid, $F_7$, is a splitter for the class of matroids with no $U_{2,5}$-, $U_{3,5}$-, and $F_7^*$-minors.

Proof. By Seymour’s Splitter Theorem, we only need to inspect the single-element extensions and coextensions. And since $F_7$ is 3-connected, a single-element extension is 3-connected if and only if it is simple, and a single-element coextension is 3-connected if and only if it is cosimple.

sage: F7 = matroids.named_matroids.Fano()
sage: U25 = matroids.Uniform(2,5)
sage: U35 = matroids.Uniform(3,5)
sage: F7d = F7.dual()
sage: S = [U25, U35, F7d]
sage: Ext = F7.extensions()
sage: print [M for M in Ext if M.is_simple() and not 
....:            any(M.has_minor(N) for N in S)]
sage: CoExt = F7.coextensions()
sage: print [M for M in CoExt if M.is_cosimple() and not
....:            any(M.has_minor(N) for N in S)]

The two lines containing “[ ]” are output. They show that the lists we just constructed are empty, and the result is proved. $\square$

What happened here? In the first three lines, we assigned easy names to several built-in matroids. To get to the built-in matroids, you can type “matroids.” in Sage (note the dot), and hit the TAB key. Likewise, typing “matroids.named_matroids.” and hitting TAB will bring up the list of named matroids. For help, you can always type the name of an object or function followed by “?”, and hit the TAB key (note: in all these examples, do not hit ENTER at any point). For instance, typing


will print this section of the reference manual.

Each matroid has many methods associated with it. For instance, in the fourth line of our example, we compute the dual of $F_7$. And in the sixth line we compute the single-element extensions. Similar to before, to get a list of all methods you can type


and to get help for any method, type


Easy! The remaining lines show off some aspects of the programming language underlying Sage, Python. It has a very pleasant, mathematical syntax, with excellent support for working with lists and sets of objects.

Let’s look at some more examples. At this point, there is no built-in method to compute the lattice of flats of a matroid. But it is very straightforward to implement this (I spent more time hunting through the documentation on Sage’s posets than on writing the code):

sage: def lattice_of_flats(M):
....:     F = [] 
....:     for i in range(M.rank()+1): 
....:         F.extend([frozenset(X) for X in M.flats(i)]) 
....:     P = Poset((F, lambda x, y: x <= y)) 
....:     return P
sage: lattice_of_flats(F7).plot()

This will yield the following picture (which could be improved, of course):

Lattice of Flats of $F_7$

The first line of this code indicates that we are defining a function with one input, $M$. We use that “M.flats(i)” returns the set of all flats of a matroid $M$ rank $i$. By calling this method for each $i$, doing a little conversion on the output, and gluing the resulting list onto the end of $F$, we make $F$ equal to the list of all flats of $M$. Then we create a poset with a custom partial order, using that Python’s built-in “frozenset” type uses set inclusion as the interpretation of its “<=” operator. The “lambda” notation means we have an inline function taking two inputs, $x$ and $y$. This is another standard Python feature.

Finally, let’s verify for one example that the weight enumerator of a linear code is an evaluation of the Tutte polynomial:

For linear codes, the Weight Enumerator is an evaluation of the Tutte Polynomial of the corresponding matroid. Example:

sage: C = HammingCode(3, GF(3))
sage: x, y = var('x,y')
sage: p = C.weight_enumerator('xy')

sage: M = matroids.PG(2,3).dual() 
sage: t = M.tutte_polynomial(x,y) 
sage: u = t.substitute({x: 3*y/(x-y)+1, 
....:                   y: (x-y)/y+1   }) * y^3 * (x-y)^10 
sage: q = u.full_simplify()

sage: p - q

This example also shows Sage’s capabilities for symbolic math. The two variables $x$, $y$ are declared as symbols, and we can use them in polynomials and other functions.

Unfortunately, it also shows that Sage, because it is so big and has so many developers, does not always have a consistent interface. The syntax for the weight enumerator differs from that of the Tutte polynomial.

In conclusion

I didn’t show off the powerful isomorphism tests, the additional capabilities that linear matroids bring to the table, or how to define your own matroids. The latter is pretty easy. In most cases, just use the “Matroid” function, which accepts a variety of inputs:

sage: G = graphs.PetersenGraph()
sage: M = Matroid(G)
sage: M
Regular matroid of rank 9 on 15 elements with 2000 bases

I invite you to give Sage, and its matroid functionality in particular, a try! Make sure to let us know what you accomplish with the code, and what you would like to see added. As for me, together with Carolyn, Deb, and Dillon, I hope to finish a first research paper that uses Sage computations in the next few weeks.

edited on October 15 to reflect that SageMathCloud runs Sage 5.12 now.

Biased graphs and their matroids II

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.


[CGW91] C.R. Coullard, J.G. del Greco, and D.K. Wagner, Representations of bicircular matroids, Discrete Appl. Math. 32 (1991), 223-240.

[Neu02] N.A. Neudauer, Graph representations of a bicircular matroid, Discrete Appl. Math. 118 (2002), 249-262.

[Sli06] D. Slilaty, Bias matroids with unique graphical representations, Discrete Math. 306 (2006),1253-1256.

[Wag85] D.K. Wagner, Connectivity in bicircular matroids, J. Combin. Theory Ser. B 39 (1985), 308-324.

[Zas91] T. Zaslavsky, Biased graphs. II. The three matroids, J. Combin. Theory Ser. B 51 (1991), 46-72.