Emilio Minichiello recently gave a woderful talk at the at the New York City Category Theory Seminar all about some results of mine (joint with Ernst Althaus, Daniel Rosiak and James Fairbanks) concerning dynamic programming and sheaves. Since many students and colleagues have asked me for recordings of my lectures on this subject and since I invariably turn up empty handed and covered in chalk, I’m very excited to now be able to point everyone to Emilio’s talk. If you’re interested, you can find the recording here.

My good friend Zoltan Kocsis and I finally got our paper “Degree of Satisfiability in Heyting Algebras” published in the Journal of Symbolic Logic. Yay! Since Zoltan is half-way across the world, we can’t grab a beer together and celebrate, so instead here’s a celebratory blog post (you can find the ArXiv version of our paper here).

Let’s start with a fun question about groups:

Let \(G\) be a finite group, for uniformly and independently chosen elements \(x\) and \(y\) in \(G\), what the the probability that \(x\) and \(y\) commute?

In other words we ask: what is the value of $$\mathsf{ds}_G(xy= yx) := \frac{|\{(x,y) \mid x, y \in G \text{ and } xy = yx\}|}{|G|^2}?$$

The answer is well-known: either \(G\) is Abelian, in which case \(\mathsf{ds}_G(xy= yx) = 1\), or \(G\) is not Abelian and one has \(\mathsf{ds}_G(xy= yx) \leq 5/8\).

This was first shown by Erdős and Turán and and later generalized by Gustafson. The result for finite groups is not hard and I recommend John Baez’s wonderful blog post about this, if you want to learn the proof.

Framing this result a bit more conceptually, it is asking: how close can a group be to being Abelian without actually being Abelian? Clearly one can ask this kind of question about any mathematical structure and indeed this falls into the more general setting of determining the degree of satisfiability of some property \(p\) in some finite structure \(M\); in other words one asks: “what is the probability that uniformly chosen elements of \(M\) satisfy \(p\)?” Formally it is defined as follows.

Def: Take a first-order language \(\mathcal{L}\), a finite \(\mathcal{L}\)-structure \(M\), and an \(\mathcal{L}\)-formula \(\varphi(x_1,\dots,x_n)\) in \(n\) free variables. We call the quantity
$$ \frac{ | \{ (a_1, \dots, a_n) \in M^n \mid \varphi(a_1, \dots, a_n) \} | }{ | M | ^n }$$
the degree of satisfiability of the formula \(\varphi\) in the structure \(M\), and denote it \(\mathsf{ds}_M(\varphi)\). One says that a formula \(\varphi\) has finite satisfiability gap \(\varepsilon\) for \(0 < \varepsilon < 1\) if for all \(M\) either \(\mathsf{ds}_M(\varphi\) = 1\) or \(\mathsf{ds}_M(\varphi) \leq 1 – \varepsilon\).

For groups there are many results establishing such finite satisfiability gaps. Some of these were developed by my friend Zoltan in his paper “Degree of Satisfiability of Some Special Equations” which is also where the terminology “degree of satisfiability” comes from. But what’s particularly interesting is the sheer quantity of known gap results (see our paper for pointers for further reading); indeed, as of now, the existence of an equation in the language of group theory that does not have finite satisfiability gap remains open. This is even in the case of equations in only one free variable; for example only partial results about finite satisfiability gaps are known for the equation \(x^p = 1\) for any \(p\) at least five.

Why Heyting Algebras?

Having said all this, it looks like the story for groups gets quite hard rather fast, so what about other structures? This is exactly what Zoltan asked me when he approached me about working on this topic. We studied Heyting Algebras and hopefully you’re now asking yourself: “why Heyting algebras?”. The answer is that the choice was motivated by both practical concerns and philosophical ones. On the practical side, Zoltan suspected that interaction of algebraic and order-theoretic structure would be helpful for our purposes; this was overwhelmingly true. On the philosophical side, studying degree of satisfiability in Heyting algebras lets us shed light on anti-exceptionalism: this is the contention that logic itself should be accepted, rejected and revised
according to the same standards as other theories in science. In other words one should attempt to disprove the validity of a given logical system by searching for empirical evidence that falsifies a true statement in that logic.

Now the question is: suppose you wanted to test whether we should reason about the universe using classical or intuitionistic logic, what would do? Even if you only find evidence for classical logic (i.e. you find that all of your experiments so far agree with with what one would expect in classical logic), that doesn’t equip you with any sense of how likely it is for you to never encounter a situation in which one must think intuitionistically, but not classically. But this is where degree of satisfiability can be useful. Suppose you knew that there is an equation \(\varphi = \top\) which is tautological in classical logic, but not intuitionistically. If we know that \(\varphi = \top\) has finite satisfiability gap \(\varepsilon\), then, as we examine the universe, collecting data about the validity of the equation \(\varphi = \top\) as we go, and, because this equation has finite satisfiability gap, we can quantify how likely it is that the following two assertions hold simultaneously: (1) so far, all of our data points satisfy \(\varphi = \top\) (which, recall, is a classical principle) while (2) the universe we inhabit exhibits evidence against classical logic (i.e. there exist data points which do not satisfy \(\varphi = \top\)).

Some examples of classical principles (i.e. formulae that are tautological if and only if the logical system we inhabit is the classical one) include:

• \(x \lor \neg x = \top\) (i.e. the law of excluded middle)
• \(\neg \neg x = x\) (i.e. double negation elimination) and
• \( x \to y = \neg x \lor y\) (i.e. material implication).

So do there exist classical principles which have finite satisfiability gap? And what does this have to do with Heyting Algebras?

Surprisingly the short answer is yes! This is part of what we show in our paper. But, before I spoil the fun, let’s answer the second question: we care about Heyting algebras because they are to intuitionistic logic what Boolean algebras are to classical logic. Formally this is what I mean:

(1) a propositional formula \(\varphi\) is provable in classical logic precisely if, for every Boolean algebra \(B\), one has that \(B \models (\varphi = \top)\) and

(2) a propositional formula \(\varphi\) is provable in intuitionistic logic precisely if, for every Heyting algebra \(H\), one has that \(H \models (\varphi = \top)\).

These two two statements mean that we can think about all of this wonderful business of anti-exceptionalism in very mathematically concrete terms; we ask: are there any classical principles (such as the ones I listed above) which have finite satisfiability gap in Heyting algebras?

To understand what this means, note that, if the answer were no, then this would mean that it’s essentially hopeless to try to empirically assert the validity of classical logic over intuitionistic logic. This is because, for any classical principle \(\varphi\) , there would be Heyting algebras \(H\) (plausible models of the logical structure of the universe we inhabit) in which the classical principle does not hold (i.e. \(H\) is not Boolean), but where the probability of satisfying the equation \(\varphi = \top\) is arbitrarily high when one samples points from \(H\) independently at random.

Fascinatingly, it turns out that this is not the case! Indeed we showed that the law of excluded middle does have finite satisfiability gap (this is the theorem below) and moreover, with much more effort, one can suitably extend this result to infinite Heyting algebras.

