Hi Mike,

You asked: “[w]hat is the analog of tree-width for finite permutation groups? This should have an answer. And the answer should be fairly obvious/deducible (Cf Grothendieck) from the right abstract point of view.“

This blog post is part of my correspondence with Mike Fellows. I’m posting it here for three reasons: (1) I needed LaTeX support (email just wouldn’t cut it), (2) the discussion is of general interest and (3) my answer involves notes that I had been intending to share on this blog for a while.

I think the answer should be structured co-decompositions. They’re things that look like this:

Let me explain.

You start by taking a tree \(T\) and you assign:

• to each node \(t \in VT\) a (finite) group \(G_t\)
• to each edge \(e = st \in ET\) a (finite) group \(G_e\) and a pair of surjective group homomorphism \(f_s^e \colon G_s \to G_e\) and \( f_t^e \colon G_t \to G_e\).

You call this resulting structure a tree co-decomposition of a group \(G\) if \(G\) arises by recursively taking fibered products of the groups assigned to the nodes of \(T\) over the groups assigned to the edges of \(T\).

For anyone reading who might not recall, what a fibered product is, here’s the definition: “a fibered product (or pullback) of two group homomorphisms \(f_1 \colon G_1 \to H\) and \(f_2 \colon G_2 \to H\) is the subgroup of \(G_1 \times G_2\) given by the elements \(\{(x,y) \mid f_1(x) = f_2(y)\}\).)

Now you might ask: “why on earth is this an analogue of tree-width for groups?“

The short answer is that the structure I defined above is an instance of a structured decomposition. These are category-theoretic generalizations of graph decompositions that I introduced a little while ago with Zoltan Kocsis and Jade Master. You can read about them in one of my older blog posts or in our paper. Since structured decompositions generalize tree decompositions of graphs, structured decompositions of groups are the natural group-theoretic analogue of graph decompositions.

But now I’m expecting some hesitation in you: I started off by saying that structured co-decompositions were the right choice, but then I spoke about structured decompositions without the “co“. So you’re probably asking yourself: “why the ‘co‘? What does that even mean?”

It’s a great question. First off let’s talk about what the “co” is doing. As usual in category theory, sticking a “co” in front of a word indicates that we’re invoking categorical duality. In this particular case we’re invoking duality on the category of objects we’re wanting to decompose: a structured co decomposition of groups is a structured decomposition in \(\mathsf{Grp}^{op}\) (i.e. the category you get by inverting the domain and codomain of all the morphisms in the category of groups and group homomorphisms). Since I didn’t give the actual category theoretic definition of a structured decomposition in this post, perhaps it’s best to unpack things a little.

First of all, what’s a structured decomposition of groups? Well, it turns out (as I found about a year after Zoltan, Jade and I wrote our paper) that group-valued structured decompositions were already studied by Hyman Bass and Jean-Pierre Serre under the name of graphs of groups. These are useful tools in geometric group theory and are defined as follows: you pick a graph \(G\) and you assign groups to each of its vertices and edges and then you assign injective group homomorphisms \(G_e \to G_x\) from each edge-group \(G_e\) to each vertex-group \(G_x\) whenever \(x\) is a vertex incident with \(e\). You’ll notice that this is exactly what you get when you “flip the directions of all the edges” in the definition I gave at the beginning of this post.

So why am I not advocating to use graphs of groups (i.e. structured decompositions of groups) as analogues of tree decompositions for graphs? There are two reasons, let me explain.

First of all, Mike, you’re asking about decomposing finite groups. And if you want to do this, graphs of groups just won’t cut it: you say that a group \(G\) is decomposed by a group-valued structured decomposition \(d\) if the colimit of \(d\) is \(G\). (Sacrificing a bit of formality in favor of more group-theoretic terminology, a colimit of groups is what you get when you do a bunch of free products with amalgamation.) So why is this not what we want? Well because in general colimits of finite groups are infinite.

However, if you start with finite groups and you take limits (think “fibered products”) then you end up with a finite group. This is the first reason why structured co-decompositions of groups are better group-theoretic analogues of (tree) graph decompositions of groups.

The second reason for preferring co-decompositions has to do with the kinds of applications we might have in mind. You and I like algorithms, obviously, and I’m guessing you’re asking about group decompositions because you have some neat algorithmic tricks lurking in your mind… so let me give just a hint as to why I suspect co-decompositions are the right choice in this setting.

The first thing to have in mind is my paper with Ernst Althaus, Daniel Rosiak and James Fairbanks about solving decision problems that are encoded as sheaves. The idea is that a computational problem should be a contravariant functor from your category of inputs (e.g. Graphs) to your category of solution spaces (e.g. Sets): the functor maps each input to its set of solutions. Mike this is the stuff I spoke about at FPT fest in Norway (for anyone else reading this, you can see a recording of a more category-theoretic version of the talk on YouTube).

The reason the contravariance is relevant to us is that, if you think of solution spaces not as sets, but instead as groups (where the idea is to exploit the symmetries in the solution space), then computational problems naturally take graph decompositions to co-decompositions of groups!

I have a lot more to say, about this. For instance one important thing I’d like to highlight is that I think that, although group decompositions are interesting, I think that groupoid decompositions are more interesting still. There are many reasons to say this (ranging from the deeply philosophical, to the very practical), but I guess that the one-liner idea is that encoding graph isomorphism as a contravariant functor naturally lands you in groupoids, not in groups…

…unfortunately Mike I’m about to be late for the category theory class I’m teaching, so I have to wrap up this post and perform a disappearing act. I’ll talk to you soon (and thanks for putting up with my slow reply; life’s been hectic lately!)

Cheerfully,

Ben