Guest post by Daryl Funk

This post is meant as a short postscript to Irene’s post in March, Which biased graphs are group-labelled graphs? Since Irene’s post generated a fair number of comments, there may be some interest in taking a closer look at the construction used in Theorem 1 of that post. Let us quickly remind ourselves of the context, and the theorem.

A graph $G$ together with a collection $\mathcal{B}$ of its cycles — called balanced — is a biased graph. Cycles not in $\mathcal{B}$ are unbalanced. Orienting the edges of $G$ and labelling each edge with an element of a group gives us a group-labelled graph. A group-labelled graph naturally gives rise to a biased graph, as follows. Traverse each cycle via a simple closed walk, taking the product of the group elements labelling each edge as you go, taking the inverse of the element when traversing an edge in reverse. Declare as balanced just those cycles for which such a product is the identity. Thus, group-labelled graphs provide the primary examples of biased graphs. An arbitrary biased graph $(G,\mathcal{B})$ is group-labellable if there is a group and a labelling for which this procedure yields precisely its collection of balanced cycles $\mathcal{B}$. Hence the question of our title: Which biased graphs are group-labelled? Theorem 1 provides an answer.

Theorem 1. Let $(G,\mathcal{B})$ be a biased graph. Construct a 2-cell complex $K$ from $G$ by adding a disc with boundary $C$ for each $C \in \mathcal{B}$. Then the following are equivalent:

1. $(G,\mathcal{B})$ is group-labellable.
2. $(G,\mathcal{B})$ is $\pi_1(K)$-labellable (where $\pi_1(K)$ is the fundamental group of $K$).
3. Every unbalanced cycle of $G$ is noncontractible in $K$.

Barring degenerate cases, the $\pi_1(K)$-labelling constructed by Theorem 1 is a labelling by an infinite group. In practice, we often work with graphs labelled by a finite group — probably the most studied group-labelled graphs are those labelled by the group of order two (i.e. signed graphs). Moreover, we consider only finite graphs. The following therefore is a natural question:

Question 1. If $(G,\mathcal{B})$ is group-labellable, is $(G,\mathcal{B})$ labellable by a finite group?

Could it be that there are group-labelled graphs whose collections of balanced cycles may only be realised by a labelling using an infinite group?

Given any group-labelling of a biased graph $(G,\mathcal{B})$, say using elements of the group $\Gamma$, there is a homomorphism from the fundamental group $\pi_1(K)$ of the 2-cell complex $K$ we construct in Theorem 1, to $\Gamma$. This homomorphism makes explicit the connection between the topology of $K$ and group-labellings of $(G,\mathcal{B})$. It also enables us to easily answer Question 1.

In preparation for a description of this homomorphism, let us recall some additional terminology and notation from Irene’s original post. Let $G$ be a graph and let $\Gamma$ be a group. Orient the edges of $G$, and let $\phi: E(G) \to \Gamma$ be a function. We extend $\phi$ to the set of closed walks in $G$ by defining, for closed walk $W$ with edge sequence $e_1, e_2, \ldots, e_k$,
\[ \phi(W) = \phi(e_1)^{\textrm{dir}(e_1)} \phi(e_2)^{\textrm{dir}(e_2)} \cdots \phi(e_k)^{\textrm{dir}(e_k)} \]
where $\textrm{dir}(e_i)$ is 1 if $W$ traverses edge $e_i$ in the forward direction, and is $-1$ if $W$ traverses $e_i$ in the backward direction. Let $\mathcal{B}_\phi$ be the collection of cycles $C$ for which a simple closed walk $W$ traversing $C$ has $\phi(W)=1$. With this notation, $(G,\mathcal{B})$ is group-labellable if there is a group $\Gamma$ and labelling $\phi$ such that $\mathcal{B}_\phi = \mathcal{B}$. In this case we say the labelling $\phi$ realises $\mathcal{B}$, and that $(G,\mathcal{B})$ is $\Gamma$-labellable.

As Irene described near the end of her post, there is a fourth statement equivalent to statements 1, 2, and 3 of Theorem 1. To state it, we need just two more definitions. A rerouting of a closed walk $W$ is a closed walk $W’$ obtained from $W$ by replacing a subpath $P$ of $W$, say between vertices $u$ and $v$, with another $u$-$v$ path $P’$ that is internally disjoint from $P$. If $P \cup P’$ is a balanced cycle, then this is a balanced rerouting. Statement 4 below is equivalent to Statements 1, 2, and 3 of Theorem 1:

4. No unbalanced cycle can be moved to a balanced cycle via a sequence of balanced reroutings of closed walks.

