Towards the end of May I visited Johannes Carmesin‘s group at the University of Birmingham. I was there to work with Will Turner on obstructions to compositionality and their categorification.

I had an absolute blast. Will and I proved a bunch of new results and this post is about one of them: I’ll tell you how to deifne tree decompositions in terms of lattices of subgraphs. I think that it’s a cute result in of itself, but also that it will have profound consequences in the future. If you’re interested, Will has written a pair of posts about separations and fracturings of objects of a category; you can read about these things on his blog here and here.

The post should be relatively self-contained and it’ll consist of three main parts. First I’ll start by explaining tree decompositions at a high level and I’ll define them in terms of structured decompositions. (I’ll do this for two reasons: this more abstract definition is cleaner and we’ll need it later anyway.) Then I’ll explain our result for graphs and finally I’ll note how this generalizes to all kinds of other cool categories.

1. Tree decompositions

Tree decompositions (and the associated notion of tree-width) are fundamental tools in structural graph theory. Roughly they witness the global connectivity of a graph: in order to make sense of how connected a graph is, you don’t simply want a single vertex cut, but instead you need many such cuts which are nicely nested. Here’s an example.

The tree-width of a graph measures how “decomposable” a given graph is; it is defined for a graph \(G\) as the minimum over all tree decompositions of \(G\) of the maximum size of the constituent parts of the decomposition.

Tree decompositions have been around for a while now. To the best of my knowledge they were first introduced by Bertelé and Brioschi in 1972 and then independently defined by Halin in 1976 and then by Robertson and Seymour in 1986. It’s interesting to see the same notion redefined multiple times (well, actually tree-width has many more cryptomorphic definitions, but we won’t get into that here..) and with three different mathematical goals: the first was focused on algorithmic compositionality, the second was interested in graph invariants similar to Hadwiger’s number and the modified chromatic and connectivity numbers and the third was motivated by topological questions (namely Wagner’s conjecture – which is now a Theorem!).

As I promised you earlier, I’ll give you a definition of tree decompositions now, but I’ll do it in terms of structured decompositions. These are much more general, but they require a little category theory to state properly. Don’t worry though: I’ll give the definition in such a way that you won’t need to know any category theory (at least not until section 3 of this post).

A monic structured decomposition is a bit like a generalized graph: it consists of a collection of objects of a category (think graphs or sets) and a collection of monic spans acting as generalized relations between the objects (FYI, for graphs, a monic span is just a pair of injective graph homomorphisms which have the same domain). Here’s a picture of a structured decomposition of graphs.

Df. Fix a graph \(G\) and a category \(\mathsf{C}\). A \(C\)-valued structured decomposition of shape \(G\) is a functor \(d\) of the form $$d \colon \int G \to \mathsf{C}$$ where \(\int G\) is the category obtained from \(G\) by making a the vertices and the edges of \(G\) into objects of \(\int G\) and which has a morphism from each edge-object to both of its endpoints (and identity arrows, naturally). For any vertex \(v\) and any edge \(e = xy\) in \(G\), we call the object \(d(v)\) a bag of \(d\), we call the object \(d(e)\) an adhesion of \(d\) and we call the span \(d x \leftarrow d e \rightarrow d y\) an adhesion span in \(d\). We say the decomposition is monic if \(d(f)\) is a monomorphism for each morphism \(f\) in it’s domain. Suppose \(\mathsf{C}\) has colimits, then, given an object \(c \in \mathsf{C}\), we say that

• (D) the decomposition \(d\) decomposes \(c\) if \(\mathsf{colim}(d) = c\).

If you don’t know what a colimt is, don’t worry: just think about it as “gluing”. For instance the colimit of a monic span \(G_1 \leftarrow H \rightarrow G_2\) of graphs is the graph obtained by gluing \(G_1\) to \(G_2\) along their shared subgraph \(H\) (specifically we glue thew two graphs along the images of \(H\) under \(f_1\) and \(f_2\) where these are the morphisms in the span.).

Since I’ll be only speaking about monic decompositions in this post, I’ll drop the adjective and simply refer to a monic structured decomposition as a structured decomposition (or even just “decomposition”).

With this definition in mind, what’s a tree decomposition?

A tree decomposition is a tree-shaped \(\mathsf{Gr}\)-valued structured decomposition (where \(\mathsf{Gr}\) is the category of reflexive, simmetric graphs).

P.S. I don’t really care which category of graphs you choose, as long as it’s defined as a C-set category, everything I’ll tell you below will work.

Just to make sure we’re on the same page, let me spell out what a tree decomposition of a graph \(G\) is. You start with a tree \(T\), then you build a category \(\int T\) from it by making a span for each edge of \(T\) (as I explained ealier). Here’s a picture.