Theorem [B. , Kocsis]: for any heyting algebra \(H\), either \(H\) is Boolean (in which case \(\mathsf{ds}_H(x \lor \neg x = \top) = 1\)) or one has that \(\mathsf{ds}_H(x \lor \neg x = \top) \leq 2/3\).

We prove many more results, for instance we show that, although double negation elimination also is a classical principle, it does not have finite satisfiability gap. In other words, there are Heyting algebras which are not Boolean, but in which double negation elimination holds with arbitrarily high probability!

This is the starting point for another one of our results which yields a complete classification of all the one-variable equations of Heyting algebras in terms of their degree of satisfiability.

Theorem [B., Kocsis]: An equation \(\varphi(p)\) in one free variable has finite satisfiability gap precisely if it is equivalent to one of the following: \(p = \top\), \(\neg p = \top\) or \(p \lor \neg p = \top\).

Where to next?

This project was incredibly fun particularly because it involved a blend of combinatorics (e.g. to prove that material implication has no gap), lattice theory and logic. Furthermore, the results are very encouraging compared to the case of finite groups, so perhaps there is a big untold story lurking here in the realms of lattice theory. I wonder what we might uncover next…

Until next time,

Ben

Recently I have been thinking a lot about pullbacks of graphs and it really is frustrating at times because they’re much harder to think about compared to colimits. It turns out that there is an obvious (in hindsight) reason for this and I thought it would be nice to tell you about it.

While thinking of limits of graphs, I’ve been progressively roping more and more people into joining me in this game. First I started with my undergraduate student Mansi Pai and then I got Will Turner into it too. Both of them (like every other person I play these games with) observe very quickly that, although it’s very visually simple to think of taking colimits of graphs, limits, the dual operation, are much harder to think about. It turns out that you can see why very easily once you know a fact and a vibe:

Fact. spans of finite sets are \(\mathbb{N}\)-valued matrices.

Vibe. prime factorization is “hard” to do.

Now I put “hard” in quotes above because, as you probably know, nobody really knows which complexity class PrimeFactorization really ought to be in (although we all suspect it to be NP-intermediate). Either way though, since we base lots of cryptography on the fact that prime factorization is difficult to do, I think it’s fair for me to say that it’s a “hard problem” for the purposes of this post.