We may now describe the homomorphism $\pi_1(K) \to \Gamma$, where $K$ is the 2-cell complex constructed from $(G,\mathcal{B})$ and $(G,\mathcal{B})$ is $\Gamma$-labellable. Let $\phi : E(G) \to \Gamma$ with $\mathcal{B}_\phi = \mathcal{B}$. The fundamental group $\pi_1(K)$ of $K$ is constructed in our proof of Theorem 1 with presentation in terms of generators $g_e$, one for each edge $e$ not in a chosen spanning tree of $G$, and relations among these generators given by simple closed walks around the cycles in $\mathcal{B}$. Each edge in the spanning tree is labelled by the group identity 1, and for each cycle in $\mathcal{B}$ we add a relation corresponding to the product of the generators labelling the edges as they are traversed by a simple closed walk around the cycle (as described by Irene in her original post; of course, details may be found in our paper [DFP14]). Let us denote this $\pi_1(K)$-labelling by $\rho : E(G) \to \pi_1(K)$. For an element $g \in \pi_1(K)$ expressed as the word $g = g_{e_1}^{a_1} g_{e_2}^{a_2} \cdots g_{e_m}^{a_m}$ for some generators $g_{e_1}, g_{e_2}, \ldots, g_{e_m}$ and integers $a_1, a_2, \ldots, a_m$, define $\eta : \pi_1(K) \to \Gamma$ by
\[ \eta(g) = \eta \left( g_{e_1}^{a_1} g_{e_2}^{a_2} \cdots g_{e_m}^{a_m} \right) = \phi \left( \rho^{-1}(g_{e_1})^{a_1} \rho^{-1}(g_{e_2})^{a_2} \cdots \rho^{-1}(g_{e_m})^{a_m} \right) .\]

Theorem 2.The map $\eta:\pi_1(K) \to \Gamma$ is a group homomorphism.

Proof. Clearly $\eta$ is a homomorphism if it is well-defined. So suppose $g=$ $g_{n_1}^{a_{n_1}} g_{n_2}^{a_{n_2}} \cdots g_{n_m}^{a_{m_n}}$ $=$ $g_{k_1}^{a_{k_1}} g_{k_2}^{a_{k_2}} \cdots g_{k_p}^{a_{k_p}}$ are two words expressing the element $g \in \pi_1(K)$, where $g_{n_1}$, $g_{n_2}$, $\ldots$, $g_{n_m}$, $g_{k_1}$, $g_{k_2}$, $\ldots$, $g_{k_p}$ are generators and $a_{n_1}, a_{n_2}, \ldots$, $a_{n_m}, a_{k_1}, a_{k_2}, \ldots, a_{k_p}$ are integers. We show that
\[ \eta\left(g_{n_1}^{a_{n_1}} g_{n_2}^{a_{n_2}} \cdots g_{n_m}^{a_{m_n}} ( g_{k_1}^{a_{k_1}} g_{k_2}^{a_2} \cdots g_{k_p}^{a_{k_p}})^{-1}\right)=1,\]
and so that $\eta$ maps both words $g_{n_1}^{a_{n_1}} g_{n_2}^{a_{n_2}} \cdots g_{n_m}^{a_{m_n}}$ and $g_{k_1}^{a_{k_1}} g_{k_2}^{a_2} \cdots g_{k_p}^{a_{k_p}}$ to the same element of $\Gamma$. We have
\begin{multline*}
\eta \left(g_{n_1}^{a_{n_1}} g_{n_2}^{a_{n_2}} \cdots g_{m_n}^{a_{m_n}} ( g_{k_1}^{a_{k_1}} g_{k_2}^{a_{k_2}} \cdots g_{k_p}^{a_{k_p}} )^{-1}\right) \\
= \phi \left( \rho^{-1}(g_{n_1})^{a_{n_1}} \rho^{-1}(g_{n_2})^{a_{n_2}} \cdots \rho^{-1}(g_{n_m})^{a_{n_m}} \rho^{-1}(g_{k_p})^{-a_{k_p}} \cdots \rho^{-1}(g_{k_2})^{-a_{k_2}} \rho^{-1}(g_{k_1})^{-a_{k_1}} \right) \\
= \phi\left( \rho^{-1}(g_{n_1})\right)^{a_{n_1}} \phi\left(\rho^{-1}(g_{n_2})\right)^{a_{n_2}} \cdots \phi\left(\rho^{-1}(g_{n_m})\right)^{a_{n_m}} \phi \left(\rho^{-1}(g_{k_p})\right)^{-a_{k_p}} \cdots \\ \phi\left(\rho^{-1}(g_{k_2})\right)^{-a_{k_2}} \phi\left(\rho^{-1}(g_{k_1})\right)^{-a_{k_1}}.
\end{multline*}
In $\pi_1(K)$, $g_{n_1}^{a_{n_1}} g_{n_2}^{a_{n_2}} \cdots g_{m_n}^{a_{m_n}} g_{k_p}^{-a_{k_p}} \cdots g_{k_2}^{-a_{k_2}} g_{k_1}^{-a_{k_1}} = 1$; the relations in $\pi_1(K)$ that reduce this word to the identity correspond to a sequence of reroutings via balanced cycles. The word in $\Gamma$ given by $\eta$ has the same corresponding edge sequence. Since $\mathcal{B}_\phi = \mathcal{B}$, this word is therefore reduced to the identity by the same sequence of balanced reroutings. $\square$

