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.

## 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!).