# Serre’s Graphs and Trees

I think this is the last Vast Branch of Mathematics I need to include before heading right into Rimlinger, but who knows? The Bass-Serre theory of fundamental groups of graphs of groups (fgoagogs!) is a very appealing way of representing constructions like free products with amalgamation and HNN extensions, where you create bigger groups by identifying subgroups of ones you’ve already got. Or the other way round; FPAs and HNN extensions are the building blocks of Bass-Serre theory. Whatever.

## Graphs

Serre formulates graphs a little bit differently to the usual.

A tree \(\Gamma\) is a set \(B\) of vertices (a.k.a. *bases*) and a set \(E\) of edges, with two maps,

\[ \begin{array}{ccc} E \rightarrow B \times B, && e \mapsto (\iota (e),\tau (e)) \end{array} \]

associating each edge with its initial and terminal vertices, and

\[ \begin{array}{ccc} E \rightarrow E, && e \mapsto \overline{e} \end{array} \]

an inversion on the edges, which must satisfy the condition that for each \(e in E\) we have \(\overline{\overline{e}}=e\), \(e \neq \overline{e}\) and \(\iota (e) = \tau (\overline{e})\).

An *orientation* of a graph \(\Gamma\) is a subset \(E_+ \subset E\) such that \(E\) is the disjoint union of \(E_+\) and \(\overline{E_+}\). What that means is that every edge either belongs to \(E_+\) or its inverse does.

Serre loves categories like mad, so I’m unable to talk about the realisation of a graph properly, but it’s basically a topological space which looks like the graph.

“connected”, “path”, and “circuit” have the usual meaning, plus wafflery.

## Trees

A tree is a connected, non-empty graph with no circuits. A *geodesic* in a tree is a path without backtracking. There is exactly one geodesic between any two vertices in a graph and it never visits the same point twice.

A *maximal tree* of a graph \(\Gamma=(B,E)\) is a subtree \(T\) which contains all of \(B\) (every vertex).

## Graphs of groups

Let \(Gamma= (B,E)\) be a connected graph, and suppose

- A set of vertex groups, \(\mathbf{G} = \{G_v\) for each vertex \(v \in B \}\), so that each vertex has a group associated with it,
- A set of edge groups, \(E_e\) for each \(e \in E\), so that each edge has a group associated with it, and \(E_e = E_{\overline{e}}\),
- A set of group monomorphisms (injective homomorphisms, so the range is the same size as the domain) \(\phi_e: E_e \rightarrow G_{\tau(e)}\), called the
*edge maps*. For convenience, instead of \(\phi_e\) we will write \(\beta\), and instead of \(\phi_{\overline{e}}\) we will write \(\alpha\), where it is obvious which edge we’re talking about.

All of this together is a graph of groups, written \((\mathbf{G},\Gamma)\). The idea is that you’ve got all these groups stuck to this graph, and you can move around between vertices by using the edge maps.

An edge map sends an entire edge group to a subgroup of the vertex group it is attached to, which is like what happens in free products with amalgamation and HNN extensions. Suppose we have a graph consisting of two vertices \(v_1\) and \(v_2\) connected by an oriented edge \(e\) and its inverse \(\overline{e}\) . So we have two vertex groups \(G_2\) and \(G_2\), an edge group \(E_e = E_{\overline{e}}\), and two edge maps \(\alpha: E_e \rightarrow G_1\), and \(\beta: E_e \rightarrow G_2\). Now, \(\alpha\) maps \(E_e\) isomorphically to a subgroup \(H_1 leq G_1\) and \(\beta\) maps \(E_e\) isomorphically to a subgroup \(H_2 \leq G_2\). By restricting the edge maps to \(H_1\) and \(H_2\), we can create an isomorphism \(\psi = \alpha^{-1}\beta\) between \(H_1\) and \(H_2\).

So this graph represents the conditions needed for a free product with amalgamation – we have two groups with subgroups which are isomorphic. Similarly, a graph with a single vertex and a loop connecting it to itself looks a lot like an HNN extension, minus the stable letter. This leads us to:

## The fundamental group of a graph of groups

Let \((\mathbf{G},\Gamma)\) be a graph of groups and \(T\) a maximal tree of \(\Gamma\). Let \(E\) be the edges of \(\Gamma\) and \(E(T)\) the edges of \(T\). Finally, let \(X\) be an orientation of \(E – E(T)\) (all the edges not in the maximal tree).

The *fundamental group* of \((\mathbf{G},\Gamma)\) is

\(\pi_1(\mathbf{G},\Gamma,T) = F(X) \underset{G \in \mathbf{G}}{\ast} G / \ll R \gg\)

where \(R\) is the set of relations

\(R = { \alpha (a) = \beta (a) | t \in E(T), a \in E_t } \cup { x^{-1} \alpha (a) x = \beta (a) | x \in X, a \in E_x }\)

What that means is that the fundamental group is constructed out of:

- \(F(X)\) is the free group generated by \(X\), so one generator for each edge not in the maximal tree,
- \(\underset{G \in \mathbf{G}}{\ast} G\) means the free product of all the vertex groups,
- then the relations \(R\) are added (the subgroup generated by \(R\) is quotiented out). For each edge in the maximal tree, there is a set of relations identifying the associated subgroups (like in a free product with amalgamation), and for each edge not in the maximal tree there’s a similar set of relations but conjugated by the generator for that edge, like the stable letter an HNN extension.

This construction gives us something which has free products with amalgamation and HNN extensions as simple cases, but can be extended much further.

## References

*Trees* by J.P. Serre

## Comments

## Comments

Joseph Cooper

Do you know about the other construction of the fundamental group, using a base point?

It’s very similar to the fundamental group in algebraic topology, using homotopy classes of loops, but also including the vertex and edge groups (obviously! pointless without this bit). It gives you an isomorphic group to the construction you’ve given, but the bit I like is that a different choice of basepoint gives you an isomorphic group and it’s very easy to actually write down the isomorphism. I don’t think this is as easy with the construction by spanning trees, but I suppose that might not matter for your uses. Just thought I’d mention it.

cp

Well I’d assumed that was a way of doing it because of the name, but no I’ve never seen it written down. To be honest I can only stand Serre’s book for small periods of time. I’m a computer scientist really, don’t tell anybody.

Nathan has just sent me Higgins’ paper on the normal form theorem for the fundamental groupoid of a graph of groups, which now I look I can see it mentions the basepoint formulation.

Thanks for being my first commenter as well!