Let’s now use this homomorphism to answer Question 1.

Theorem 3. There exists a group-labellable biased graph whose collection of balanced cycles is not realised by any labelling with any finite group.

Proof. Let $H$ be the Higman group
\[ H = \left< a, b, c, d \mid a^{-1} b a = b^2, b^{-1} c b = c^2, c^{-1} d c = d^2, d^{-1} a d = a^2 \right>. \]
The Higman group is infinite with no non-trivial finite quotients [H51] (the Wikipedia entry has a brief description). Construct a simplicial 2-complex $\mathcal{K}$ by identifying the points of edges marked $a$, $b$, $c$, and $d$, respectively, of five pentagons, oriented as shown in the figure.

Let $G$ be the graph consisting of the vertices and edges of the barycentric subdivision of $\mathcal{K}$ (the following figure shows the part of the graph obtained from the first pentagon above), and let $\mathcal{B}$ be the set of cycles of $G$ that are contractible in $\mathcal{K}$.

By construction, the fundamental group $\pi_1(\mathcal{K})$ is $H$. Hence the biased graph $(G,\mathcal{B})$ is $H$-labellable. Let $\Gamma$ be a group for which there is a labelling $\gamma : E(G) \to \Gamma$ realising $\mathcal{B}$. By Theorem 2, there is a homomorphism from $H$ to $\Gamma$. Since $H$ has no non-trivial finite quotient, and $(G,\mathcal{B})$ is not labellable by the trivial group, $\Gamma$ cannot be finite. $\square$

The graph $G$ constructed in the proof of Theorem 3 is pretty; it is shown below.

References

[H51] Graham Higman. A finitely generated infinite simple group. J. London Math. Soc., 26:61-64, 1951.

[DFP14] DeVos, Matthew; Funk, Daryl; and Pivotto, Irene. When does a biased graph come from a group labelling? Advances in Applied Mathematics, Vol 61 (October 2014), pp 1-18.

Guest post by Thomas Savitsky

A $k$-polymatroid is a generalization of a matroid in which the rank of an element is allowed to exceed one, but cannot exceed $k$.

Definition 1.
Let $S$ be a finite set. Suppose $\rho : 2^S \to \mathbb{N}$ satisfies the following four conditions:

• if $X, Y \subseteq S$, then $\rho(X \cap Y) + \rho(X \cup Y) \le \rho(X) + \rho(Y)$
  (submodular);
• if $X \subseteq Y \subseteq S$, then $\rho(X) \le \rho(Y)$ (monotone);
• $\rho(\varnothing) = 0$ (normalized); and
• $\rho(\{x\}) \le k$ for all $x \in S$.

Then $(\rho, S)$ is a $k$-polymatroid with rank function $\rho$ and ground set $S$.

So a matroid is a $1$-polymatroid. Here are a few examples of $2$-polymatroids.

• If $(r_1, S)$, and $(r_2, S)$ are matroids, then $(r_1+r_2, S)$ is a $2$-polymatroid.
• If $G = (V, E)$ is a graph, one may define a $2$-polymatroid $(\rho, E)$, where
  $\rho(X)$ equals the number of vertices incident to $X$.
• Given an $m \times 2n$ matrix with entries in a field, one may define a representable $2$-polymatroid on $n$ elements by pairing up the columns in a obvious manner.

We became interested in $k$-polymatroids and thought it would be practical to have a catalog of the small ones at our disposal. We successfully adapted the canonical deletion
approach used by Mayhew and Royle (see [MR08]) to catalog matroids on nine elements to $2$-polymatroids. This first required developing a theory of single-element extensions of $k$-polymatroids. We then wrote code in the C programming language and interfaced with Brendan McKay’s nauty program and the igraph graph library. After a few days of execution time on a desktop computer, our program produced a catalog of all $2$-polymatroids, up to isomorphism, on at most seven elements.