Then you choose a graph for each object of \(\int T\) and an injective graph homomorphism for each morphism of \(\int T\); i,e. you define a functor \(d \colon \int T \to \mathsf{Gr}\). This is a tree decompostion, but we only say that it decomposes the graph \(G\) if, when we glue together all of the graphs in the bags of the decomposition along the shared subgraphs in the adhesions, we obtain the graph \(G\).

2. Tree Decompositions via Lattices

Fix a graph \(\Gamma\) throught this section. To any such graph we can associate a poset \(\mathsf{Sub} \Gamma\) whose elements are subgraphs of \(\Gamma\) ordered by inclusion. Formally this is a special case of subobject poset \(\mathsf{Sub} c\) which is a construction which works on any category \(\mathsf{C}\) and for any object \(c\) therein. It’s defined as the category consisting of the following data:

• Objects: these are monomorphisms \(d \to c\) into \(c\).
• Morphism: these are commutative triangles of monos.

Notice that for graphs, the subobject poset comes equipped with infima and suprema and these distribute over eachother. In other words, this means that \(\mathsf{Sub} \Gamma\) is a distributive lattice. This is all we need to get the definition of a tree decomposition in terms of the subobject lattice.

Df. let \(\delta \colon \Delta \to \mathsf{Sub} \Gamma\) be a subposet of \(\mathsf{Sub} \Gamma\). We call \(\delta\) a weak tree pre-arrangement if for all \(x, y, z \in \Delta\) the following holds:

• (WTPR) if \(\delta x \land \delta y \neq \bot\) and \(\delta y \land \delta z \neq \bot\) then \(\delta x \land \delta y \land \delta z = \delta x \land \delta z\).

We say that \(\delta\) is a weak tree arrangement if it is a pre-arrangement which also satisfies the following condition:

• (TR) for all \(x \in \mathsf{Sub} \Gamma\), there exists a subposet \(\delta’ \colon \Delta’ \to \Delta\) such that \(x \leq \bigvee_{x’ \in \Delta’} \delta \delta’ x’\).

Admittedly, since we’re in a lattice, condition (TR) might look weird since taking \(x = \top\) implies that \(\top \leq \bigvee_{y’ \in \Delta’} \delta \delta’ y’ \leq \bigvee_{y \in \Delta} \delta y\) and hence that \(\bigvee_{y \in \Delta} \delta y = \top\) (in other words it says that we chose a bunch of subgraphs whose union is the whole graph… compare this to condition (D) of the definition of a structured decomposition). I stated point (TR) in this obfuscated way because I’m hoping to something neat with it in the future, so don’t worry about it. Anyway, after all this, here’s the proof I promised you.

Proposition. Given any tree decomposition \(\tau \colon \int T \to \mathsf{Gr}\) of a graph \(\Gamma\), the bags of \(\tau\) determine a weak tree arrangement. Conversely, every weak tree arrangement of \(\Gamma\) determines a tree decomposition.

Proof. Take any three bags \(\tau x, \tau y, \tau z\) in \(\tau\). Notice that the fact that \(\mathsf{colim} \tau = \Gamma\) (together with the observation that, given any diagram of monos in the category of graphs, its colimit cocones also consists of monos) implies that \(\tau x, \tau y, \tau z\) are subobjects of \(\Gamma\). Now suppose that \(\tau x \land \tau y \neq \bot\) and \(\tau y \land \tau z \neq \bot\). Clearly we always have that \(\tau x \land \tau y \land \tau z \leq \tau x \land \tau z\), so we have to show that, if \(w \in \tau x \land \tau z\), then we also have \(w \in \tau y\). To see this, observe that, since \(T\) is a tree and since \(\mathsf{colim} \tau = \Gamma\), the only way to have \(\tau x \land \tau y \neq \bot\) and \(\tau y \land \tau z \neq \bot\) is for \(y\) to lie on the unique path from \(x\) to \(z\) in \(T\) (if not, then you’d get a cycle). But then notice, since \(\mathsf{colim} \tau = \Gamma\), we must have \(w \in \tau y\) as deisred.

