This post is mainly about results that I proved together with Matt DeVos and Daryl Funk, partly while they were visiting the University of Western Australia after the 37ACCMCC (Dillon talked about this conference in his blog post on December 16, 2013).
First, let me remind you of what a biased graph is (more details can be found in my introductory post). A biased graph is a pair $(G,\mathcal{B})$, where $G$ is a graph and $\mathcal{B}$ is a set of cycles of $G$ satisfying the theta-property: there is no theta subgraph of $G$ that contains exactly two cycles in $\mathcal{B}$. Cycles in $\mathcal{B}$ are called balanced, while the other cycles of $G$ are unbalanced.
A quite general way of constructing biased graphs is via group-labelled graphs. Pick your favourite (say multiplicative) group $\Gamma$ and graph $G$, and assign to each edge $e$ of $G$ an orientation and a value $\phi(e)$ from $\Gamma$: then what you have is a group-labelled graph. Now consider any walk $W$ in $G$, with edge sequence $e_1,e_2,\ldots,e_k$ and extend $\phi$ as
$\phi(W)=\prod_{i=1}^{k}\phi(e_i)^{\textrm{dir}(e_i)}$,
where $\textrm{dir}(e_i)$ is 1 if $e_i$ is forward in $W$, and -1 otherwise. Then we define a cycle $C$ of $G$ to be balanced if a simple closed walk $W$ around $C$ has $\phi(W)=1$. It’s easy to see that this definition is independent of the choice for $W$, and in this way we get, indeed, a biased graph. In this case we identify the group-labelled graph with the associated biased graph. If a biased graph can be constructed in this way from a group $\Gamma$, then we say that such a biased graph is $\Gamma$-labellable. If a biased graph is $\Gamma$-labellable for some group $\Gamma$, then we say that the biased graph is group-labellable. Not all biased graphs are group-labellable, hence the question that is the title of this post. As it turned out, there is a nice topological answer to this question.
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 every $C \in \mathcal{B}$. Then the following are equivalent:
- $(G,\mathcal{B})$ is group-labellable.
- $(G,\mathcal{B})$ is $\pi_1(K)$-labellable (where $\pi_1(K)$ is the fundamental group of $K$).
- Every unbalanced cycle of $G$ is noncontractible in $K$.
Before I explain a bit how the proof works, let me discuss some nice constructions that we derived using this theorem. For any group $\Gamma$, the class of $\Gamma$-labellable graphs is closed under minors, for both definition of minors given in my second post on biased graphs. Using Theorem 1, we proved that if $\Gamma$ is an infinite group then there are infinitely many excluded minors to the class of $\Gamma$-labellable biased graphs. In fact, we proved something stronger, namely that there is an infinite list of excluded minors on $n$ vertices for every $n \geq 3$.
Theorem 2: For every $n \geq 3$ and $\ell$ there exists a biased graph $(G,\mathcal{B})$ with the following properties:
- $G$ is a graph on $n$ vertices and every pair of vertices is joined by at least $\ell$ edges.
- $(G,\mathcal{B})$ is not group-labellable.
- For every infinite group $\Gamma$, every proper minor of $(G,\mathcal{B})$ is $\Gamma$-labellable.
For a group $\Gamma$, let $\mathcal{F}_{\Gamma}$ and $\mathcal{L}_{\Gamma}$ denote the class of frame and lift matroids respectively that arise from $\Gamma$-labelled graphs. From Theorem 2 (and a one-page argument) we also show that
Theorem 3: For every infinite group $\Gamma$ and every $n \geq 3$ the classes $\mathcal{F}_{\Gamma}$ and $\mathcal{L}_{\Gamma}$ have infinitely many excluded minors of rank $n$.
Theorem 3 implies in particular that frame and lift matroids are not well-quasi ordered. This was already known, since swirls and spikes form infinite antichains of, respectively, frame and lift matroids (see [GGW02] and [M05]). As far as I know, however, it wasn’t known that there are infinite antichains of frame and lift matroids all of the same rank.
I’ll conclude the post by mentioning the two main ingredients for the proof of Theorem 1. The first main part of the proof consists of expressing $\pi_1(K)$ in the appropriate way. Let $\gamma_e$ be a variable associated with every edge in $G$. We use an application of Van Kampen’s Theorem (see Hatcher’s book on algebraic topology), to express $\pi_1(K)$ as the group presented by the generating set $\{\gamma_e | e \in E(G)\}$, with the relations given by setting
$\prod_{i=1}^{k}\phi(e_i)^{\textrm{dir}(e_i)}=1$,
for each balanced cycle $C$ and any closed walk $W$ around $C$ with edge sequence $e_1,\ldots,e_k$. This allows us to show that (3) implies (2).
The second ingredient of the proof involves reroutings. Consider a closed walk $W$ containing a path $P$, and a balanced cycle $C$ containing $P$. Let $P’$ be the complement of $P$ in $C$; then the walk $W’$ obtained by from $W$ by replacing $P$ with $P’$ is obtained by rerouting along the balanced cycle $C$. If in the previous definition $W$ and $W’$ are both simple walks around a cycle, then the theta property implies that $W$ is balanced if and only if $W’$ is balanced. However, if we start with a simple closed walk $W_1$ around a cycle, we do a series of reroutings and we end with a simple closed walk $W_k$ around a cycle, then knowing the bias of $W_1$ doesn’t tell us anything about the bias of $W_k$, since the intermediate closed walks in the sequence of reroutings may not be simple closed walks around a cycle. However, things are different for group-labelled graphs.
Suppose that $(G,\mathcal{B})$ is a group-labelled graph (so every edge $e$ of $G$ has an orientation and a value $\phi(e)$ from some group $\Gamma$). Consider the extension of $\phi$ to closed walks of $G$, as above. If a closed walk $W’$ is obtained from a closed walk $W$ by rerouting along a balanced cycle, then $\phi(W)=\phi(W’)$ (because $C$ is balanced, so $\phi(P)=\phi(P’)$ in the definition of rerouting). So if $(G,\mathcal{B})$ is group-labelled, then we can never start from a simple closed walk around a balanced cycle and obtain (via reroutings) a simple closed walk around an unbalanced cycle. That is, any biased graph $(G,\mathcal{B})$ that is group-labellable satisfies the following:
4. There does not exist a sequence $W_1,W_2,\ldots,W_k$ of closed walks such that each $W_{i+1}$ is obtained from $W_i$ by rerouting along a balanced cycle and $W_1$ is a simple walk around a balanced cycle and $W_k$ is a simple walk around an unbalanced cycle.
By the argument above, (1) in Theorem 1 implies (4). Using the fundamental group of $K$ we can show that if (3) fail then (4) fails (so (4) implies (3)).
References
[GGW02] J. Geelen, A.M.H. Gerards, and G. Whittle, Branch-Width and Well-Quasi-Ordering in Matroids and Graphs, J. Combin. Theory Ser. B 84 (2002), 270-290.
[M05] D. Mayhew, Inequivalent Representations of Bias Matroids, Combinatorics, Probability and Computing 14 (2005) 567-583.
I’m confused by the last paragraph. If (4) fails then (3) fails, but this means that (3) implies (4), not (4) implies (3), right?
Hi Rohan! You’re right of course, in fact in the proof we show that (1) implies (4), and the fundamental group is used (also) to show that the negation of (3) implies the negation of (4). The mistake is fixed now.
One thing about Theorem 2 seems puzzling. Suppose (G, B) is not group-labellable, but all proper minors are. So there is a contractable unbalanced cycle C in K. The disc D bounded by C must have some edges in it since we only added discs onto balanced cycles. If there is such an edge e whose ends are not both in C, then C is still unbalanced in G/e I think? So that means some cycle inside this disc D must become unbalanced in G/e, otherwise C would be a contractible unbalanced cycle for G/e. But can contracting an edge ever make a new unbalanced cycle?
ps these are very interesting theorems!
I’m not completely sure I understand your argument, but I think that the issue is that the complex on G/e is generally different from the complex obtained by contracting edge e in the complex for G. Contracting edges you may loose balanced cycles (so the complex on G/e may have fewer discs).
In Thm 1, statement 3) itself seems to imply that (G,B) is balanced: if you glue disks on two cycles of a theta, the third cycle will be contractible. So I wonder, what is 3) exactly equivalent to? That no embedding of a planar subgraph of G has exactly one unbalanced face?
Is it possible to test if 3) holds in polynomial time?
Hi Rudi, I’m not sure of what you mean by your comment… if you glue disks on two cycles of a theta, it’s true that the third cycle will be contractible, but the theta property implies that the third cycle of the theta is also balanced (so in fact it has a disc glued onto it).
I don’t know if (3) can be checked in polynomial time: there are potentially exponentially many cycles to check, so my guess would be no.
Hi Irene, what I meant to say is this. Suppose G is a graph and B any subset of its set of circuits. If (G,B) satisfies (3), then (G,B) is balanced. So `balanced’ is just a local version of condition (3).
By `polynomial’, I meant polynomial in the size of the input, which contains B. So if B is very big, it will be trivial to test (3) in polynomial time. If B is small, then perhaps the search for a violation of (3) is quite contained. Certainly one can test if (G,B) is balanced in polynomial time: just consider all pairs from B to see if they span a theta.
Hi Rudi, I think you mean “biased”, i.e. the theta property is satisfied. “Balanced” means that there are no unbalanced cycles. And yes, if you take a graph G and any set of cycles B of G satisfying (3) then (G,B) is a biased graph, as you noticed.
About “polynomial”: usually B is the set of balanced cycles, so if B is small you may have lots of unbalanced cycles to check for (3). Maybe when B is small it would be easier to use (4).
Hi, sorry to interrupt the conversation between you and Irene. I’m pretty sure it’s possible to check if (3) holds in polynomial time. Please correct me if there’s anything wrong with this argument:
If I understand correctly, the question is, given a graph $G$, a set of circuits $B$, and the manifold $K$ defined as in the post, determine whether
(*) there exists a circuit $C$ not in $B$ such that $C$ is contractible in $K$.
Here is the algorithm:
First, as you pointed out we can check every pair of circuits in $B$ to see if they form a theta whose third cycle is not in $B$. So we may assume that $B$ satisfies the theta property.
Consider any two circuits $C_1$, $C_2$ in $B$ whose intersection is a path $P$ with at least one edge. Assume that the discs in $K$ bounded by $C_1$ and $C_2$ have no edges embedded in their interiors.
I claim that (*) holds for $(G, B, K)$ if and only if it holds for $(G – E(P), B’, K’)$ where $B’$ is the set of circuits in $B$ disjoint from $E(P)$ and $K’$ is the surface for $(G-E(P), B’)$.
If $C$ is a circuit of $G$ disjoint from $E(P)$ then it is in $B’$ if and only if it is in $B$.
Any other circuit $C$ of $G$ contains $E(P)$. In this case, $C$ is contractible if and only if $C’ = C \cup C_1 – E(P)$ is contractible. (I’m not completely sure of this claim.)
So we can delete $E(P)$ and by induction solve the problem on $(G – E(P), B’)$ and we’re done.
Next suppose the disc of $K$ bounded by $C_1$ does contain an edge. Then we replace $C_1$ with any circuit embedded in this disc that meets $E(P)$ and bounds a smaller disc.
So we may assume that no two circuits in $B$ share an edge. Then $K$ is a union of discs bounded by circuits in $B$, whose pairwise intersections are disconnected finite sets of points. Any contractible circuit is embedded in such a disc $D$ bounded by a circuit $C$ in $B$, but no circuit embedded in $D$ (other than $C$ itself) can be balanced by the last sentence. So we just have to check if there exists a vertex in the interior of any disc bounded by a circuit in $B$.
Actually, now I think my above comment must be wrong, but it’s too late to edit. If it is true it seems to show that every biased graph satisfies (3).
Hi Rohan, no need to apologise, I’m happy to continue the conversation.
I think your confusion is about the way discs are glued onto cycles. If C is a balanced cycle of G and we glue a disc D onto it, then D only shares its boundary with G. So if C has a chord e, then e only shares its endpoints with D.
Yes, I understand how the discs are glued. It’s still confusing though. Do you know if the following is true or false: If a closed disc $D’$ is the union of a finite number of closed discs that intersect only on their boundaries, then there exist two such discs whose intersection is a line segment.
It looks like it’s true, but topology can be counterintuitive so I’m not sure. If it is true then I can’t find the mistake in the following argument, which must have a mistake because it proves that if $(G, B)$ is a biased graph then every unbalanced circuit is uncontractible in $K$:
Suppose $(G, B)$ is a biased graph, and for each circuit $C$ in $B$, let $D(C)$ be the disc of $K$ corresponding to $C$.
Let $C’$ be an unbalanced circuit that is contractible in $K$. Then $C’$ is the boundary of some disc $D’$. Then $D’$ is the union of some discs $D(C)$; we pick $D’$ so that it is the union of the minimum number of these discs. Since $C’$ is not balanced, this union contains at least two discs $D(C)$. We pick two of these discs $D(C_1)$ and $D(C_2)$ contained in $D’$ whose intersection is a line segment. Then by the theta property, the symmetric difference of $C_1$ and $C_2$, $C_1 \Delta C_2$, is a balanced circuit, so it bounds a disc $D(C_1 \Delta C_2)$. Then the disc $D’ – D(C_1) – D(C_2) \cup D(C_1 \Delta C_2)$ is a disc bounded by $D’$ that is the union of a smaller number of discs, contradicting the choice of $D’$.
Hi Rohan. It’s probably better if I give an example of a small biased graph that is not group-labellabel (this is from Daryl’s talk in Maastricht in 2012). Let G be a 4-cycle, with every edge doubled. Label the edges 1,2,…,8 so that {1,2,3,4} and {5,6,7,8} are 4-cycles and the parallel pairs are {1,5}, {2,6}, {3,7} and {4,8}. Now declare the balanced cycles to be {1,2,3,4}, {1,2,7,8} and {3,4,5,6}. No two balanced cycles form a theta, so this is a biased graph. Now in the complex arising from this biased graph the cycle {5,6,7,8} is contractible (but it’s not balanced). I think the problem is your first claim, since in this example all the balanced cycles are Hamiltonian (and the same is true in our infinite families of examples).