By consulting our catalog, we produced Table 1, which lists the number of unlabeled $2$-polymatroids on the ground set $\{1, \ldots, n\}$ by rank.

Surprisingly, the number of $2$-polymatroids on seven elements is not unimodal in rank. In contrast, matroids are conjectured to be unimodal in rank, and the catalog of matroids with nine elements supports this. By the way, the symmetry in the columns in Table 1 is accounted for by a notion of duality for $2$-polymatroids.

Note that one can obtain the analogue of Table 1 for labeled $2$-polymatroids by computing the automorphism group of each $2$-polymatroid and then using the Orbit-Stabilizer relation. This allowed us to confirm the results of our enumeration through another means. By interpreting a $2$-polymatroid as a solution to a certain integer programming program, the number of labeled $2$-polymatroids can theoretically be computed by integer programming software. Fortunately, the software package SCIP was up to the task when $n \le 7$.

See [Sa14] for more details on all of the above.

Now recall that a matroid $M$ is paving if it contains no circuit of size less than $r(M)$. If both $M$ and $M^{*}$ are paving, then $M$ is sparse-paving. If $M$ is sparse-paving, then one can show that that every set of size less than $r(M)$ is independent and that the dependent $r(M)$-subsets are circuit-hyperplanes; furthermore, the symmetric difference of any two circuit-hyperplanes must be at least $4$. In fact, sparse-paving matroids are characterized by these properties.

It is conjectured that almost all matroids are sparse-paving.

The ideas in the remainder of this post were communicated to me by
Rudi Pendavingh.

We first mention the following background item. Let $S = \{e_1, e_2, \dots, e_n\} \cup \{f_1, f_2, \dots, f_n\}$ be a set of size $2n$. Suppose $(r, S)$ is a matroid. We will pair up the elements of $S$ to define a $2$-polymatroid as follows. Define $S’ = \big\{\{e_1, f_1\}, \{e_2, f_2\}, \dots, \{e_n, f_n\}\big\}$, and define $\rho : S’ \to \mathbb{N}$ by
$$\rho\big(\big\{\{e_{i_1}, f_{i_1}\}, \{e_{i_2}, f_{i_2}\}, \dots, \{e_{i_m}, f_{i_m}\}\big\}\big) = r(\{e_{i_1}, f_{i_1}, e_{i_2}, f_{i_2},\dots, e_{i_m}, f_{i_m}\}).$$
Then $(\rho, S’)$ is a $2$-polymatroid on $n$ elements with $\rho(S’) = r(S)$. Furthermore, every $2$-polymatroid on $n$ elements may be obtained in this manner from a matroid on $2n$ elements. See Section 44.6b of Schrijver’s Combinatorial Optimization or Theorem 11.1.9 of Oxley’s Matroid Theory for details.

Now assume that $r$ is a sparse-paving matroid. If $r(S)$ is odd, then $\rho$ does not detect any of the circuit-hyperplanes of $r$; namely,
\begin{equation*}
\rho(X) =
\begin{cases}
2|X| & \text{if} \ 2|X| < r(S),\\ r(S) & \text{if} \ 2|X| > r(S).\\
\end{cases}
\end{equation*}
To illustrate, all the rank-$7$ sparse-paving matroids on 14 elements map, in this manner, to a single rank-$7$ $2$-polymatroid on seven elements. However, if $r(S)$ is even, then the circuit-hyperplanes of $r$ are picked up by $\rho$. Perhaps this observation, combined with the conjecture that almost all matroids are sparse-paving, makes the non-unimodality of $2$-polymatroids appear more reasonable.

References

[MR08] Dillon Mayhew and Gordon F. Royle.
Matroids with nine elements.
J. Combin. Theory Ser. B, 98(2):415–431, 2008.
doi

[Sa14] Thomas J. Savitsky.
Enumeration of 2-polymatroids on up to seven elements.
SIAM J. Discrete Math., 28(4):1641–1650, 2014.
doi

Guest Post by Rohan Kapadia. 

Two popular invariants in graph theory are the girth of graph (the size of its smallest cycle) and its edge-connectivity. Given a graph, both can be easily computed. In fact, if $e$ is an edge and $s$ and $t$ are its ends, then finding the shortest cycle or smallest edge-cut containing $e$ can be done by finding a shortest $s,t$-path or a minimum $s,t$-cut, both easy problems.

Can we generalize the problem of computing these invariants to matroids? Cycles and minimal edge-cuts in graphs correspond to circuits and cocircuits in their cycle matroids (as long as we count loops and pairs of parallel edges as cycles). So we know how to find a shortest circuit or cocircuit in a graphic matroid. Note that in the matroid world, these become just one problem, since computing the smallest size of a cocircuit is the same under duality as computing the girth of a matroid, the smallest size of a circuit.

