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.

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.

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

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.

Biased graphs and their matroids I

In this post I will define some matroids on graphs and give some examples. Such examples include graphic matroids, bicircular matroids and Dowling geometries. These matroids arise in different contexts and this led to a profusion (and confusion) of terminology. As a consequence, it’s really difficult to look up literature and see what has or hasn’t been done in the area. I’ll try to give a road map of the terminology and the main results. For now I’ll mostly give basic definitions and examples, leaving results for the next post.

1. Biased graphs

All graphs in this post are allowed parallel edges and loops. I’ll constantly talk about cycles of a graph: as is common in graph theory, by a cycle I mean a nonempty connected subgraph in which every vertex has degree two. In various contexts these are also called polygons, circuits, circles… I’ll stick to the word “cycle”. I’ll also abuse terminology and use the word “cycle” to mean the set of edges of a cycle. By a nonempty path I mean a path with at least one edge. Let’s start by defining our general universe.

Def. biased graph is a pair $(G,\mathcal{B})$ where $\mathcal{B}$ is a set of cycles of $G$ satisfying the following property:

Theta property: for every two cycles $C_1$ and $C_2$ in $\mathcal{B}$ intersecting in a nonempty path, the third cycle in $C_1 \cup C_2$ is also in $\mathcal{B}$.

The cycles in $\mathcal{B}$ are called balanced, and the other cycles are unbalanced. Two cycles sharing a non-empty path form a theta; a theta with all cycles unbalanced is an unbalanced theta.

The theta property guarantees that the matroids defined in the next two sections are indeed matroids. In particular, this property guarantees that the third circuit axiom is satisfied.

Here are some important examples of biased graphs (the importance will become clear in the next sections):

  • Biased graphs having only balanced cycles.
  • Biased graphs having only unbalanced cycles.
  • Signed graphs: consider a graph $G$ and a set of edges $F$ of $G$. Then we declare a cycle of $G$ to be balanced if it contains an even number of edges in $F$, and unbalanced otherwise. The resulting biased graph is called a signed graph. Balanced cycles in signed graphs are also called even or positive in the literature, while unbalanced cycles are also called odd or negative.
  • Group labelled graphs: consider a graph $G$ and a (say multiplicative) group $\Gamma$. Orient every edge of $G$ and assign to every oriented edge a value from $\Gamma$. This is how we obtain group labelled graphs. Group labelled graphs are also called gain graphs or voltage graphs. From a group labelled graph we obtain a biased graph as follows. Pick any cycle $C$ of $G$ and choose an orientation for $C$. Traverse $C$ with this orientation and multiply the values on the traversed edges, where backward edges will get the inverse value (so if $(u,v)$ is an oriented edge with value $g$ and this edge appears as $(v,u)$ in the orientation of $C$, the value for this edge will be $g^{-1}$). If the total value along the cycle is $1$, then the cycle is declared to be balanced, otherwise it is unbalanced. Changing the orientation of a cycle only changes the value to its inverse, so this assignment is well defined. It is easy to see that this assignment of balanced/unbalanced cycles satisfies the theta property, so we obtain a biased graph from our group labelled graph. I’ll often abuse terminology and call this biased graph a group labelled graph. Signed graphs are special cases of group labelled graphs, obtained by labelling the edges of a graph with elements from $GF(2)$ or, equivalently, from the multiplicative group of the ternary field. I set them aside because they are relevant on their own.

Following are the two main matroids arising from biased graphs. This general setting was first introduced by Zaslavsky (see [Zas89] and [Zas91]).

2. Frame matroids

Def. Given a biased graph $\Omega=(G,\mathcal{B})$, the frame matroid represented by $\Omega$ has as elements the edges of $G$ and as circuits the edge sets of subgraphs of the following forms (see the figure below): 

  1. A balanced cycle.
  2. Two unbalanced cycles sharing a vertex.
  3. Two vertex-disjoint unbalanced cycles together with a minimal path joining them.
  4. An unbalanced theta.

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

The circuits in 2. and 3. are called handcuffs (respectively tight and loose). 

Zaslavsky [Zas91] calls these matroids biased matroids, but recently the term “frame matroids” has become more common. Originally, a frame matroid was defined to be a matroid $M$ to which a basis $B$ could be added so that every element of $M$ is spanned by two elements in $B$. Zaslavsky showed that this definition is equivalent to the one coming from biased graphs. Consider a frame matroid $M$ represented by a biased graph $\Omega$. Form a new biased graph $\Omega’$ by adding an unbalanced loop to every vertex of $\Omega$ and call $B$ the set of these unbalanced loops. Then $B$ is a basis of the frame matroid $M’$ of $\Omega’$ and $M$ is a restriction of $M’$. Every loop of $\Omega$ is either balanced (hence spanned by the empty set), or unbalanced (so in parallel to the element of $B$ incident to the same vertex). Moreover, every edge of $\Omega$ that is not a loop is spanned by the two loops of $B$ at its endpoints.