Now what about the fact I mentioned? Well, as the nlab will tell you, Spans in FinSet are \(\mathbb{N}\)-valued matrices : a span \(X_1 \leftarrow M \rightarrow X_2\) of finite sets, is a matrix with \(|X_1|\) rows, \(|X_2|\) columns and where the \((x_1, x_2)\)-entry (for \((x_1, x_2) \in X_1 \times X_2\)) is given by the cardinality of the fiber over the two elements \(x_1\) and \(x_2\) (i.e. the cardinality of the set \(\{m \in M \mid f_i(m) = x_i \text{ for } i \in \{1,2\}\) where \(f_1\) and \(f_2\) are the legs of the span above).

In any category \(\mathsf{C}\) with pullbacks, you can define the category \(\mathsf{Span}(\mathsf{C})\) of spans in \(\mathsf{C}\). This has as objects those of \(\mathsf{C}\) and as arrows the spans in \(\mathsf{C}\). Composition is done by pullback as follows: given two composable morphisms \((M, m_1, m_2) \colon X_1 \to X_2\) and \((N, n_1, n_2) \colon X_2 \to X_3\) as drawn below,

we form their composite by taking the pullback of \(m_2\) and \(n_1\) yielding the red span shown below.

Now, given what I just told you about thinking of matrices as spans, it should be natural to wonder whether the category \(\mathsf{Span}(\mathsf{FinSet})\) represents. It turns out that it can be thought of as the category having natural numbers as objects and matrices as morphisms which compose via matrix multiplication.

But then, armed with this fact and the fact that integer factorization is hard, it should be obvious that writing a graph as a limit of prime factors (where I mean “prime” in terms of being written as pullbacks) should be hard: if you could do that, then you would also have a way of factorizing matrices; but then you could factorize \(1 \times 1\) matrices. In other words, limits of graphs are hard to think about because integers are hard to factorize.

Alla prossima,

Ben

During Thanksgiving week I went to Wytham Abbey, a manor house in Oxfordshire where the “Workhop on Non-Compositionality in Complex Systems” was taking place. The workshop (organized by Matteo Cappucci and Jules Hedges) was centered around four papers that covered the theme of compositional patterns and emergence therein. I wrote one of them (the one on Structured Decompositions which I authored with Zoltan Kocsis and Jade Master) and you can find the other three here: 1, 2, 3. It was a truly lovely week of research in beautiful frescoed rooms warmed by fireplaces that Fabrizio would diligently keep burning at their maximum capacity.

While I was there, I worked with Fabrizio Genovese, Caterina Puca and Daniel Rosiak on some ideas that Daniel, James Fairbanks and I had been throwing around for a while, namely: “can you use cohomology to detect the failures of compositionality of a computational problem?” This ended up requiring us to spend a week computing in a frenzy, but the outcome amounted to many deep observations that we’re still trying to digest fully. The goal of this blog post is to just explain why I (really I should say “we“) think that cohomology is the right tool for making sense of emergence.

Computational Problems as Presheaves

I like to think of computational problems as presheaves assigning a set of solutions (i.e. a solution space) to each object \(c\) in some category of inputs. For example consider the “fruit fly” of computational complexity theory: the \(k-\texttt{VertexCover}\) problem. It is the decision problem that asks whether a given graph \(G\) contains a vertex subset \(S\) of size at most \(k\) (some given integer) such that the removal of \(S\) from \(G\) yields an edgeless graph. An example of a graph with a vertex cover of size two is shown below (pick \(\{b,d\}\) as the vertex cover).

You can encode this problem as a presheaf \(\mathcal{V}_k \colon \mathsf{Grph}^{op}_{mono} \to \mathsf{Set}\) which is a “functor by pullback” acting on objects as follows: $$\mathcal{V}_k \colon G \mapsto \{S \subseteq G \mid |S| \leq k \text{ and } G – S \text{ edgeless}\}.$$ (Note that you really need to start with the category of graphs and monomorphisms if you want this to actually be functorial since otherwise the size of the vertex covers might blow up when you pull them back along arbitrary morphisms.)

An Example: Solving Vertex Cover by Dynamic Programming on a Decomposed Graph.

Suppose we’re given a graph \(G\) and a cover of \(G\) (i.e. a structured decomposition) consisting of a collection \((U_i)_{i \in I}\) of subgraphs of \(G\) whose colimit is \(G\). Can we solve \(k-\texttt{VertexCover}\) on the instance \(G\) by only computing locally on the pieces \((U_i)_{i \in I}\) of the cover?

The answer is yes and you’ll see why in moment. But I’m not going to bother telling you the whole solution because it’s more complicated than it needs to be and it would obfuscate the point I’m trying to make. Instead, I’ll tell you an easier story: rather than considering any cover \((U_i)_{i \in I}\), we’ll only focus on path decompositions. Intuitively a path decomposition is a cover where each open \(U_i\) has non-empty intersections with \(U_{i-1}\) and \(U_{i+1}\) and empty intersection otherwise. More precisely, a path decomposition of a graph \(G\) is a diagram that looks like a sequence of monic spans whose colimit is \(G\). For example a path decomposition into \(n\) pieces \(U_1, U_2, \dots, U_n\) might look like $$U_1 \hookleftarrow U_{1, 2} \hookrightarrow U_2 \hookleftarrow U_{2,3} \hookrightarrow U_3 \dots U_{n-1} \hookleftarrow U_{n-1, n} \hookrightarrow U_n.$$

So how might we solve \(k-\texttt{VertexCover}\) by dynamic programming on a path decomposition?

To see how to do this, let’s start with an even easier presheaf, namely the one that takes a graph to all of its vertex covers without any size restrictions. Let’s call this \(\mathcal{V} \colon \mathsf{Grph}^{op}_{mono} \to \mathsf{Set}\). This presheaf is actually a sheaf, meaning that, if we are given a vertex cover \(S_i\) in \(U_i\), say and a vertex cover \(S_j\) in \(U_j\), then we can always construct a unique vertex cover \(S\) on the union (pushout) of \(U_i\) and \(U_j\) which restricts to \(S_i\) (resp. \(S_j\)) on \(U_i\) (resp. \(U_j\)) whenever \(S_i |_{U_i \cap U_j} = S_j |_{U_i \cap U_j}\) (i.e. whenever the two vertex covers agree over the intersection \(U_i \cap U_j\)).

The fact that \(\mathcal{V}\) is a sheaf has profound algorithmic consequences (which you can read about in my paper with Ernst Althaus, James Fairbanks and Daniel Rosiak) which let us design fast dynamic programming algorithms. In this concrete case the dynamic programming algorithm to decide if \(\mathcal{V}(G)\) is empty (i.e. \(G\) is a no-instance) or not goes as follows.

– You start with the given path decomposition $$U_1 \hookleftarrow U_{1, 2} \hookrightarrow U_2 \hookleftarrow U_{2,3} \hookrightarrow U_3$$ of the input graph \(G\) (for simplicity let’s assume we only have three opens).

– Then you apply \(\mathcal{V}\) to this decomposition to get the following diagram of sets: $$\mathcal{V}(U_1) \hookrightarrow \mathcal{V}(U_{1, 2}) \hookleftarrow \mathcal{V}(U_2) \hookrightarrow \mathcal{V}(U_{2,3}) \hookleftarrow \mathcal{V}(U_3)$$

which represents the local solution spaces \(\mathcal{V}(U_i)\) and their restriction maps to the pairwise intersections.

– Now we compute the pullback \(\mathcal{V}(U_1) \times_{\mathcal{V}(U_{1, 2})} \mathcal{V}(U_2)\) and we remove from \(\mathcal{V}(U_1)\) and \(\mathcal{V}(U_2)\) any element which is not in the range of the legs of the pullback cone.

– Finally repeat the previous step for \(\mathcal{V}(U_2)\) and \(\mathcal{V}(U_3)\) and answer “NO” if any of sets associated to \(U_1\), \(U_2\) or \(U_3\) after this process of filtering are empty.

Since \(\mathcal{V}\) is a sheaf, it’s not too hard to see that this algorithm is correct (for an actual statement of the algorithm I sketched above and its proof of correctness in a much more general case, see our paper). Furthermore this algorithm is fast since it takes time at most \(2^{2k} \cdot n\) where \(n\) is the number of pieces in the path decompsotion (in the example above we had \(n = 3\)).

At this point one might ask whether this same approach might work if we replace the presheaf \(\mathcal{V}\) with the one we actually care about, namely \(\mathcal{V}_k\). Unfortunately this doesn’t work and it fails because \(\mathcal{V}_k\) is not a sheaf. To see why, observe that, although we might have two vertex covers \(S_i\) and \(S_j\) of size at most \(k\) on some opens \(U_i\) and \(U_j\), even if we have that \(S_i |_{U_i \cap U_j} = S_j |_{U_i \cap U_j}\), we are not guaranteed that the union \(S_i +_{S_i |_{U_i \cap U_j}} S_j\) has size at most \(k\).

Now staring at this, one might get the feeling that this is the only way in which the \(k-\texttt{VertexCover}\) problem fails to be compositional, but how can we make this intuition precise?

Čech Cohomology for Vertex Cover

To study the failures of compositionality of the \(k-\texttt{VertexCover}\) problem, we’ll first need to set ourselves up for some cohomology. First of all, consider the nerve

of the path decomposition. We will use define the following augmented complex

where \(F\) to denotes the functor obtained by composing \(\mathcal{V}_k\) with the free Abelian group functor and where the coboundary maps are given by $$ \delta^{-1} \colon \bigl (s \in \mathcal{V}_k(G) \bigr) \mapsto \bigl (s|_{U_i})_{i \in I} \quad \text{ and } \quad \delta^n \colon s \mapsto \sum_{j = 0}^{n} (-1)^j F(d_{n,i})(s). $$

As usual we will define the \(n\)-th cohomology group \(H^n\) as the quotient \(H^n := \ker \delta^n / \text{im} \delta^{n-1}\). Now notice that, if \(F\) were a sheaf, then \(H^0\) as defined with respect to this augmented complex would be trivial. To see this, observe that \(\ker \delta^0\) is generated exactly by the matching families of the sheaf and thus, if \(F\) were a sheaf, then each matching family would lift to a unique global section (i.e. each matching family would be in the image of \(\delta^{-1}\)). For a presheaf which refuses to be a sheaf (such as our \(F\) as we just defined it above), however, \(H^0\) is generated exactly by those families of local vertex covers, which, despite being in pairwise agreement, fail to lift to global solutions.

This is wonderful: what we just did was deduce that the obstructions to compositionality are given by the generators of \(H^0\). But what does this mean concretely? And does this agree with our intuition that the only way in which \(\mathcal{V}_k\) fails to be compositional is that local vertex covers may glue into vertex covers that are too large (i.e. they exceed our budget of \(k\) vertices)?

It’s time to compute!

Let’s make this a small example. Take \(k = 2\) and let \(G\) be a four-cycle with vertices \(a,b,c,d\) and let’s consider a path decomposition of \(G\) into two parts \(U_1\) and \(U_2\) where \(U_1\) is the two-edge path \(d-a-b\) and \(U_2\) is the two-edge path \(d-c-b\). Now enumerate the local vertex covers of size at most \(2\); these are (below I’m dropping parentheses, so read \(a\) as \(\{a\}\) and \(ab\) as \(\{a,b\}\) etc.):

$$\mathcal{V_2}(U_1) = \{a, ab, ad, bd\} \quad \text{ and } \quad \mathcal{V_2}(U_2) = \{c, bc, dc, bd\}.$$

Since \(U_{12}\) consists solely of the vertices \(b\) and \(d\) (and no edges), we have that \(\mathcal{V}_2(U_{12}) = \{\emptyset, b, d\}\) and hence the matching familes are

$$\ker \delta^0 = \{(a, c), (ab, bc), (ad, dc), (bd, bd)\}$$

while, since \(\mathcal{V}_2(G) = \{ac, bd\}\), we have

$$\text{im} \delta^{-1} = \{(a,c), (bd, bd)\}.$$

Thus we have that \(H^0\) has two generators (namely these are \((ab, bc)\) and \((ad, dc)\)) which correspond precisely to those local vertex covers which agree on the intersection, but whose union is too large!

Does this work this nicely for other problems?

The answer is a resounding yes! If you want to try it out, I suggest you try the \(k-\texttt{CycleTransversal}\) problem which asks to find a set \(S\) of vertices whose removal from the host graph \(G\) renders it a forest. This too can be cast as a presheaf by pullback and this too refuses to be a sheaf. The interesting thing is that, if you try to compute \(H^0\) for this presheaf on the same graph and cover described in the previous example, you’ll end up with three generators: two of them will describe issues relating to the size of the glued solutions (just like in the case of vertex cover) but the third one is different, it describes the fact that two local cycle covers can agree, but their gluing can fail to cover all the global cycles!

Looking ahead

Ideally it would be wonderful if we could make use of the information of \(H^0\) to automatically come up with dynamic programming algorithms. I have many ideas of how to do this and, based on my ongoing work with Spencer Breiner, Matteo Cappucci, James Fairbanks and Daniel Rosiak, I think these are all very promising. However, for now it’s unclear whether we can actually turn this cohomological information into a practical tool for designing combinatorial algorithms. On the bus ride from Wytham Abbey to Heathrow airport, I was told that cohomology groups are sheaves. If that’s true, then I have some good news for us all… but I’m having a hard time hunting down the precise result. If anyone knows about this, please reach out, I’d love to know the details!

Until next time,

Ben

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

Sometimes in math things sound obviously true and that’s exactly how it turns out. Other times, you’re less lucky. Today was one of those days. In this post we’ll see that, although \(\mathsf{Grph}\) is adhesive, \(\mathsf{Grph}^{op}\) isn’t.

For a while now, Will Turner and I have been working both with adhesive categories and with \(\mathsf{Grph}^{op}\). As is often the case, if you’re holding a nail-shaped thing in one hand and hammer-shaped thing in the other, you might think that they might go together well. That’s what we did. In the back of our minds there was this little harmless assumption that \(\mathsf{Grph}^{op}\) was adhesive. The proof of this “fact” was one of those “to-dos” that I was saving for a rainy day. The trouble is that there aren’t that many rainy days in Florida, so I never checked it until today when Will found a little counterexample to a conjecture we had made. It turns out that \(\mathsf{Grph}^{op}\) isn’t adhesive and in fact neither is \(\mathsf{Set}^{op}\) (and hence no copresheaf category is!).

So what’s the plan? Well, we’re going to think about co-adhesive categories: i.e. any category \(\mathsf{C}\) such that \(\mathsf{C}^{op}\) is adhesive. I’ll remind you what an adhesive category is and then I’ll prove that \(\mathsf{Set}\) isn’t co-adhesive. It’ll be real short and easy. I’m writing this mostly for me so that I never make the same mistake twice.

Df: an adhesive category is a category \(\mathsf{C}\) in which:

• all pushouts of monomorphims exist,
• all pullbacks exist and
• all monic pushout squares as Van Kampen.

What does Van Kampen mean? A pushout square

is Van Kampen if, whenever we are given a commutative square sitting above it (i.e. the given pushout square is the bottom face) as in the following diagram

then, if back faces are pullback squares, then the front faces are pullbacks if and only if the top face is a pushout.

If adhesive categories seem mysterious to you, don’t worry. The definition scares a lot of people at first sight. But adhesive categories are very nice and in fact most of the nice categories you know and love are adhesive: \(\mathsf{Set}\) is adhesive, any copresheaf category is adhesive (such as graphs, Petri nets, simplicial sets, hypergraphs, databases) and any small topos is adhesive too. Surprisingly (at least for me) it turns out that \(\mathsf{Set}^{op}\) isn’t adhesive.

Prop: \(\mathsf{Set}\) is not coadhesive.

Proof: we have to show that \(\mathsf{Set}^{op}\) is not adhesive. Since \(\mathsf{Set}\) has all pushouts and pullbacks, the problem must lie with the Van Kampen squares. So take the following pushout square in \(\mathsf{Set}^{op}\) (I’ll draw it as a pullback square in \(\mathsf{Set}\) because it’s easier to think about that way).

And take any cube sitting above it as in the definition of a Van Kampen square (again notice that everything will look upside-down because we’re dualizing everything).

This cube has the pullback square we started with as its bottom face and it’s generated by taking pushouts starting with the red function \(f\) defined as \(f = \{(xa,a_x),(xb, b_x), (ya, y’), (yb, y’)\}\). It is easy to verify that, although all of the side faces of the cube are pushouts, the top face is not a pullback. Thus \(\mathsf{Set}\) is not co-adhesive, as desired.

So there you go. It turns out as usual that it’s the “easy things” that bite you. It turns out that categorical duality continues to be difficult to think about. And it turns out that I have little intuition as to which categories can be both adhesive and co-adhesive! If you know of any examples please do get in touch with me!

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

Last fall I read “A diagrammatic view of differential equations in physics” by Evan Patterson, Andrew Baas, Timothy Hosgood and James Fairbanks. They show that you can use diagrams to write down the sorts of equations on manifolds that physicists care about. In this post I’ll try to convey the main ideas of the paper to you so that: (1) I can get you excited about it and (2) I can refer back to these notes in the future.

So how does one think of an equation as a diagram?

The idea is pretty neat. First you’ve got to ask yourself: “what’s an equation?” Since an actually good answer to this questions can get rather philosophical and since I want to get to the point fast, I’ll wave my hands a bit: an equation is a way of relating “quantities” that are defined on some “space” of interest.

Then you’ve got to ask yourself: “what kind of mathematical structure can I use to impose relations on some quantities?”

If you’re thinking of graphs – the relational structure par excellence – then you’re not far off. They don’t really do the trick, but you’ll see in a second that diagrams (a.k.a. semantically-rich graphs) are exactly what we need.

(By the way, as an Italian who grew up in a culture where hand gestures can be very precise, I never really understood why “hand-waving” is considered another way of saying “sweeping details under the rug”.)

So having established the intutition behind where the diagrams come from, all that’s left is to figure out what we’ll mean by “space” and “physical quantities” defined on that space. This is summarized below.

“Space”	A manifold \(M\)
Physical quantities defined in “space”	Sheaves on \(M\)
Equations	Diagrams relating physical quantities on the space (i.e. diagrams into the category of sheaves on \(M\))

I like to get the big picture first, but that’s just my general preference, so don’t worry if you’re lost a this point: I’ll unpack things below. Let’s start with an example (it’s the same example that’s given in the Patterson, Baas Hosgood & Fairbanks paper).

Example: the Discrete Heat Equation as a Diagrammatic Equation

I’ll be talking about the heat equation as an example, so, just as a reminder, let’s recall it: we say that a function \(u \colon (T \subseteq \mathbb{R}, U \subseteq \mathbb{R}^n) \to \mathbb{R}\) is a solution to the heat equation (where \(T\) is the time domain and \(U\) is the spacial domain) if \[\frac{\partial u}{\partial t} = \Delta u\] where \(\Delta u\) denotes the Laplacian \[\Delta u = \sum_{1}^n \frac{\partial^2 u}{\partial x_i^2}\] in terms of the Cartesian coordinates \(x_1, \dots, x_n\).

Now, since the goal is to explain how to think of equations as diagrams and since I’m trying to follow the Diagramamtic Equations paper closely here (so that you can seemelessly transition into reading it, if you’re interested), I’ll focus on the discrete heat equation.

In the discrete case, rather than thinking of space as \(\mathbb{R}^n\), we’ll think of it as a graph \(G\) with vertices \(V\) (for instance we could take \(G = \mathbb{Z}^n\)). Just as in the case above, we’ll want a solution (a “quantity”) to the heat equation on the spacial domain \(G\) to be a function of the form \(u \colon \mathbb{N} \times V \to \mathbb{R}\) (note that we’re thinking of everything, including time as being discrete).

The discrete derivative with respect to time of such a function \(u\) is then given as the operator \(\partial \colon \mathbb{R}^{\mathbb{N} \times V} \to \mathbb{R}^{\mathbb{N} \times V}\) which takes any function \(u\) to the function \[\partial \: u \colon (n, x) \mapsto u(n+1, x) – u(n,x).\] One can similarly define the discrete Laplacian as an operator \(\Delta \colon \mathbb{R}^{\mathbb{N} \times V} \to \mathbb{R}^{\mathbb{N} \times V} \). I won’t give the whole definition here (you can just check out page 6 of the paper) since the point I’m trying to get accross is that the heat equation can be written as the following diagram in \(\mathsf{Vect}_{\mathbb{R}}\) (the category of \(\mathbb{R}\)eal vector spaces and linear maps)

To undertand why this is an equation, notice that you can pick out a single vector \(u \in \mathbb{R}^{\mathbb{N} \times V}\) as a generalized element i.e. a linear map \(\mathbb{R} \to \mathbb{R}^{\mathbb{N} \times V}\) which takes the basis vector of \(\mathbb{R}\) to \(u\) (the vector we were trying to pick out). Then the commutativity of the following diagram is precisely the statement of the heat equation!

Summarising what we’ve learnt so far, we have the following table.

Traditional view	Diagrammatic View
An equation \(e\)	A diagram \(d_e\) whose morphisms are the operators of \(e\).
A solution \(u\) to \(e\)	A cone over the diagram \(d_e\).

Diagrammatic Equations

If you get the general idea by now (please ask questions in the comments, if not!) then it’s time to do two things: (1) think of the continuous case and (2) figure out what kinds of properties we want the “operators” to have (and what category we ought to live in). I’ll give a very concise summary below of how to think of all of this. For that, though, you’ll need to know about sheaves.

Sheaves. I already explained sheaves in some previous posts (see §1, §2 and §3 if you want to learn a bunch about them) but, for what I’ll be speaking about in this post, we can stick with the more down-to-Earth notion of a sheaf on a topological space.

Df. Let \(X\) be a topological space and \(\mathsf{S}\) be a category. An \(S\)-sheaf on \(X\) is a contravariant functor \[\mathcal{F} \colon (\mathcal{O}X)^{op} \to \mathsf{S} \] from the poset of open sets of \(X\) to \(\mathsf{S}\) satisfying the sheaf condition; i.e. the requirement that, if you give me a collection \((U_i)_{i \in I}\) of opens in \(X\) whose union is an open \(U\), then \(\mathcal{F}U\) is the limit of the \(FU_i\) over the diagram induced by \(I\) (in other words \(\mathcal{F}\) takes colimits to limits).

I’m telling you about sheaves becasue we’ll use them to represent the physical quantities involved in our diagrammatic equations: these quantities will be described as sheaves on a fixed space-time domain represented by a manifold \(M\) with corners.

For this post, I’ll only care about \(\mathsf{Vect}_{\mathbb{R}}\)-valued sheaves such as the sheaf \(\mathfrak{X}_M\) of smooth vector fields on a manifold \(M\). Such sheaves (as do all sheaves for that matter) assemble into a category \(\mathsf{Sh}(M, \mathsf{Vect}_{\mathbb{R}})\) of \(\mathsf{Vect}_{\mathbb{R}}\)-valued sheaves on \(M\) (the morphisms are natural transformations). Following the notation in the Diagrammatic Equations paper, I’ll abbrevite \(\mathsf{Sh}(M, \mathsf{Vect}_{\mathbb{R}})\) as \(\mathsf{Sh}_\mathbb{R} M\).

Recall that in our earlier Heat Equation example the solution to the heat equation on \(\mathbb{R}^n\) was a function \[u \colon \mathbb{R} \times \mathbb{R}^n \to \mathbb{R}\] assigning quantities (heat, for instance) to space-time. The idea in Patterson, Baas Hosgood & Fairbanks’ paper is to replace \(\mathbb{R}^{T \times \mathbb{R}^n}\) by a sheaf on a fixed manifold \(M\) representing space-time. Indeed here’s how they put it:

“[p]hysical quantities are taken to be sections of sheaves on the spatial domain M or the space-time domain \(M \times [0, \infty)\). Loosely speaking, a sheaf on a topological space is a coherent family of quantities defined on open subsets that can be glued together from smaller subsets whenever they agree on the overlaps.“

We’ve already seen such a sheaf \(\mathfrak{X}_M\) (first on the list below) and the following screenshot has a few more physically-relevant examples they give in the paper.

Finally, with this view in mind, we can speak of a diagram \[e \colon J \to \mathsf{Sh}_{\mathbb{R}} M \] as a diagrammatic equation \(e\) on a manifold \(M\) whose solutions (as in the example above) are cones over \(e\).

Even though I’m only thinking of \(\mathsf{Vect}_{\mathbb{R}}\)-valued sheaves (note that things are presented in greater generality in the original paper), I still find this “definition” of a diagramamtic equation remarkably satisfying.

---

Until next time,
Ben

In a previous post, we discussed sieves, the sieve-y definition of Grothendieck topologies and a few exaples thereof. Today we’ll return to sheaves, but this time we do so armed with a better understanding of sites (the “places” in which to define sheaves).

This post consists of notes and reflections from reading Daniel Rosiak’s book “Sheaf Theory through Examples“.

A refresher

As you might recall, the frist definition of a sheaf which we saw was that of a sheaf on the subgraph topology; namely a functor $$\mathcal{F}: \mathbf{Sub}G \to \mathbf{Set}$$ satisfying the condition that, whenever we are given an \(I\)-indexed mathching family of sections \((s_i \in \mathcal{F}G_i)_{i \in I}\) (i.e. satisfying the requirement that \(s_i|_{G_i \cap G_j} = s_j|_{G_i \cap G_j}\) for all \(i\) and \(j\)), then there is a unique section \(s \in \mathcal{F}\bigl(\bigcup_{i \in I }G_i\bigr)\) which restrict to each section in the family (i.e. such that \(s|_{G_i} = s_i\)).

Notice that, when one says that a functor is a sheaf, one must also specify with respect to which topology it is a sheaf. For instance, in the definition above, we have that \(\mathcal{F}\) is a sheaf with respect to the subobject topology on \(\mathbf{Sub}G\) (but it might fail to be a sheaf with respect to some other topology on \(\mathbf{Sub}G\). The key point is that, if we change the topology, then we are also changing what it means when we state that a family of sections is a matching family. So the first step forwards is to define the matching condition more generally.

Matching families

Recal that a sieve \(S\) on an object \(c \in C\) can be defined as a subfunctor of the representable $$y_c \colon C \to \mathbf{Set}^{C^{op}}$$ $$y_c \colon b \mapsto C(b, c).$$ You should think of \(S\) as the functor taking each \(b \in C\) to the subset set of all morphisms in \(C(b,c)\) which are in the sieve \(S\).

Def : Let \((C, K)\) be a site, \(S\) be a \(K\)-cover of an object \(c \in C\) and \(P: C^{op} \to \mathbf{Set}\) be a presheaf. Then a matching family of sections of \(P\) with respect to the cover \(S\) is a morphism of presheaves \(\chi \colon S \Rightarrow P\).

Let’s unpack this. Let \(a\) be an object of \(C\). The component of \(\chi\) at \(a\) is a function \(\chi_a \colon Sa \to Pa\) which “picks-out” a section in \(Pa\) for each element of \(Sa\) (think an “open” in \(S\)). The naturality of \(\chi\) ensures that every morphism \(f \colon a \to b\) gives rise to a commutative square which intuitively states, for any “open” \(\beta \in Sb\) in \(b\), that “if you restrict \(\beta\) to \(a\) (via \(Sf\)) and then consider its associated section \(\chi_a Sf(\beta)\), you’ll get the same answer as if you had first grabbed ahold of the section \(\chi_b(\beta)\) associated to \(\beta\) and then restricted that section to \(a\) (via \(Pf\))”. If you compare this to the definition of a matching family on the subgraph topology I gave earlier, you’ll see that the intuition carries over.

Now we’re ready to give a proper definition of a sheaf on a site.

Def: Let \(P \colon C^{op} \to \mathbf{Set}\) be a presheaf on a site \((C, K)\). Then we call \(P\) a sheaf with respect to \(K\) (or a \(K\)-sheaf) if $$\forall c \in C \text{ and } \\ \forall \text{ covering sieves } \bigl(\iota \colon S \Rightarrow y_c\bigr) \in Kc \text{ of } c \text{ and } \\ \forall \text{ matching families } \chi: S \Rightarrow P$$ there is a unique extension $$\mathcal{E} \colon y_c \Rightarrow P$$ making the following triangle commute.

Let’s process that definition one step at a time, starting with the quantifiers;. We’re just saying the usual thing: “\(P\) is a sheaf if there is a unique extension for every matching family \(\chi\) w.r.t. any cover \(S\) of any object \(c\)”. That’s the trivial part.

The harder part to unpack is understanding how the morphism of presheaves \(\mathcal{E}_\chi\) encodes the amalgamation property of sections of sheaves (it’s the usual big equalizer diagram.. see the first post in the series if you don’t remember what I’m talking about). This is not apparent “on the nose”. But it becomes clear once you invoke the Yoneda Lemma: since the natural transformations \(\mathsf{Nat}( y_c , P) \) from \(y_c\) to \(P\) are in one-to-one correspondence with the elements of \(Pc\), a morphism of presheaves \(\mathcal{E}: y_c \Rightarrow P\) is just a way of picking an element of \(Pc\) — i.e. a global section on \(c\). The fact that the triangle commutes is simply saying that the global section \(\mathcal{E}\) which we picked must restrict to the local sections picked by the matching family \(\chi\).

Anyway, today is a short post because I’m taking my Christmas spirit elsewhere. Ciao!

This post is in two parts. The first part consists of notes based on reading Daniel Rosiak’s book Sheaf Theory Through Examples; while the second part of this post (titled “Decompositions as topologies”) consists of new work straight from my notebook. As always the lines are blurred between learning something that is new to me and discovering something that is new to me and as well as others.

Notes on Sieves & Grothendieck Topologies

Last time I started explaining (\(\mathbf{Set}\)-valued) sheaves, coverages, sites and Grothendieck (pre-) topologies. Today I’ll talk about sieves and I’ll go deeper on sheaves, presheaves and Grothendieck topologies.

So here’s a reminder of what happened in the previous post in this series. Even though topology is all about open sets and continuity, Grothendieck realised that, from the point of view of defining sheaves, the only thing that is important is the notion of a covering. This is a notion that has nothing to do with the idea of an “open set” and is hence much easier to generalize.

The very rough idea is the following. You start with a category \(C\). Thinking of a cover of any object \(c \in C\) as a set of morphisms with codomain \(c\), you associate to each such object \(c \in C\) a set \(K(c)\) of “permissible coverings” of \(c\). Then you call \((C, K)\) a site (a “place in which you can define sheaves”) if \(K\) satisfies certain “niceness” conditions.

One concern I was having last time while I was reading Daniel’s book was that the assignment \(K\) of permissible converings was defined as a function rather than as a functor. Thankfully nature is healing: today \(K\) will indeed be a functor. But for this we need our notion of a cover to be a little nicer. We need sieves.

Def: A sieve on an object \(c \in C\) is a family \(S_c\) of morphisms with codomain \(c\) which is closed under pre-composition.

Think: its a sieve because, after picking “entry-points into \(c\)” of the form \(f: d \to c\), anything that can enter \(d\) (i.e. any morphism \(g: e \to d\)) can also enter \(c\) (i.e. as the composite \(fg: e \to d \to c\)).

The idea now is to work only with “nice” covers (i.e. sieves) and define a “permissible covers” functor \(K\) which assigns sets \(K(c)\) of sieves to any object \(c\). Before doing this, though, let’s give two other equivalent definition of a sieve.

Def [sieve – Yoneda definition]: A sieve \(S\) on an object \(c \in C\) is a subfunctor of the Yoneda embedding at \(c\) (i.e. the functor \(y_c = C(-, c)\)).

Here’s how you see that this agrees with the defintion above. Given a family of morphisms \(\mathcal{S} := \{f_i: c_i \to c \mid i \in I\}\), we can define a functor \(S: C^{op} \to \mathbf{Set}\) taking each object \(x\) to the set \(\{f:x \to c \mid f \in \mathcal{S}\}\) and each morphism \(g: x \to y\) to the functor \(S_g: S(y) \to S(x)\) given by \(S_g: (f \in S(y)) \mapsto (fg \in S(x))\). Conversely, given any subfunctor \(S\) of \(y_c\), we get a sieve on \(c\) (in the set theoretic sense of the first definition above) as the set \(\bigcup_{x \in c} S(x)\) (by construction this will be closed under precomposition, as desired).

Def [sieve – Slice definition]: A sieve \(S\) on an object \(c \in C\) is a subcategory of the slice \(C/c\).

Given these definitions, we can redefine a Grothendieck topology as a category \(C\) equipped with an assignment \(K\) of “permissible” coverings to each object satisfying three axioms (which I’ll define in a second): (1) maximality, (2) stability and (3) transitivity.

The second axiom – i.e. stability – is just a funny way of saying that \(K\) is itself in fact a presheaf by postcomposition $$K: C^{op} \to \mathbf{Set}$$ which takes each \(c \in C\) to a set of sieves of \(c\) and which contravariantly maps each morphism \(f : x \to y\) in \(C\) to the function $$K_f : (S \in Ky) \mapsto (\{g: x’ \to x \mid (fg: x’ \to x \to y) \in S\} \in Kx).$$ We can rewrite this \(K\) as a subfunctor of the functor $$\mathbf{Sieve} : C^{op} \to \mathbf{Set}$$ which takes each object \(c \in C\) to the collection of all sieves on \(c\) (and which acts on arrows as we defined above).

I find this functorial perspective much easier to remember that the statement of the stability axiom, so I’ll adopt it when formulating the definition of a Grothendieck topology below.

Def: Let \(C\) be a category. We call a subfunctor \(K\) of \(\mathbf{Sieve} : C^{op} \to \mathbf{Set}\) a Grothendieck topology on \(C\) if it satifies the following two conditions:

• [Identity/maximality] the maximal sieve is always permissible; i.e. \(C/c \in K(c)\) for all \(c \in C\)
• [Transitivity] for any sieve \(R\) on some object \(c \in C\), if there is a permissible sieve \(S \in Kc\) on \(c\) such that for all \((\sigma: b \to c) \in S\) the sieve $$\sigma^*(R) := \{g: a \to b \mid (\sigma g: a \to b \to c) \in R\}$$ is permissible on \(b\) (i.e. \(\sigma^*(R) \in Kb\)), then \(R\) is itself permissible on \(c\) (i.e. \(R \in Kc\)).

Note: there is an equivalent “arrow” version of this definition which I won’t tell you about here (you can find in Daniel’s book or in Mac Lane & Moerdijk).

Thinking of a cover as a means of obtaining information about an object, the first axiom makes sense: perfect information should always be allowed. The second axiom has to do with the idea that “a cover of a cover better be itself a cover”. To see this, notice that it says that any sieve \(R\) on some object \(c\) must be a “permissible” (i.e. a “cover” for \(c\) – i.e. \(R \in Kc\)) if it “refines” some permissible cover \(S \in Kc\). Anyway, now we can define a site in the usual way.

Def: a site is pair \((C, K)\) consisting of a category \(C\) and a Grothendieck topology \(K\) on \(C\).

Examples

For my own sake, I’ll review four Grothendieck topologies which are covered in Daniel’s book.

The minimal topology on a category \(C\) is the the Grothendieck topology \(K\) which assigns to each \(c \in C\) precisely one covering sieve; namely the maximal sieve \(\{f \in \mathbf{Mor}(C) \mid \mathsf{codom}(f) = c\}\).

If \(C\) is a poset, the minimal topology simply amounts to assigning to each \(c \in C\) its downset \(\downarrow c\).

The maximal topology on a category \(C\) is the functor \(\mathbf{Sieve} : C^{op} \to \mathbf{Set}\) which we defined earlier.

The maximal topology looks wild to me. Taking \(C\) to be the category of graphs, the maximal topology would allow, for instance, the singleton set consisting of the uniqe morphism \(! : K_0 \to G\) to be a permissible cover of any graph \(G\).

The dense topology on a category \(C\) is the functor \(\mathsf{dense}: C^{op} \to \mathbf{Set}\) which takes each \(c \in C\) to the set of all dense sieves on \(c\) where a sieve \(S\) is dense if it satifies the following requirement: $$\forall f: b \to c \; \exists g: a \to b \text{ s.t. the composite } fg: a \to b \to c \in S.$$

For a finite poset \(P\) the notion of a dense set on some \(p \in P\) is easy to understand: it is any subset of \(\downarrow p\) which is a superset of the set of all those minimal elements of \(P\) which are in \(\downarrow p\). To see this, take some dense set \(S\) and notice that, if \(m\) is a minimal element which is at most \(p\), then there exists a \(q\) in \(S\) which is at most \(m\); but then \(q = m\) by the minimiality of \(m\). Conversely, writing \(M_p\) to denote the set of minimal elements which are at most \(p\), consider any set \(S\) with \(M_p \subseteq S \subseteq \downarrow p\). This set is dense since, for all \(p’ \leq p\) at least one of the elements of \(M_p\) will be at most \(p’\) and in \(S\). When a dense set is also a sieve, then it can be specified by any choice of elements in \(\downarrow p\) whose union contains all of \(M_p\). (Clearly the notion of a dense set is more interesting in infinite posets.)

For fun, let’s instantiate this example on the subobject poset \(\mathbf{Sub}G\) of some finite graph \(G\). Then, by the finiteness of \(G\) and the fact that \(\mathbf{Sub}G\) has a least element (namely the empty graph) we find that, for (G’ \subseteq G), any downset (or unions thereof) in \(\mathbf{Sub}G’\) is a permissible cover in \(\mathsf{dense}(G’)\).

The atomic topology on a category \(C\) specifies that a sieve on any \(c \in C\) is permissible whenever it is non-empty. As Daniel points out in his book, the maximality and transitivity axioms are trivially met; however, it is the functoriality of the Grothendieck topology that might fail: if \(C\) fails to have pullbacks, then, given a morphism \(b \to c\) it might not be obvious how to pull sieves on \(c\) back to sieves on \(b\). This can be resolved by requiring every cospan in \(C\) to have at least one cone (in particular posets which are not down-semi-lattices do not satisfy this property).

Some examples on graphs

An interesting example is to consiter the free category \(FG\) on a directed graph \(D\). What’s a sieve on \(FD\)? Well, pick a vertex \(x\) in \(D\) and recall that morphisms in \(FD\) are directed walks in \(D\). If we have a sieve \(S\) on \(x\), this corresponds to a union of maximal directed walks towards \(x\).

If \(D\) is strongly connected, then every sieve will necessarily be all of \(D\). To see this proceed by induction: it’s obvious on the 1-vertex graph. Now pick a vertex \(x\) in \(D\) and let \(S\) be a sieve on \(x\). By the inductive hypothesis we have that \(S\) contains all of \(D – y\) for some vertex \(y\) distinct from \(x\). Now consider any morphism \(f: y \to w\) for some \(w\) in \(D\). By the inductive hypothesis and since \(D\) is strongly connected, we have that there is a morphism from \(g: w \to x\) which is in the sieve and hence \(gf: y \to w \to x\) is in the sieve as well. Similarly, take any morphism \(f’: w’ \to y\) and notice that, since \(gf: y \to x\) (defined as above) is in the sieve, then \(f’gf\) is also in the sieve, as desired.

What’s nice about this is that it suggests that sieves on \(FG\) are related to the condensation of directed graphs. However, since the relationship doesn’t seem as clean as I’d like, I won’t sketch this further.

Finally let’s have a look at the subobject poset \(\mathbf{Sub}(G)\) of some fixed graph \(G\). We can assign a Grothendieck topology \(K\) to the category \(\mathbf{Sub}(G)\) as follows. For every subgraph \(G’\) of \(G\), define \(K(G’)\) to be the set of all sieves on \(G’\) in \(\mathbf{Sub}(G)\) (i.e. downward-closed collections of subgraphs of \(G’\)) whose colimit is \(G’\). This forms a Grothendieck topology because the colimit of the maximal sieve \(\downarrow G’\) is \(G’\) for each subgraph \(G’\) of \(G\) and because, if \(R\) is a downards-closed collection of subobjects of \(G’\) such that there is a cover \(S\) for \(G’\) satisfying the requirement that, for any morphism \(G” \subseteq G’\) in \(S\), the set \(R \cap \downarrow G”\) yields \(G”\) as a colimit, then clearly \(R\) yields \(G’\) as a colimit as well.

Decompositions as Topologies

Note: this section includes new work and departs from the note-taking theme of the rest of this post.

The topology on \(\mathbf{Sub}G\) I mentioned above, together with a similar topology on the poset \(\mathcal{O}X\) of opens of a topological space \(X\), are – from what I gather (and please correct me if I’m wrong) – the prototypical examples of Grothendieck topologies. But I find these constructions somewhat in conflict with my perspective on what the point of category theory is: I don’t want to define a topology for each graph, instead I’d like to equip the category of all graphs with a topology which I can then induce on a graph itself. I’m sure there are many ways of doing this, but I’ll focus on using structured decompositions (I have alterior motives, you see).

Throughout the rest of this section, fix some small category \(C\) which is adhesive (we need both assumptions). On any such category I’ll define a functor $$\mathsf{decomp}: C^{op} \to \mathbf{Set}$$ which takes each object \(c \in C\) to the set of all \(C\)-valued structured decompositions yielding \(c\); spelling this out we have $$\mathsf{decomp}: (c \in C) \mapsto \{d \in \mathcal{D}C \mid \mathrm{colim }\:d = c\}$$ where \(\mathcal{D}C\) denotes the category of \(C\)-valued structured decompoisitions. The arrow-component of \(\mathsf{decomp}\) is defined by “pointwise pullback”. Although this construction is a direct consequence of Lemma 5.10 and Theorem 5.8 in my paper with Jade Master and Zoltan Kocsis, I’ll still spend some time giving you the gist of it here. For each morphism \(f: b \to c\) in \(C\) we define a map $$\mathsf{decomp}\:f : \mathsf{decomp}\:c \to \mathsf{decomp}\:b$$ which takes each decomposition \(d_c\) which yields \(c\) to a decomposition \(d_b\) which yields \(b\). The way you go about producing such a \(d_b\) from \(d_c\) is by pointwise pullback with \(f: b \to c\); rather than explain this further I’ll refer you to the following screenshot of my paper (which you should check out if you want futher details).

The point of all this is that we’ve defined a functor $$\mathsf{decomp}: C^{op} \to \mathbf{Set}$$ which we’ll now show is a Grothendieck topology on \(C\).

First of all notice that each structured decomposition gives us a sieve by just taking the colimit arrows and then completing these downwards (by precomposition). In turn, any sieve \(S\), gives rise to structured decompositions by sticking spans betwen the bases of the resulting multicospan defined by \(S\); the choice of spans can be done by taking products in the slice \(C / c\) (i.e. pullbacks in \(C\) … tangentially Matteo cappucci just tweeted about this yesterday, so say “ciao Matteo” and check that out). With this in mind, let’s check the two remianing axioms in turn.

Maximality. The maximal sieve \(M\) on any object \(c \in C\) clearly defines a decomposition \(m: F_{dag}K_{|C|} \to \mathbf{Sp}C\) which yields \(c\) as a colimit (note that we need \(C\) to be small to be able to define the – possibly infinite – compelte graph \(K_{|C|}\) as the shape of the decomposition).

(Parenthetical remark: to be able to apply this whole construction to sets or graphs, say, we need to work with their skeletons since otherwise \(\mathbf{FinSet}\) and \(\mathbf{FinGr}\) are too big… you might even say that they are large.)

Transitivity. Take any sieve \(R\) on some object \(c \in C\), and consider the situation where there is a structured decomposition \(d_c \in \mathsf{decomp}\:c\) yielding \(c\) whose sieve \(S\) defined by the colmit cocone arrows from \(d_c\) into \(c\) satisfies hte following requirement:

\(\mathbf{(\star)}\) for all \((\sigma: b \to c) \in S\) the sieve $$\sigma^*(R) := \{g: a \to b \mid (\sigma g: a \to b \to c) \in R\}$$ is permissible on \(b\) (i.e. there is a structured decomposition \(d_\sigma \in \mathsf{decomp}\:b\) whose colimit arrows form a basis for \(\sigma^*(R)\)).

Now our task is to show that \(R\) is itself permissible on \(c\); in other words we need to show that there is a structured decomposition \(\rho\) whose colimit is \(c\) and whose colimit arrows define \(R\). This, however, follows since diagrams of diagrams are themselves diagrams. To see this note that for each \((\sigma: b \to c) \in S\) we get a structured decompositon \(d_\sigma\) for \(b\) via \(\sigma^*(R)\) (as we noted above). This corresponds to replacing each bag \(dx\) of the structured decompostion \(d\) corresponding to the sieve \(S\) by a structured decomposition \(d_{\sigma_x}\) defined as I mentioned earlier from some \((\sigma_x : dx \to c) \in S\). But since

• \(\mathsf{colim}\:d_{\sigma_x} = dx\) and
• \(\mathsf{colim}\:d = c\) and
• \(\mathbf{id}_c\) is terminal in \(C /c\),

we have that \(\mathsf{colim}\:\rho = c\), as desired. Thus we have shown the following theorem.

Theorem: For any small, adhesive category \(C\), the functor \(\mathsf{decomp}: C^{op} \to \mathbf{Set}\) is a Grothendieck topology on \(C\).