In this post I will discuss computing the girth of a matroid. We will only consider binary matroids, since the problem is already intractable just for this class: Alexander Vardy [4] proved that it is NP-hard to compute the girth of a given binary matroid (he actually worked on an equivalent problem from coding theory, that of finding the minimum distance of a binary linear code).

But, we know that it is easy to compute the girth of two types of binary matroids, the graphic and cographic ones. Are there other subsets of the binary matroids where the problem is still tractable? The class of regular matroids is an obvious candidate to consider after the graphic and cographic. In fact, the regular matroid decomposition theorem of Paul Seymour says that any regular matroid can be built by repeated $1$-, $2$-, and $3$-sums of graphic matroids, cographic matroids, and one particular matroid called $R_{10}$. This means that for any regular matroid $M$, there is a tree $T$, each of whose vertices is either a graphic matroid, a cographic matroid, or a copy of $R_{10}$, and such that $M$ is built by $(\leq 3)$-sums from these smaller matroids, each sum corresponding to an edge of the tree. Computing the girth of regular matroids is easy if we have an algorithm to find such a tree. How to find it is beyond the scope of this post, but more information can be found in [3].

Now let’s see how to compute the girth of a regular matroid. It’s actually easier if we allow matroid elements to be weighted. If each element $e$ of a matroid $M$ has a non-negative weight $w(e)$, then we’ll say that the girth of $M$ is \[ \min\left\{\sum_{e \in C} w(e) : C \text{ is a circuit of } M\right\} . \] For graphic and cographic matroids, this introduces no difficulties since we can find minimum cuts and shortest paths even in weighted graphs.

Theorem 1. There is a polynomial-time algorithm to compute the girth of a given regular matroid $M$ with non-negative weights on its elements.

Proof. First, we need to get the tree $T$ mentioned above. If $T$ has one vertex, then $M$ is just graphic, cographic, or a copy of $R_{10}$, and the problem is easy. Otherwise, we pick any leaf of the tree, $v$. So $v$ corresponds to a matroid $M_1$ that is either graphic, cographic, or a copy of $R_{10}$. The tree $T – v$ corresponds to a regular matroid $M_2$, such that $M$ is a $(\leq 3)$-sum of $M_1$ and $M_2$. If $M$ is a $1$-sum of $M_1$ and $M_2$, then the girth of $M$ is the minimum of the girths of $M_1$ and $M_2$, so we can find it by induction.

Otherwise, suppose that $M$ is a $2$-sum of $M_1$ and $M_2$. Denote by $e$ the common element in $E(M_1)$ and $E(M_2)$. We give each element of $M_1$ and of $M_2$ the same weight as it had in $M$, and we give $e$ a weight of zero in $M_1$. We will assign the weight of $e$ in $M_2$ later. Since $M_1$ is either graphic, cographic, or a copy of $R_{10}$, we can find the following two things in polynomial time: the first is a minimum-weight circuit $C$ of $M_1 \backslash e$ and the second is a minimum-weight circuit $C’$ of $M_1$ containing $e$.

We now assign the value $\sum_{f \in C’} w(f)$ as the new weight of $e$ in $M_2$. It is not too hard to see that the girth of $M$ is the minimum of the weight of $C$ and the girth of $M_2$. We can therefore find it by induction.

The last case is when $M$ is a $3$-sum of $M_1$ and $M_2$. This is just a variant of the $2$-sum case but we need to find four circuits in $M_1$ instead of two; the details are omitted. $\square$

We have seen that computing girth is easy even in regular matroids, and the reason was that we can reduce them to graphic and cographic matroids. What about other classes of binary matroids? In an earlier entry on this blog, Peter Nelson talked about a theorem announced by Jim Geelen, Bert Gerards and Geoff Whittle [2] which gives a decomposition of binary matroids in any proper minor-closed class similar to that given by the decomposition theorem for regular matroids. The pieces in this decomposition are actually not that different from graphic and cographic matroids.

If $N$ is a binary matroid and $A$ is a matrix such that $N = M(A)$, then a rank-($\leq t$) perturbation of $N$ is a matroid of the form $M(A + T)$, where $T$ is a binary matrix with rank at most $t$.

Here is the statement of their theorem (Theorem 3.1 of [2]) from that earlier post:

Theorem 2. Let $\mathcal{M}$ be a proper minor-closed class of binary matroids. There exist integers $k$ and $t$ so that every vertically $k$-connected matroid in $\mathcal{M}$ is a rank-($\leq t$) perturbation of a graphic or cographic matroid.

