I have a new paper up! It's about "one-endedness" and "semistability at infinity" of certain outer automorphism groups of free products; more about this almost certainly soon. What I want to talk about today is an algorithmic process I wanted to include in the paper but was unable to provide a proof of its correctness. The statement that I needed was that a certain collection of subforests of a graph (with special vertices—this is a graph of groups) forms what's called a matroid. This is true, but I wanted a concrete method for proving it. If you're out there reading and now how to finish the proof, I'd love to see it.
Table of Contents
1. Matroids
A nonempty (typically finite) set \(S\) is called a matroid when it is equipped with the following extra structure: a certain (nonempty) collection of finite subsets of \(S\) are called bases. Bases satisfy the exchange property, which says that if \(A\) and \(B\) are bases, then for any element \(a\) in \(A\) but not in \(B\), there is an element \(b\) of \(B\) not in \(A\) such that swapping \(a\) for \(b\) yields a new basis \(A - \{a\} \cup \{b\}\).
The first basic example to keep in mind is the set of bases for a vector space of finite positive dimension: indeed, something that appears slightly stronger on the surface is true: a subset of the vector space has a notion of (linear) independence; a basis is just a maximal independent set. If you have an independent set \(A\) and another \(B\), and \(B\) has more elements than \(A\), then in fact some element of \(B\) may be added to \(A\) while still preserving independence. If you know some linear algebra, prove this!
1.1. The matroid of spanning trees
The other basic example of a matroid is the collection of spanning trees in a finite, connected graph. Graphs, let's remember, are things with vertices and edges. A graph is a tree when it has no embedded circles: there is only one way to travel from point \(a\) to point \(b\) without backtracking. A maximal or spanning tree in a graph is a subgraph which is a tree and which contains every vertex of the graph. For finite graphs, there are algorithms that produce spanning trees. For infinite graphs, the existence of a spanning tree is equivalent to the axiom of choice.
Anyway, let's prove that the collection of spanning trees forms a matroid. Suppose \(F\) and \(F'\) are two spanning trees in the graph \(G\), and let \(e\) be an edge of \(F\) not in \(F'\). Since \(F\) was a tree, removing \(e\) disconnects it into two components, say \(F_1\) and \(F_2\). Since \(F'\) visits every vertex, there is a path in \(F'\) from one endpoint of \(e\) to the other. It follows that some edge (in fact an odd number of edges that can be greater than one) connects \(F_1\) to \(F_2\). Any such edge will do as \(e'\). In fact, if \(e\) belongs to \(F'\) as well, then this process makes sense too: it just gives back \(e\).
Notice that if we repeat this argument, we may interpolate from \(F\) to \(F'\) through spanning trees at each step. It was this latter property that I needed for my application, so I proved in my paper a slightly back-to-front formulation of the exchange condition: given an element \(b\) of the basis \(B\) not in the basis \(A\), there is an element \(a\) of \(A\) not in \(B\) such that \(A \cup \{b\} - \{a\}\) is a basis. It's not obvious to me whether this axiom is equivalent to the one I stated above with the quantifiers reversed, but in my case it's not hard to see that both hold; let's talk about it.
1.2. The matroid of maximal forests
Suppose now our graph \(G\) is equipped with \(n\) special vertices. A maximal forest in such a graph \(G\) is a forest (so a disjoint union of trees) with the property that each component of the forest contains at most (and actually exactly) one special vertex. Supposing that \(G\) has more than \(n\) vertices, let us show that the collection of maximal forests in \(G\) satisfies the "reverse" matroid axiom: given \(F\) and \(F'\) forests and \(e'\) an edge of \(F'\) not in \(F\), since \(F\) was maximal, \(F \cup \{e'\}\) is not a maximal forest, either because it is not a forest because some component contains an embedded circle or because some component contains two special vertices. In fact, the new edge \(e'\) belongs to the core of \(F \cup \{e'\}\), namely that embedded circle in the former case or the unique path between the two special vertices in the latter. Since \(F'\) is a maximal forest, this core cannot be entirely contained in \(F'\), so it contains an edge of \(F - F'\), any such edge will do as \(e\).
2. Algorithms
I was slightly unsatisfied with this proof: in the case of two spanning trees \(F\) and \(F'\), one just needs to compute the geodesic in \(F'\) between the edges of \(e\) and then ask each edge of that geodesic whether it connects to two complementary components. This feels a bit more constructive than the existence proof we gave above.
Here is my proposed algorithm. Given two maximal forests \(F\) and \(F'\), complete them to spanning trees \(\bar F\) and \(\bar F'\) by adding sets of edges \(T\) and \(T'\). Consider the graphs \(H\) and \(H'\) obtained by collapsing each component of \(F\) or \(F'\) respectively to a vertex. Since \(F\) and \(F'\) were maximal, each vertex of \(H\) or \(H'\) corresponds to a unique special vertex of \(G\). The edges of \(T\) and \(T'\) descend to spanning trees of \(H\) and \(H'\) respectively. Form a new graph \(\Gamma\) by gluing \(H\) and \(H'\) along their vertices, where each vertex \(v\) in \(H\) is glued to the unique vertex \(v'\) in \(H'\) with the property that \(v\) and \(v'\) correspond to the same special vertex of \(G\).
Run the spanning tree swap algorithm on \(\Gamma\). This yields a bijection \(\Phi \colon T \to T'\) with the property that if \(T\) has \(k\) edges \(e_1,\ldots,e_k\), the collection of edges \(\{\Phi(e_1),\ldots,\Phi(e_\ell),e_{\ell+1},\ldots,e_k\}\) is a spanning tree in \(\Gamma\) for each \(\ell\) satisfying \(1 \le \ell \le k\).
Run the spanning tree swap algorithm on \(G\) with respect to \(\bar F\) and \(\bar F'\). For definiteness, maybe it makes sense to assume that edges of \(T\) in \(\bar F\) precede edges of \(F\). This produces a bijection \(\Psi\colon \bar F \to \bar F'\) with similar properties to \(\Phi\). Now if it were the case that \(\Psi\) sends \(T\) to \(T'\), we would be done, but this is not the case in general. Instead we define a new bijection \(\Theta \colon F \to F'\) and claim (this is what I'm unable to prove in general) that it has the property similar to \(\Phi\) above.
Suppose \(e\) is an edge of \(F\) which is sent into \(T'\) by \(\Psi\). Then it makes sense to consider \(\Psi\Phi^{-1}\Psi(e)\). Either this edge is in \(T'\) or not. The maps \(\Psi\) and \(\Phi\), being bijections, have very simple dynamics; in particular, it is not possible for an edge like \(e\) to be "trapped" into a loop of edges in \(T'\) forever. Therefore we may repeatedly apply \(\Psi\Phi^{-1}\) some finite number of times until we reach an edge of \(F'\); call it \(\Theta(e)\). If \(\Theta = (\Psi\Phi^{-1})^k\Psi\) for some \(k \ge 0\) on \(F\), we may define it on \(T\) as \(\Psi\) when \(\Psi\) sends the edge of \(T\) into \(T'\) and as \(\Psi\Theta^{-1}\Psi = (\Phi\Psi^{-1})^{k-1}\Phi\) otherwise. Actually this latter definition makes sense in all cases.
2.1. Some observations
I'll conclude with one particularly simple, but illuminating example.
In the figure there is a graph with three special vertices and one other vertex. The special vertices are labeled \(A\), \(B\) and \(C\). The vertices \(A\) and \(B\) have valence two, while \(C\) and the unlabeled vertex have valence three. \(A\) and \(B\) are both connected to each of \(C\) and the unlabeled vertex. There are two spanning trees: one highlighted in blue containing the edges from \(A\) and \(B\) to the unlabeled vertex and from \(A\) to \(C\), and one highlighted in yellow containing the edges from \(A\) and \(C\) to the unlabeled vertex and from \(B\) to \(C\). These spanning trees contain one-edge maximal forests: in the blue spanning tree the maximal forest I have chosen is the edge from \(B\) to the unlabeled vertex, while in the yellow spanning tree the maximal forest is the edge from \(C\) to the unlabeled vertex.
There is only one possibility for \(\Psi\), and for \(\Phi\). Interestingly, \(\Phi\) does not send the edge from \(A\) to the unlabeled vertex, which belongs to both trees, to itself. The bijection \(\Psi\), going from yellow to blue, sends the unique edge \(e\) in the maximal forest to the edge from \(A\) to \(C\). This edge is not in \(F'\), and neither is \(\Psi\Phi^{-1}\) of it, which is the edge from \(A\) to the unlabeled vertex. The bijection \(\Phi^{-1}\) sends this edge to the edge from \(B\) to \(C\), and finally one more application of \(\Psi\) sends this edge to the edge from \(B\) to the unlabeled vertex, which is in the maximal forest \(F'\).
Thus in this, and indeed in all examples I've tried, \(\Theta\) correctly interpolates through maximal forests. Interestingly, it suffices to consider planar graphs, since edges outside the spanning trees are irrelevant to the consideration, and a graph which is the union of two spanning trees is always planar (prove this!).