It follows immediately from the definition that the independent sets of the frame matroid of $(G,\mathcal{B})$ are the set of edges $F$ such that every component induced by $F$ contains at most one cycle, which will have to be unbalanced.

Here are some examples of frame matroids, arising from different choices for the biased graph $\Omega=(G,\mathcal{B})$.

  • Graphic matroids: those are simply the frame matroids of biased graph with all cycles balanced. So frame matroids are a generalization of graphic matroids.
  • Bicircular matroids: these are the frame matroids of biased graphs with all cycles unbalanced. Bicircular matroids have been widely studied (more of this in the next post, else no reader will make it to the definition of lift matroids).
  • Signed-graphic matroids: these are frame matroids of signed graphs.
  • Dowling geometries: first defined by Dowling ([Dow73]) these are frame matroids of group labelled graphs.

If $\mathbb{F}$ is a field and $\Omega$ is a group labelled graph on the multiplicative group of $\mathbb{F}$, then the frame matroid of $\Omega$ is $\mathbb{F}$-representable. A matrix representation is obtained in the following way: let $e$ be an edge of $\Omega$ with label $g$. If $e$ is a balanced loop (i.e. a loop labelled $1$), then the column for $e$ is an all-zero column; if $e$ is an unbalanced loop incident to vertex $u$, then the column for $e$ has the $u$ entry equal to $g$ and zero everywhere else.  If $e=uv$ is not a loop and $e$ is oriented as (u,v), then the corresponding column for $e$ has a $1$ in position $u$, $-g$ in position $v$ and zero everywhere else. The proof that this is a representation of the frame matroid of $\Omega$ is not obvious, but appears, for example, in [Zas82].

The class of frame matroids (and the subclasses defined above) are minor-closed classes. The same is true for lift matroids, defined in the next section. However, this post is long enough without adding matroid operations for biased graphs. I’ll leave that for the next post as well.

3. Lift matroids

Def. Given a biased graph $\Omega=(G,\mathcal{B})$, the lift matroid represented by $\Omega$ has as elements the edges of $G$ and as circuits the edge sets of subgraphs of the following forms (see the figure below): 

  1. A balanced cycle.
  2. Two unbalanced cycles sharing a vertex.
  3. Two vertex-disjoint unbalanced cycles.
  4. An unbalanced theta.
Circuits of lift matroids are subdivisions of these graphs. Unlabelled cycles are unbalanced.

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

At a first glance lift matroids may look quite similar to frame matroids, but the differences between them emerge as soon as you start working with them. My rule of thumb is that frame matroids are easier to deal with than lift matroids, for some definition of “easier”. Having circuits that are not connected in the graph makes things a lot more complicated in a lot of cases.

From the definition we can easily see that the independent sets of the lift matroid of $(G,\mathcal{B})$ are the set of edges $F$ containing at most one cycle, which will have to be unbalanced.

Here are some examples of lift matroids, arising from different choices for the biased graph $\Omega=(G,\mathcal{B})$.

  • Graphic matroids: those are simply the lift matroids of biased graph with all cycles balanced. So lift matroids are also a generalization of graphic matroids.
  • Even cycle matroids: these are lift matroids of signed graphs. Even cycle matroids appear in alternative proofs of the list of excluded minors for graphic matroids ([Ger95]) and Seymour’s decomposition of regular matroids ([GG95]). In fact, any binary single element coextension of a graphic matroid is an even cycle matroid.
  • Spikes: let $G$ be obtained from the cycle on $n$ edges by doubling every edge. Declare every pair of parallel edges to form an unbalanced cycle. The other cycles of the graph may be declared to be balanced or unbalanced, as long as the theta property is satisfied. The lift matroid of the resulting biased graph is a spike with no tip. To obtain a spike with a tip, add an unbalanced loop to the graph.

If $\mathbb{F}$ is a field and $\Omega$ is a group labelled graph on the additive group of $\mathbb{F}$, then the frame matroid of $\Omega$ is $\mathbb{F}$-representable. A matrix representation is obtained in the following way: let $A$ be the vertex-edge oriented incidence matrix of $G$, with the orientation given in the group labelled graph. Add a row to $A$, where the entry for edge $e$ is the group label of $e$. The reader is invited to check that this is a valid matrix representation for the matroid.

In the next post I’ll survey some problems and results regarding these matroids.

References

[Dow73] T.A. Dowling, A class of geometric lattices based on finite groups, J. Combin. Theory Ser. B 14 (1973), 61–86.

[GG05] J. Geelen, A.M.H. Gerards, Regular matroid decomposition via signed graphs, J. Graph Theory 48 (2005), 74-84.

[Ger95] A.M.H. Gerards, On Tutte’s characterization of graphic matroids – a graphic proof, J. Graph Theory 20 (1995), 351-359.

[Zas82] T. Zaslavsky, Signed graphs, Discrete Applied Mathematics. 4 (1982), 47-74.

[Zas89] T. Zaslavsky, Biased graphs. I. Bias, balance, and gains, J. Combin. Theory Ser. B 47 (1989), 32-52.

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