This means that, for any proper minor-closed class $\mathcal{M}$ of binary matroids, we can make an efficient algorithm to compute the girth of members of $\mathcal{M}$ if we can do two things efficiently:

1. Compute the girth of a given rank-($\leq t$) perturbation of a graphic or a cographic matroid, and
2. Reduce the problem of computing the girth of members of $\mathcal{M}$ to that of computing the girth of vertically $k$-connected members of $\mathcal{M}$.

We don’t yet know how to solve either of these two subproblems in polynomial time, though in joint work Jim Geelen and I have mostly solved the first one by finding randomized algorithms to do it, which run in polynomial time and work correctly with probability nearly 1 (I won’t say more about those algorithms in this post though).

When $\mathcal{M}$ is the class of regular matroids, Theorem 2 holds with $k = 4$ and $t = 0$ (ignoring the slight exception of $R_{10}$). We can thus compute girth in regular matroids by reducing to the easy case of graphic and cographic matroids.

Unfortunately, the trick we used to do this reduction for regular matroids does not work so easily for other classes. For regular matroids, we needed to be able to find a minimum-weight circuit in a graphic or cographic matroid that used a specified element. While this was easy, the requirement of using a specified element makes things trickier for perturbations.

In the remainder of this post, I will outline a way to compute girth only for one special type of perturbation of graphic matroids, known as the even-cut matroids. But since it’s the same problem under matroid duality, we’ll actually look at cogirth (the smallest size of a cocircuit) in the duals of even-cut matroids, which are projections of graphic matroids. A projection of a graphic matroid $M(G)$ means a matroid of the form $M(A) / e$, where $A$ is a binary matrix obtained by adding one new column, indexed by an element $e$, to the vertex-edge incidence matrix of a graph $G$. The cocircuits of this matroid are precisely the cocircuits of $M(A)$ disjoint from $e$. But we need a way to describe these cocircuits in terms of the graph $G$.

We can view the new column of $e$ that we added to the vertex-edge incidence matrix of $G$ as the characteristic vector of a set of vertices of $G$. So we can fully describe this matroid by the pair $(G, T)$ where $T$ is a subset of $V(G)$. We can assume that $|T|$ is even; if not, then $e$ is a coloop of $M(A)$ and so $M(A) / e$ is graphic and the problem becomes easy.

Now we can describe the cocircuits in terms of the graph: they are precisely the minimal edge-cutsets of the form $\delta(X)$ where $|X \cap T|$ is even. Let’s call such edge-cutsets $T$-even cuts. How can we find a minimum-size $T$-even cut and thereby compute the cogirth of this projection of a graphic matroid? Here is a solution from Barahona and Conforti [1].

Let’s say that $\delta(W)$ is a minimum $T$-even cut in the graph $G$, so we want to either find it, or find another one of equal size. We already know how to find a minimum cut in $G$ in poylnomial time, so we’ll find one of those and call it $\delta(U)$. If we are lucky and $|U \cap T|$ is even, then we’re done. Otherwise, $|U \cap T|$ is odd.

Now let’s look at the possible interactions between $W$ and $U$. Exactly one of the sets $|W \cap U \cap T|$ and $|(V(G) – W) \cap U \cap T|$ is odd and the other is even; by the symmetry between $W$ and $V(G) – W$, let’s say that $|W \cap U \cap T|$ is even. And since $|W \cap T|$ is even, the set $|W \cap (V(G) – U) \cap T|$ is also even.

That means that $\delta(W \cap U)$ and $\delta(W \cap (V(G) – U))$ are also $T$-even cuts! Unless they are empty. But they can’t both be empty, or $W$ would be empty. So suppose, by symmetry, that $\delta(W \cap U)$ is a non-empty $T$-even cut. Then we apply the submodularity inequality: \[ |\delta(W \cap U)| + |\delta(W \cup U)| \leq |\delta(U)| + |\delta(W)|. \] Since $\delta(U)$ is a minimum cut, we have $|\delta(U)| \leq |\delta(W \cup U)|$, which means that $|\delta(W \cap U)| \leq |\delta(W)|$ so $\delta(W \cap U)$ is actually a minimum $T$-even cut!

So we’ve shown that there is a minimum $T$-even cut of the form $\delta(W’)$, where $W’$ is either contained in $U$ or contained in $V(G) – U$. We construct two graphs: $G_1$ is obtained from $G$ by identifying all vertices in $U$ to a single vertex, and $G_1$ is obtained by identifying all vertices in $V(G) – U$ to a single vertex. In both cases, we add the new vertex to the set $T$. We can check that every $T$-even cut of $G_1$ or of $G_2$ is also a $T$-even cut of $G$. But in addition, our desired cut $\delta(W’)$ is definitely a $T$-even cut in either $G_1$ or $G_2$. So we finish by recursively solving the problem for these two smaller graphs.