For the converse direction, take a weak tree arrangement \(\delta \colon \Delta \to \mathsf{Sub} \Gamma\). The naïve approach is to just make a structured decomposition for \(\Gamma\) by taking pairwise intersections between the elements of the tree ararngement (notice, as we did earlier, that condition (TR) implies condition (D)). However, if you do this, you’ll likely end up with a structured decomposition $$d_0 \colon \int G_0 \to \mathsf{Gr}$$ which isn’t tree-shaped. We’ll see that this is just a superficial issue since there is a way of “uncycling” the decomposition in what follows (this will then conclude the proof). Suppose we have elements \(x_1, \dots, x_n\) in \(\Delta\) which give rise to a cycle in \(d\); i.e. such that \( x_n \land x_1 \neq \bot \) and \( x_i \land x_{i+1} \neq \bot \) for all \(1 \leq i < n\). Then obseve that condition (WTPR) implies that \(\delta x_i \land \delta x_j = \delta x_k \land \delta x_\ell\) for all distinct \(x_i, x_j, x_k\) and with \(x_\ell\) distinct from \(x_k\). Thus we have shown that \(x_i \land x_j = \bigwedge_{k \in \{1, \dots, n\}} x_k\) (for dinstinct \(x_i, x_j\)) and thus that any cycle in \(d\) actually also contains a wheel where the spokes are centered at \(\bigwedge_{k \in \{1, \dots, n\}} x_k\). We will use this to make a new decomposition \(d_1\) from \(d_0\) as follows. Let \(G_1\) be the graph obtained from \(G_0\) (where \(G_0\) is the shape graph of \(d_0\)) by removing all the edges joining any two vertices in the cycle \(x_1 \dots x_n\) we were just considering and then adding a star centered at a new vertex \(w_1\) and with \(x_1, x_2, \dots, x_n\) as its leaves. Thus define \(d_1 \colon \int G_1 \to \mathsf{Gr}\) by letting \(d_1(x) = d_0(x)\) for all \(x \in G_1 \cap G_2\) and setting \(d_1(w) = \bigwedge_{k \in \{1, \dots, n\}} x_k\) and associating to each edge \(wx_i\) of the star centered at \(w\) the trivial adhesion \(\bigwedge_{k \in \{1, \dots, n\}} x_k \leftarrow \bigwedge_{k \in \{1, \dots, n\}} x_k \hookrightarrow x_i\). From what we argued before (namely that \(x_i \land x_j = \bigwedge_{k \in \{1, \dots, n\}} x_k\)) we have that \(\mathsf{colim} d_1 = \mathsf{colim} d_0 = \Gamma\). The plan is to show that \(G_1\) has strictly fewer cycles than \(G_0\); the result will then follow since it implies that by continuing this process \(d_0, d_1, \dots \) we will eventually (in a finite number of steps since \(G_0\) is finite) reach a acyclic decomposition, as desired (note that I’m not distinguishing between trees and forests..). This is the following claim.

Claim: let \(H\) be the graph obtained from \(G\) by replacing a clique on the vertices \(x_1, \dots, x_n\) with a star with center \(w\) and leaves \(x_1, \dots, x_n\). Then there is an injection \(|\{C \mid C \text{ is a cycle in } H\}| < |\{C \mid C \text{ is a cycle in } G\}|.\)
Proof: There is an injection $$f \colon \{C \mid C \text{ is a cycle in } H\} \hookrightarrow \{C \mid C \text{ is a cycle in } G\}$$ defined as follows. For any cycle \(C\) in \(H\), if \(C\) uses no edges of the star centered at \(w\), then \(C\) is also a cycle in \(G\) so let \(f\) take \(C\) to `itself’ in \(G\). Otherwise, \(C\) must use precisely two edges of the star — w.l.o.g. let these be \(x_1 w\) and \(w x_2\) — so, since \(x_1, \dots, x_n\) was a clique in \(G\), we can map the cycle \(C\) the cycle \(C – \{x_1 w, w x_2\} +\{x_1x_2\}\). Completing the proof, observe that some cycles of \(G\) (e.g. those that more than one edge of the clique on the vertices \(x_1, \dots, x_n\) ) are not in the image of the injection \(f\). Thus \(|\{C \mid C \text{ is a cycle in } H\}| < |\{C \mid C \text{ is a cycle in } G\}|\), as desired.

My sense of aethetics tell me that it would be ideal if we could change the definition of a weak tree (pre-) arrangement so as to make sure that it consist of a downwards-closed sub poset. It turns out this is possible (giving rise to what I’ll call tree pre-arrangements and tree arrangements) so I’ll include this definition below.

3. A small note on generalizing these ideas

Notice that the only assumptios we used above were:

• that pushouts of monos exist and are monos
• that the subobject lattice has pullbacks (i.e. that pullbacks of monos exist)
• that, taking the supremum in the subobject lattice to be defined as a pushout over a pullback of monos, the lattice becomes a distributive lattice.

With a list of requirements like this, my friend Paweł Sobociński would imediately exclaim: “you shouldn’t be working with graphs, you should be working with adhesive categories”. Obviously Paweł would be correct in saying this and indeed averything I just mentioned works in any adhesive category.

---

Anyway, that’s all for today; see you next time!

Cheerfully,

Ben