Guest post by Jim Geelen.
$\newcommand{\del}{\,\backslash\,}$ $\newcommand{\con}{/}$ $\newcommand{\cC}{\mathcal{C}}$ $\newcommand{\bF}{\mathbb{F}}$
Anyone who has given significant consideration to the classes of frame matroids and lifted graphic matroids will have been struck by their similarities. The point of this posting is that these classes can be unified in a way that might have significant algorithmic implications. We also prove an amazing result (Theorem 3) concerning representations of matroids in the unified class.
Graphic matroids
The class of graphic matroids is very well understood; for example, the set of excluded minors is known and there is a polynomial-time algorithm for recognizing whether a matroid, given by its rank oracle, is graphic.
There are two key parts to the recognition algorithm. First one needs an algorithm for testing whether a given binary matroid is graphic; see, for example, [BC80]. Second one needs to check, for a given matroid $M$ and graph $G$, whether $M=M(G)$. This second part is solved by the following beautiful result due to Seymour [Sey81].
Theorem 1: Let $M$ be a matroid and let $G$ be a loopless $2$-connected graph with $E(G)=E(M)$. Then $M=M(G)$ if and only if $r(M)\le |V(G)|-1$ and, for each vertex $v$ of $G$, the set of edges incident with $v$ in $G$ forms a cocircuit of $M$.
Bias graphs
In the following three short sections, I will review the frame matroid and the lift matroid associated with a bias graph. These objects were introduced by Zaslavsky [Zas91] and were discussed in Irene Pivotto’s post on August 26.
Let $\cC$ be a set of circuits in a graph $G$. A theta in $G$ is loopless $2$-connected subgraph $H$ with $|E(H)| = |V(H)|+1$. Thus, a theta has two special vertices connected by three internally-disjoint paths, and such graphs have exactly three circuits. We say that $\mathcal C$ has the theta-property if there is no theta in $G$ having exactly two of its three circuits in $\cC$. The pair $(G,\cC)$ is called a bias graph if $\cC$ has the theta-property.
Frame matroids
The frame matroid associated with any bias graph $(G,\cC)$ is a unique matroid, denoted $FM(G,\cC)$, with ground set $E(G)$ such that a set $I\subseteq E(G)$ is independent if an only if no circuit of $G[I]$ is contained in $\cC$ and for each component of $G[I]$ has at most one circuit.
Zaslavsky showed that a matroid $M$ is a frame matroid if and only if there is a matroid $M’$ and a basis $B$ of $M’$ such that $M$ is a restriction of $M’$ and for each element $e\in E(M’)-B$, the unique circuit of $B\cup\{e\}$ contains at most two elements of $B$.
Lifts of graphic matroids
The lift matroid associated with any bias graph $(G,\cC)$ is a unique matroid, denoted $LM(G,\cC)$, with ground set $E(G)$ such that a set $I\subseteq E(G)$ is independent if an only if no circuit of $G[I]$ is contained in $\cC$ and $G[I]$ contains at most one circuit. Any matroid that is the lift matroid of a bias graph is called a lifted graphic matroid.
Zaslavsky showed that a matroid $M$ is a lifted graphic matroid if and only if there is a matroid $M’$ an element $e\in E(M’)$ such that $M’\del e = M$ and
$M’\con e$ is graphic.
Combining the classes
Let us call a graph $G$ a framework for a matroid $M$ if
- $E(M) = E(G)$,
- $G$ is connected,
- $r(M)\le |V(G)|$, and
- for each vertex $v$ of $G$, the set of edges incident with $v$ is a cocircuit of $M$.
We will call $M$ a framework matroid if it admits a framework representation.
The definition of a framework is motivated by Theorem 1; it has the appealing property that it is constructive. Given a matroid $M$, via a rank oracle, and a graph $G$ one can readily check (in polynomial time) whether or not $G$ is a framework for $M$. This constructive property is in contrast with the following conjectures.
Conjecture 1: There is no polynomial-time algorithm that, given a matroid $M$ via its rank oracle and a graph $G$, determines whether there is a bias graph $(G,\cC)$ such that $M=FM(G,\cC)$.
Conjecture 2: There is no polynomial-time algorithm that, given a matroid $M$ via its rank oracle and a graph $G$, determines whether there is a bias graph $(G,\cC)$ such that $M=LM(G,\cC)$.
I further believe that the recognition problem is intractable for both the class of frame matroids and the class of lifted graphic matroids. In contrast, I think that one can recognize framework matroids.
Conjecture 3: There is a polynomial-time algorithm that, given a matroid $M$ via its rank oracle, determines whether $M$ is a framework matroid.
Technical details
Let us call a graph $G$ a weak framework for a matroid $M$ if
- $E(M) = E(G)$,
- $r(M)\le |V(G)|$,
- for each vertex $v$ of $G$, the set of edges incident with $v$ is the union of a collection of cocircuits of $M$ and a set of loops of $M$, and
- each loop of $M$ is a loop of $G$.
This weakened notion behaves nicely with respect to our three classes.
- If $G$ is a graph, the $G$ is a weak framework for $M(G)$.
- If $M$ is the frame matroid for the bias graph $(G,\cC)$, then $G$ is a weak framework for $M(G)$.
- If $M$ is the lift matroid for the bias graph $(G,\cC)$, then $G$ is a weak framework for $M(G)$.
Lemma 1: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected and $H$ is a subgraph of $G$, then $H$ is a weak framework of $M| E(H)$.
Proof. Note that for any edge $e$ of $G$, $G-e$ is a weak framework of $M-e$. Now consider a vertex $v$ of $G$ and let $X$ denote the set of edges incident with $v$. If there is a nonloop edge $e$ of $G$ that is incident with $v$, then there is a cocircuit $C^*$ of $M$ such that $e\in C^*\subseteq X$. Then $r(E(G-v)) \le r(E(G)) – 1 \le |V(G)|-1 = |V(G-v)|$. Hence $G-v$ is a weak framework of $M\del X$. Now the result follows by deleting the vertices $V(G)-V(H)$, in an appropriately chosen order, and then deleting the edges in $E(G[V(H)]) – E(H)$. $\Box$
Lemma 2: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected, then $r(M)\ge |V(G)|-1$ and equality holds if and only if $M$ is the cycle matroid of $G$.
Proof. Order the vertices of $G$ in the order $(v_1,v_2,\ldots,v_n)$ such that, for each $i\ge 2$, the vertex $v_i$ has a neighbour among $\{v_1,\ldots,v_{i-1}\}$. The sets $E(G[\{v_1,v_2,\ldots,v_n\}]),\, E(G[\{v_1,v_2,\ldots,v_n\}]),\,\ldots, \,E(G[\{v_1\}])$ have strictly decreasing rank in $M$, so $r(M)\ge |V(G)|-1$.
Equality clearly holds when $M=M(G)$. Conversely suppose that equality holds. A routine variation on the proof of Lemma 1 proves that, for each subgraph $H$ of $G$, we have $r(E(H)) \le |V(H)|-1$. Then, by the first part of the proof, for each connected subgraph $H$ of $G$ we have $r(E(H)) = |V(H)|-1$. In particular, if $H$ is a circuit of $G$, then $E(H)$ is a circuit of $M$, and, if $H$ is a tree of $G$, then $E(H)$ is independent in $M$. Thus $M = M(G)$. $\Box$
The following result is an easy application of Lemmas 1 and 2.
Lemma 3: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected and $M$ is $3$-connected, then $G$ is $2$-connected.
Lemma 4: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected, $M$ is $3$-connected, and $|E(M)|\ge 4$, then $M$ is a framework matroid.
Proof. We may assume that among all connected weak frameworks for $M$ we have chosen $G$ with as many loops as possible. Since $M$ has no loops, if $G$ is not itself a framework of $M$, then there is a vertex $v$ of $G$ such that the set $X$ of edges incident with $v$ is the union of at least two distinct cocircuits of $G$. By Lemma 1 and the fact that $M$ is simple, there is at most one loop at $v$. Choose a cocircuit $C^*\subseteq X$ so that $X-C^*$ contains no loop of $G$. Now define $G’$ by replacing each edge $e=vw$ of $X-C^*$ with a loop at $w$. Note that $G’$ is a weak framework of $M$ and, since $G$ is $2$-connected, $G’$ is connected. However, this contradicts our choice of $G$ and that completes the proof.$\Box$
This proves that:
Theorem 2: The class of framework matroids contains all $3$-connected frame matroids and all $3$-connected lifted graphic matroids.
Represented matroids
A matrix with at most two nonzero nonzero entries in each column is called a frame matrix. Let $A_1$ and $A_2$ be matrices over a field $\bF$ with a common set $E$ of column indices. We say that $A_1$ and $A_2$ are row equivalent if $A_1$ can be obtained from $A_2$ by elementary row operations.
Problem 1: Given as input a matrix $A$, decide whether $A$ is row equivalent to a frame matrix.
Note that, if a matrix $A$ is row-equivalent to a frame matrix, then $M(A)$ is a frame matroid.
Conjecture 4: There is a polynomial-time algorithm that solves Problem 1.
We say that $A_1$ and $A_2$ are projectively equivalent if $A_1$ is row equivalent to a matrix $A_3$ that can be obtained from $A_2$ by column scaling. A signed incidence matrix is a frame matrix with entries in $\{0,\pm 1\}$ such that each column sums to zero. A lift of a matrix is a matrix obtained by appending a new row. A lifted signed-incidence matrix is a lift of a signed-incidence matrix.
Problem 2: Given as input a matrix $A$, decide whether $A$ is projectively equivalent to a lifted signed-incidence matrix.
Note that, if a matrix $A$ is projectively equivalent to a lifted signed-incidence matrix, then $M(A)$ is a lift of a graphic matroid.
Conjecture 5: There is a polynomial-time algorithm that solves Problem 2.
The amazing theorem
Let $A\in \bF^{V\times E}$ be a frame matrix with no all-zero column. The support of $A$ is the graph $G=(V,E)$ such that a vertex $v\in V$ is incident with an edge $e\in E$ if and only if the $(v,e)$-entry of $A$ is nonzero. If $A$ is a signed-incidence matrix with support $G$, then we say that $A$ is a signed incidence matrix of $G$.
The following remarkable fact came out of discussions with Bert Gerards and Geoff Whittle.
Theorem 3: Let $A$ be a matrix and let $M=M(A)$ be a framework matroid with framework $G$. Then either
- $A$ is projectively equivalent to a lift of the signed-incidence matrix of $G$, or
- $A$ is row equivalent to a frame matrix whose support is $G$.
Proof. By Lemma 2, we may assume that $r(M) = |V(G)|$. For each cocircuit $C$ of $M$ there is a vector $v$ in the row space of $A$ whose support is $C$. Therefore there is a frame matrix $A’$ whose support is $G$ and whose row space is contained in the row space of $A$. Now $G$ is a weak framework for $M(A’)$, so the rank of $A’$ is either $|V(G)|$ or $|V(G)|-1$. If $A’$ has rank $|V(G)|$, then $A$ is row equivalent to the frame matrix $A’$, as required. Thus we may assume that $A’$ has rank $|V(G)|-1$. Then, by Lemma 2, $M(A’)= M(G)$ and hence $A’$ is projectively equivalent to the signed incidence matrix of $G$. Finally, since the row space of $A’$ is contained in the row space of $A$ and $rank(A) = rank(A’)+1$, $A$ is row equivalent to a lift of $A’$. $\Box$
Theorem 3 some interesting consequences; the first of these is a striking converse to Theorem 2.
Corollary 1: For any field $\bF$, if $M$ is an $\bF$-representable framework matroid, then $M$ is either a frame matroid or a lifted graphic matroid.
Corollary 2: If $M$ is a $3$-connected matroid that has a representation by a frame matrix, then every representation of $M$ is either row equivalent to a frame matrix or is projectively equivalent to a lifted signed incidence matrix.
Corollary 3: If $M$ is a $3$-connected matroid that has a representation by a lifted signed incidence matrix, then every representation of $M$ is either projectively equivalent to a lifted signed incidence matrix or is row equivalent to a frame matrix.
Consider, for example, the matroid $R_{10}$. It is represented over GF$(3)$ by the “unsigned” incidence matrix of $K_5$. However, over GF$(2)$ it is represented by a lift of a signed incidence matrix of $K_5$.
References
[BC80] R.E. Bixby, W.H. Cunningham, Converting linear programs to network problems, Math. Oper. Res. 5 (1980), 321-357.
[Sey81] P.D. Seymour, Recognizing graphic matroids, Combinatorica 1 (1981), 75-78.
[Zas91] T. Zaslavsky, Biased graphs. II. The three matroids, J. Combin. Theory, Ser. B 51 (1991), 46-72.