References

[1] Francisco Barahona and Michele Conforti, A construction for binary matroids, Discrete Math. 66 (1987), 213-218.

[2] Jim Geelen, Bert Gerards and Geoff Whittle, The highly connected matroids in minor-closed classes, arXiv:1312.5012 [math.CO].

[3] K. Truemper, Matroid Decomposition, Leibniz, Plano, Texas, 1998.

[4] Alexander Vardy, The intractability of computing the minimum distance of a code, IEEE Trans. Inform. Theory 43 (1997), 1757-1766.

Guest post by Daniel Slilaty.

In a series of three posts by Irene Pivotto (on 08-26-13, 10-07-13, and 10-28-13) subscribers to The Matroid Union blog were introduced to biased graphs and their matroids. Again, a biased graph is a pair $(G,B)$ in which $G$ is a graph and $B$ is a collection of cycles in $G$ (called balanced) for which any theta subgraph of $G$ contains 0, 1, or 3 balanced cycles, i.e. not exactly two balanced cycles. (A theta subgraph is the union of a pair of cycles that intersect along a path.)

Biased graphs were first defined by Zaslavsky [Za91] and they are primarily used to characterize two types of matroids: single-element coextensions of graphic matroids and frame matroids [Za94]. Frame matroids contain the very important class of Dowling Geometries whose centrality within matroid theory was first displayed by Kahn and Kung [KK82] and more recently by Geelen, Gerards, and Whittle [GGW14]. Given a biased graph $(G,B)$, denote the frame matroid by $F(G,B)$ and the complete lift matroid by $L_0(G,B)$ (i.e., the single-element coextension of $M(G)$ defined by $B$).

The canonical examples of biased graphs are given by gains over a group. Formally, this is a function $\varphi\colon\vec E(G)\to\Gamma$ where $\vec E(G)$ is the collection of oriented edges of a graph (if $e$ is an oriented edge, then $-e$ is the same underlying edge oriented in the opposite direction) and $\Gamma$ is a group such that $-\varphi(e)=\varphi(-e)$ for additive groups and $\varphi(e)^{-1}=\varphi(-e)$ for multiplicative groups. In this post we will only consider abelian groups. One advantage of abelian groups over nonabelian ones is that gain functions, up to a certain type of equivalence, gives rise to and can be specified by homomorphisms $\hat\varphi\colon Z_1(G)\to\Gamma$ in which $Z_1(G)$ is the integer cycle space of the graph. Given $\varphi$, let $B_\varphi$ be the collection of cycles in $G$ for which $\hat\varphi(\vec C)$ is the identity element of $\Gamma$ (0 when $\Gamma$ is additive, 1 when $\Gamma$ is multiplicative). Now $(G,B_\varphi)$ is a biased graph.

Given a biased graph $(G,B)$, a homomorphism $\hat\varphi\colon Z_1(G)\to\Gamma$ such that $B_\varphi=B$ is called a $\Gamma$-realization of $(G,B)$. The following proposition by Zaslavsky can be stated for skew fields as well as ordinary fields.

Proposition 1 (Zaslavsky [Za03]) Let $(G,B)$ be a biased graph and $\mathbb F$ a field.

1. If $(G,B)$ is realizable over the multiplicative subgroup of $\mathbb F$, then $F(G,B)$ is $\mathbb F$-representable.
2. If $(G,B)$ is realizable over the additive subgroup of $\mathbb F$, then $L_0(G,B)$ is $\mathbb F$-representable.

Partial fields have become a central and popular topic in modern matroid theory. (See Stefan van Zwam’s blog post from 09-16-13 for an introduction to partial fields.) Briefly a partial field is a pair $\mathbb P=(R,U)$ in which $R$ is a commutative ring and $U$ is a subgroup of the multiplicative group of units of $R$ such that $-1\in U$.

Proposition 2 (van Zwam [vZ09]) Let $\mathbb P=(R,U)$ be a partial field and $(G,B)$ a biased graph.

1. Let $\varphi\colon\vec E(G)\to U$ be a $U$-realization of $(G,B)$. If $\varphi(\vec C)$ is a fundamental element of $\mathbb P$ for each cycle $C$ of $G$, then the frame matroid $F(G,B)$ is $\mathbb P$-representable.
2. Let $\varphi\colon\vec E(G)\to R_+$ be an $R_+$-realization of $(G,B)$. If $\varphi(\vec C)\in U$ for every unbalanced cycle $C$ of $(G,B)$, then $L_0(G,B)$ is $\mathbb P$-representable.

