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.

References

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

4 thoughts on “Biased graphs and their matroids II

  1. That is a nice class and, as you say, Conjectures 3 and 4 certainly look tractable. Another natural class to consider along these lines is the union of the class of graphic matroids together with their truncations.

Leave a Reply

Your email address will not be published. Required fields are marked *