“Well-connected” examples of matroids representable over various partial fields can sometimes be hard to come by. The largest possible simple $\mathbb P$-matroids of a given rank are known for various partial fields, but not every $\mathbb P$-matroid of a given rank must be contained within a $\mathbb P$-matroid of maximum size. Sometimes biased graphs defined by embeddings in surfaces can provide interesting examples of $\mathbb P$-matroids as well. Given a graph $G$ embedded in a closed surface $S$, invariance of homology gives us a natural homomorphism $\natural\colon Z_1(G)\to H_1(S)$ where $H_1(S)$ is the first homology group of the surface calculated with integer coefficients. Now given a partial field $\mathbb P=(R,U)$ there may be some choice of $\sigma\colon H_1(S)\to\mathbb P$ such that the biased graph $(G,B_{\sigma\natural})$ satisfies the conditions of Proposition 2.

Two of my favorite examples come from graphs embedded in the Klein Bottle. The Klein bottle is the surface obtained by identifying two Möbius bands along their circular boundary. In the figure below we have the lighter and darker Möbius bands. The first homology group $H_1(K)$ of the Klein bottle is $\mathbb Z\times\mathbb Z_2$. Of particular usefulness for us is the fact that any cycle $C$ embedded in the Klein bottle now has $\pm\natural(\vec C)\in\{(0,0),(1,0),(0,1),(1,1),(2,0)\}$.

Now let $G$ be a nice large graph embedded in the Klein bottle with high face width e.g., a square grid.

• The dyadic partial field $\mathbb D=(\mathbb Q,U)$ has $U=\{\pm 2^i:i\in\mathbb Z\}$. Define $\sigma\colon\mathbb Z\times\mathbb Z_2\to\mathbb Q_+$ by $(1,0)\mapsto 1$ and $(0,1)\mapsto 0$. This yields $\sigma(a,b)\in\{0,\pm 1,\pm 2\}\subset U$ and so $L_0(G,B_{\sigma\natural})$ is $\mathbb D$-representable by
  Proposition 2 (2).
• The 2-cyclotomic partial field $\mathbb K_2=(\mathbb Q(x),U)$ has $U=\{\pm x^i(1-x)^j(1+x)^k:i,j,k\in\mathbb Z\}$. Define $\sigma\colon\mathbb Z\times\mathbb Z_2\to U$ by $(1,0)\mapsto x$ and $(0,1)\mapsto \pm1$. Either choice for $\sigma(0,1)$ yields $\sigma(a,b)\in\{1,x,-x,x^{-1},-x^{-1},x^2,x^{-2}\}$ and each element of this set is a fundamental element of $\mathbb K_2$ [vZ09]. Thus $F(G,B_{\sigma\natural})$ is $\mathbb K_2$-representable by Proposition 2(1). Representations of matroids over $\mathbb K_2$ have homomorphic images over other interesting partial fields as well, e.g., the golden-mean and Gersonides partial fields.

These are two very nice examples, but are there more? Do other surfaces yield interesting partial fields to work with? Other surfaces have restrictions on the homology classes of cycles embedded on their surface although these restrictions are not as tight as those for the Klein bottle. The first homology group for the torus is $\mathbb Z\times\mathbb Z$ and cycles must be in homology class $(a,b)$ where the greatest common divisor of $a$ and $b$ is 1. The first homology group of Dyck’s surface (i.e., the connected sum of the torus and the projective plane) is $\mathbb Z\times\mathbb Z\times \mathbb Z_2$ and cycles must be in homology classes $(a,b,0)$, $(a,b,1)$, or $(2a,2b,0)$ where the greatest common divisor of $a$ and $b$ is 1. Then again, is it necessary to restrict ones attention to graphs embedded in surfaces? There are other interesting topological spaces that could be explored as well: dunce hats and connected sums of surfaces with dunce hats, for example.

References

[KK82] J. Kahn, J. Kung, Varieties of combinatorial geometries, Trans. Amer. Math. Soc. 271 (1982) 485–499.

[GGW14] J. Geelen, B. Gerards, G. Whittle, Solving Rota’s conjecture, Notices Amer. Math. Soc. 61 (2014) 736–743.

[vZ09] S. van Zwam, Partial Fields in Matroid Theory, Doctoral dissertation, Technische Universiteit Eindhoven, Netherlands, 2009.

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

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

[Za94] T. Zaslavsky, Frame matroids and biased graphs, European J. Combin. 15 (1994) 303–307.

[Za03] T. Zaslavsky, Biasedgraphs IV: Geometrical realizations, J. Combin. Theory Ser. B 89 (2003) 231–297.