Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: deprecated: concurrency

Topic: shapes and algebraic structures

Joachim Kock (Mar 17 2021 at 15:15):

This is a continuation of some discussion in the thread "bisimulation". I just wanted to explain a little bit more some of the viewpoints behind whole-grain Petri nets. Actually it is not really specific to Petri nets...

Joachim Kock (Mar 17 2021 at 15:16):

Maybe this is more like a blog post than a chat. Sorry if it is out of scope.

Joachim Kock (Mar 17 2021 at 15:18):

So, it is an important technique in geometry to probe a space by mapping certain shapes into it, like charts or bases or paths or loops or simplices. Once one figures out which properties of geometric objects can be detected with which shapes, it is a very useful tool, and one can also begin synthetically to build spaces out of classes of shapes, which leads to notions of presheaf and sheaf. I just wanted to stress the geometric origin of the idea, and stress that colimits are about gluing, and gluing is a key aspect of geometry. But let's immediately move to category theory.

Joachim Kock (Mar 17 2021 at 15:24):

For a presheaf category, the obvious choice of shapes are the representables -- that's the whole point of presheaf categories -- and every presheaf is the colimits of representables. The colimit is over the category of elements, and by definition, elements are maps from representables. Although this is super abstract, it is very familiar: for example a directed graph is a presheaf on the category $0 \rightrightarrows 1$, where $0$ is the representable corresponding to vertices and $1$ is the representable corresponding to edges. We are just saying that to probe a graph we ask for its vertices and edges -- these are the elements of the graph -- and how they fit together. And that every graph is obtained by gluing together its vertices and edges.

Joachim Kock (Mar 17 2021 at 15:37):

So presheaf categories are a kind of tautological geometry, but still very interesting. The book Generic figures and their glueings by Reyes, Reyes and Zolfaghari is a very nice and elementary introduction to such things.

Fawzi Hreiki (Mar 17 2021 at 15:37):

I was learning a little bit about this recently. Are there any places where the notion of a total category is related to this framework?

Fawzi Hreiki (Mar 17 2021 at 15:38):

Because if we view the presheaf category as the topos of generalised spaces probeable by test spaces, then the left adjoint to the Yoneda embedding allows you to reconstruct a test space from a generalised space.

Joachim Kock (Mar 17 2021 at 15:39):

A category is a directed graph with further algebraic structure, namely composition of edges and identity edges. So we can probe it by studying its objects and arrows. But that does not say anything about the algebraic structure! To detect this, we need to probe with more complicated shapes, namely chains of edges, or linear graphs. These are (nonempty) finite linear orders and we write $[n]$ for the chain of n arrows. So we are now interested in the sets $Fun([n],C)$ for $C$ a category, but of course we should also take into account the way these sets fit together. This is governed by the combinatorics of how the shapes $[n]$ relate to each other. And this is summarised by saying that they are the object of the simplex category $\Delta$. The morphisms are the monotone maps. This means that the sets $Fun([n],C)$ fit together to form a simplicial set, that is presheaf on $\Delta$. This is called the nerve of $C$.

This works not just for categories but also for functors, and defines altogether a functor from categories to simplicial sets, called the nerve functor.

Joachim Kock (Mar 17 2021 at 15:42):

Theorem (attributed to Grothendieck): the nerve functor is fully faithful, and the simplicial sets in the image are characterised by the Segal condition. The Segal condition can be formulated in many different ways, most of which involve the language of face and degeneracy maps, and simplicial identities, and a lot of notation (which has turned out to be so useful in algebra and topology, that people tend to use it without explaining it). But here is one non-technical way to understand the Segal condition: by definition a 2-simplex in $C$ is a functor $[2] \to C$, which is to say a commutative triangle in $C$. The Segal condition says that such a triangle is completely determined by its two short edges. This is true for categories because of the ability to compose arrows to reconstruct the long edge. The content of the theorem is that the Segal condition actually characterises categories.

Joachim Kock (Mar 17 2021 at 15:44):

The nerve theorem is really important.

Joachim Kock (Mar 17 2021 at 15:45):

The importance comes from connecting category theory with topology and combinatorics, which happens because simplicial sets is a combinatorial model for topological spaces. In particular, one can now apply homotopy techniques in category theory. In fact large parts of the theory of $\infty$-categories is developed in the setting of simplicial sets. In fact, Joyal defined $\infty$-categories (quasi-categories) to be certain simplicial sets, satisfying a condition weaker than the Segal condition.

Joachim Kock (Mar 17 2021 at 15:49):

So where did $\Delta$ come from? And how did it happen that something algebraic (the notion of category) could be encoded with conditions that have a very geometric flavour? In fact the Segal condition is very nearly a sheaf condition, because it says that the value on $[2]$ (a chain of length 2) is determined by its value on the two edges of the chain, and the way $[2]$ is covered by $[1]$ and $[1]$. However, it is not precisely a sheaf condition. If it were, then categories would form a topos. But $Cat$ is not a topos. (For example it is not locally cartesian closed.) So these questions, and the near-sheaf-ness of the Segal condition, have been analysed deeply by many people. A good place to start reading about it is a beautiful blog post by Tom Leinster called How I learned to love the nerve construction, in which he explains the beginning of Weber theory, a general theory of nerve theorems -- for the nerve theorem for categories is only the beginning!

https://golem.ph.utexas.edu/category/2008/01/mark_weber_on_nerves_of_catego.html

Joachim Kock (Mar 17 2021 at 15:54):

Here is a executive summary: the forgetful functor from categories to directed graphs has a left adjoint, the free-category functor. Categories are algebras for the resulting monad. This monad takes a directed graph and introduces many new edges, namely a new edge for each linear path in the graph. So where in the original graph $G$ the set of edges was $Hom([1], G)$, the new graph (underlying the free category on the graph) has edge set $\sum_n Hom([n],G)$. What we see here is that the algebraic structure is introduced by allowing more complicated shapes.

So far we have not used $\Delta$, only its 'graphical' or inert part, which we denote $\Delta_{\text{inert}}$. This is the full subcategory the category of directed graphs consisting of the nonempty finite linear graphs, henceforth called linorders. Now we construct $\Delta$: it is the Kleisli category of the category monad restricted to $\Delta_{\text{inert}}$. In other words, the objects are the same, but as morphism we now allow not just the graphical maps but also maps between free categories on these linear orders.

Joachim Kock (Mar 17 2021 at 16:00):

$\Delta_{\text{inert}}$ is a more geometric category than $\Delta$. In fact the idea of covering $[2]$ with two copies of $[1]$ now does work to define a Grothendieck topology. (It did not work up in $\Delta$ since there were too many maps --- too much algebra!) What it says is that among all the linear graphs $[n]$ there are some special small ones called elementary linear graphs, namely $[0]$ and $[1]$, and every linorder is canonically a colimit (in $\Delta_{\text{inert}}$) of its elementary sub-linorders. It follows that presheaves on elementary linorders (these presheaves are the same things as directed graphs) are the same thing as sheaves on $\Delta_{\text{inert}}$ (for that Grothendieck topology).

Joachim Kock (Mar 17 2021 at 16:02):

Now we can finally interpret the Segal condition: it says that a simplicial set (presheaf on $\Delta$) is the nerve of a category if and only if its restriction to $\Delta_{\text{inert}}$ is a sheaf. It says that categories are simplicial sets for which longer chains are determined by shorter chains. (Well, I don't know if this heuristic formulation is any better than the Segal condition iself. Work it out for yourself and formulate it heuristically as you find best! The good thing about having a powerful language like sheaves is that it is precise and does not depend on heuristic interpretations.)

Joachim Kock (Mar 17 2021 at 16:03):

Furthermore, the proof of the nerve theorem now becomes something very formal, which follows from some very basic properties of the category monad, namely that it is a local right adjoint monad (cf. Weber). This ensures that there is a factorisation system on $\Delta$ where the right class consists of the inert maps and the left class (called active maps) are those maps generated by the monad. This is where the algebra takes place.

Joachim Kock (Mar 17 2021 at 16:10):

Altogether we have split the notion of category into an algebraic part and a geometric part. The algebraic part is composition and identity arrows. The geometric part is all the underlying bookkeeping, about source and target, how arrows are required to be lined up (glued together) to a chain before it makes sense to compose them.

Joachim Kock (Mar 17 2021 at 16:14):

Aside: the (active, inert) factorisation system is called (generic, free) in Weber's work. 'Free' comes from the fact that they are the images of the downstairs map under the free part of the monad. 'Generic' comes from earlier work of Joyal on analytic functors. The (active, inert) terminology was introduced by Lurie, apparently unaware of Weber's work. This terminology is now the dominant one. Not because we should copy all Lurie's terminology and notation, but it is quite nice: the active part is the part expressing algebraic operations. The inert part is the underlying bookkeeping. So I ended up adopting Lurie's terminology, although I am a fan of Weber theory (and a proud collaborator of Mark Weber).

Fawzi Hreiki (Mar 17 2021 at 16:16):

Joachim Kock said:

Altogether we have split the notion of category into an algebraic part and a geometric part. The algebraic part is composition and identity arrows. The geometric part is all the underlying bookkeeping, about source and target, how arrows are required to be lined up (glued together) to a chain before it makes sense to compose them.

I recall reading somewhere that every essentially algebraic (i.e. finite limit) theory gives a finitary monad on a presheaf category and vice versa.

Nathanael Arkor (Mar 17 2021 at 16:20):

This is true because the category of models of an essentially algebraic theory is a locally finitely presentable category, which is a finitarily reflective subcategory of a presheaf category (and hence induces an idempotent monad on the presheaf category).

Joachim Kock (Mar 17 2021 at 16:20):

Here is a memory card, before we move on to operads etc.:

$\bullet$ categories are probed by linorders and elementary linorders.

$\bullet$ Presheaves on elementary linorders are the same as sheaves on linorders.

$\bullet$ The category monad lives on that presheaf category, and works by allowing more shapes, all linorders instead of just elementary linorders.

Fabrizio Genovese (Mar 17 2021 at 16:20):

I'm getting lost, who is $[n]$?

Fabrizio Genovese (Mar 17 2021 at 16:21):

Also, how come $[2]$ picks a commutative triangle? Shouldn't it just pick two arrows if $[2]$ represents a chain of two arrows?

Fabrizio Genovese (Mar 17 2021 at 16:21):

In that case the Segal condition would be trivial I guess, so I fear I'm missing something.

Fawzi Hreiki (Mar 17 2021 at 16:21):

No, because its the walking composable pair

Nick Hu (Mar 17 2021 at 16:22):

Fabrizio Genovese said:

Also, how come $[2]$ picks a commutative triangle? Shouldn't it just pick two arrows if $[2]$ represents a chain of two arrows?

I think the idea is that the third edge of the triangle is the composite

Fabrizio Genovese (Mar 17 2021 at 16:22):

Yeah, but if that's so why do you need the Segal condition to say it? It should be obvious from the fact that you have a functor, no?

Fawzi Hreiki (Mar 17 2021 at 16:23):

You don't need the Segal condition to say that.

Joachim Kock (Mar 17 2021 at 16:23):

Fabrizio Genovese said:

I'm getting lost, who is $[n]$?

In $\Delta_{\text{inert}}$ it is the linear graph with $n$ edges. In $\Delta$ it is the $n$-simplex, which is the free category on the linear graph with $n$ edges.

Fabrizio Genovese (Mar 17 2021 at 16:23):

Can you spell out what a linear graph is?

Fabrizio Genovese (Mar 17 2021 at 16:23):

That also came a bit out of nowhere for me T_T

Fabrizio Genovese (Mar 17 2021 at 16:24):

You mean 1-> 2 -> ... -> n?

Joachim Kock (Mar 17 2021 at 16:25):

Fabrizio Genovese said:

Also, how come $[2]$ picks a commutative triangle? Shouldn't it just pick two arrows if $[2]$ represents a chain of two arrows?

This is the subtlety: the nerve refers to $\Delta$ where $[2]$ is a triangle, but the sheaf interpretation of the Segal condition refers to $\Delta_{\text{inert}}$, where $[2]$ is a linear graph with 2 edges (chain of two arrows).

Fabrizio Genovese (Mar 17 2021 at 16:26):

I'm really lost T_T

Fabrizio Genovese (Mar 17 2021 at 16:26):

Anyway, I don't want to interrupt, I'll try to understand this by myself

Tom Hirschowitz (Mar 17 2021 at 16:27):

Yes, a linear graph is one of the form 1 → 2 → … → n.

Fawzi Hreiki (Mar 17 2021 at 16:27):

The graphs of the form $\bullet \rightarrow \bullet \rightarrow ... \bullet \rightarrow \bullet$ generate the categories of finite ordinals.

Fawzi Hreiki (Mar 17 2021 at 16:27):

You can think of these things either as finite ordinals, or as simplices

Joachim Kock (Mar 17 2021 at 16:27):

Fabrizio Genovese said:

Yeah, but if that's so why do you need the Segal condition to say it? It should be obvious from the fact that you have a functor, no?

Yes, it is obvious that the nerve of a category satisfies this condition. The content of the theorem is that the Segal condition characterises categories. Meaning that if you have a simplicial set, defined in any crazy way, if it satisfies the Segal condition, then there is a category whose nerve is isomorphic to it as simplicial sets.

Fawzi Hreiki (Mar 17 2021 at 16:28):

That's because the composites (which here are the finite paths) are like 'fillers' for the 'boundaries'

Fawzi Hreiki (Mar 17 2021 at 16:30):

In particular, the category generated by $\bullet \rightarrow \bullet \rightarrow \bullet$ classifies commutative triangles. The simplex category contains all of these finite ordinals (and the functors between them, which just amount to monotone maps)

Fabrizio Genovese (Mar 17 2021 at 16:31):

Joachim Kock said:

Fabrizio Genovese said:

Yeah, but if that's so why do you need the Segal condition to say it? It should be obvious from the fact that you have a functor, no?

Yes, it is obvious that the nerve of a category satisfies this condition. The content of the theorem is that the Segal condition characterises categories. Meaning that if you have a simplicial set, defined in any crazy way, if it satisfies the Segal condition, then there is a category whose nerve is isomorphic to it as simplicial sets.

Ah!

Fabrizio Genovese (Mar 17 2021 at 16:31):

Ok, so it was going the other way around, ok

Joachim Kock (Mar 17 2021 at 16:31):

Fabrizio Genovese said:

You mean 1-> 2 -> ... -> n?

Yes, except that the simplicial machinery dictates we should start the chain with $0$: This is just so that if you write it out with all the composites, so that it becomes a simplex, then $n$ is the dimension. So $[3]$ is $0 \to 1 \to 2 \to 3$.

Fabrizio Genovese (Mar 17 2021 at 16:32):

Yeah, I was reading a bit of algebraic tolopogy with very scarce results on the side these days, so this I get :smile:

Fabrizio Genovese (Mar 17 2021 at 16:34):

Things are miracolously starting to get a bit clearer for me anyway, thanks for the patience :grinning:

Joachim Kock (Mar 17 2021 at 16:44):

More about the distinction between $\Delta_{\text{inert}}$ and $\Delta$. The objects in $\Delta_{\text{inert}}$ are linear graphs (it's a full subcategory of the category of directed graphs. There are several pictures above. Hence the maps must be graph maps. For example there are
only two injective graph maps from $[1]$ to $[2]$, namely the one that hits the first edge and the one that hits the second edge. it is also clear that a longer $[n]$ can be covered by copies of $[1]$ in this way, and it is easy to work out that it is actually a colimit of copies of $[1]$ glued along copies of $[0]$.

In $\Delta$ we interpret $[n]$ as an ordinal with $n+1$ elements, and it could be pictured as $0 < 1 < \cdots < n$. That's a category, not just a graph. In fact it is the free category on the graph version of $[n]$. At first it is confusing to use the same notation for the two kinds of objects, but in the end it is both harmless and logical: $\Delta$ is the subcategory of $Cat$ spanned by the free categories on linear graphs, or in other words, the Kleisli category of the free-category monad, but restricted to $\Delta_{\text{inert}}$. So the objects of the two categories are naturally identified. Furhtermore, the morphisms in $\Delta_{\text{inert}}$ are naturally identified with certain morphisms in $\Delta$, namely those that are in the image of the free-category functor. It is easy to characterise these maps explicitly: they are the functors $\phi: [m]\to [n]$ that are distance preserving, meaning that $\phi(i+1) = \phi(i)+1$.

Fabrizio Genovese (Mar 17 2021 at 16:49):

Yeah, because in $\Delta_\text{inert}$ you can't send edges to path of edges

Joachim Kock (Mar 17 2021 at 16:52):

I guess I'll have to leave the next installment for tomorrow: multicategories and operads.
But just as a teaser, here are the memory cards for them (or maybe it should be called cheat-sheet):

Joachim Kock (Mar 17 2021 at 16:53):

$\bullet$ multicategories are probed by planar rooted trees and elementary planar rooted trees.

$\bullet$ Presheaves on elementary planar rooted trees are the same as sheaves on planar rooted trees.

$\bullet$ The free-multicategory monad lives on that presheaf category, and works by allowing more shapes, all planar rooted trees instead of just elementary planar rooted trees.

Joachim Kock (Mar 17 2021 at 16:53):

And then come symmetric operads:

Joachim Kock (Mar 17 2021 at 16:54):

$\bullet$ (coloured) operads are probed by rooted trees and elementary rooted trees.

$\bullet$ Presheaves on elementary rooted trees are the same as sheaves on rooted trees.

$\bullet$ The free-operad monad lives on that presheaf category, and works by allowing more shapes, all rooted trees instead of just elementary rooted trees.

Fabrizio Genovese (Mar 17 2021 at 16:56):

Thanks for what you explained so far!

Joachim Kock (Mar 17 2021 at 16:57):

This is the first point where symmetries start to pop up and complicate things
:strangely-enjoying-suffering smiley:

Joachim Kock (Mar 17 2021 at 16:57):

I'll eventually come to Petri nets.

Fawzi Hreiki (Mar 17 2021 at 18:31):

The interesting thing is that you don't even need all simplices (or linear graphs) to get a nerve construction for categories, just the first three

Martti Karvonen (Mar 17 2021 at 19:07):

I guess the walking composable pair of arrows alone is enough to get a fully faithful nerve, right?

Fawzi Hreiki (Mar 17 2021 at 20:56):

Yes. It's because the category monad on directed graphs has a presentation with max arity the composable pair.

Jade Master (Mar 17 2021 at 21:04):

Interesting, thanks Joachim :)

Fawzi Hreiki (Mar 17 2021 at 21:12):

Martti Karvonen said:

I guess the walking composable pair of arrows alone is enough to get a fully faithful nerve, right?

Actually, I'm not so sure. I think you need the full subcategory on all the arties (i.e. $1, 2, 3$) since I don't know if $3$ alone is dense in $\text{Cat}$

Martti Karvonen (Mar 17 2021 at 21:25):

I was thinking that it would be: the restricted yoneda is faithful as knowing what $F\colon\mathbf{C}\to\mathbf{D}$ does on functors $\mathbf{3}\to\mathbf{C}$ lets you know what $F$ does on maps and on objects. The trickier part I guess is checking that it is full: given a function $hom(\mathbf{3},\mathbf{C})\to hom(\mathbf{3},\mathbf{D})$ that is natural for endofunctors on $\mathbf{3}$, naturality should imply that it sends constant functors to constant functors and hence objects to objects and identities to ids, and I think one should also be able to show (by considering the functor sending $0\to1$ to $0\to 2$) that composites are preserved.

John Baez (Mar 17 2021 at 23:10):

Fabrizio Genovese said:

Also, how come $[2]$ picks a commutative triangle? Shouldn't it just pick two arrows if $[2]$ represents a chain of two arrows?

A chain of two arrows is the same thing as a commutative triangle.

We've got $f: x \to y$, and $g: y \to z$, and $h : x \to z$ which must equal $gf$.

John Baez (Mar 17 2021 at 23:10):

That's a commutative triangle.

John Baez (Mar 17 2021 at 23:13):

This "shift by 1" is a general thing: a chain of $n$ arrows is the same thing as a commutative $(n+1)$-simplex.

Amar Hadzihasanovic (Mar 18 2021 at 07:28):

A triangle is a 2-simplex, and in general chains of $n$-arrows do correspond to $n$-simplices. It is true that there are a couple of “shifts-by-1” related to simplices, though:

• an $n$-simplex has $n+1$ vertices / corresponds to the ordinal $n+1$ / (a number of equivalent facts)
• the 2-dimensional source and target boundary of an oriented $n$-simplex is a 2-dimensional pasting diagram with $n$ arrows in the source and 1 arrow in the target, so $n+1$ arrows in total.

In the nerve of a category, the arrow in the target is the unique composite of the $n$ arrows in the source. An instance of this is “2 arrows + their composite = 3 arrows (a commutative triangle)” that you were discussing, so I think that the second “shift” is what John was thinking of.

Amar Hadzihasanovic (Mar 18 2021 at 07:30):

It has now occurred to me that there was probably just a typo in John's message and that “$(n+1)$-simplex” should have been “$(n+1)$-gon”.

Jason Erbele (Mar 18 2021 at 11:29):

I think John's $(n+1)$-simplex is correct: you don't just get one composite arrow when $n>1$. Also, the composite arrow is pointing the wrong way around to give an $(n+1)$-gon that you could actually cycle around. I'd prefer my directed polygons to be cyclic, at least.

Jason Erbele (Mar 18 2021 at 11:34):

Based on the teaser for multicategories and operads, I'm sure I'm a bit confused. My (mis?)understanding is that any rooted tree will be a planar graph, so I don't see how "planar rooted trees" and "rooted trees" are supposed to be different.

Fabrizio Genovese (Mar 18 2021 at 11:35):

John Baez said:

Fabrizio Genovese said:

Also, how come $[2]$ picks a commutative triangle? Shouldn't it just pick two arrows if $[2]$ represents a chain of two arrows?

A chain of two arrows is the same thing as a commutative triangle.

We've got $f: x \to y$, and $g: y \to z$, and $h : x \to z$ which must equal $gf$.

Yeah, my confusion came from the fact that this is true when you consider functors from $[2]$ to a category, so I wasn't understanding why the Segal condition was needed. Then I understood that, when you consider functors $[2] \to \mathbf{Set}$, you can map things to pretty much whatever you want. If I understand things correctly, the Segal condition precisely identifies which functors among those come from functors $[2] \to \mathcal{C}$ when $\mathcal{C}$ is a category.

Fabrizio Genovese (Mar 18 2021 at 11:37):

All in all, I was reading things upside down: We are asking "when does a random complex represent a category?", and looking for conditions that characterize the question. I was giving the question for granted, so I wasn't really getting why all the Segal condition stuff had to be. :smile:

Amar Hadzihasanovic (Mar 18 2021 at 13:31):

Jason Erbele said:

I think John's $(n+1)$-simplex is correct: you don't just get one composite arrow when $n>1$. Also, the composite arrow is pointing the wrong way around to give an $(n+1)$-gon that you could actually cycle around. I'd prefer my directed polygons to be cyclic, at least.

I don't understand the first comment.
For the second one, that's in conflict with how category theorists use “commutative triangle”, “commutative square”, or Mac Lane's “pentagon”, which are never cyclic directed polygons.

Amar Hadzihasanovic (Mar 18 2021 at 13:32):

John wrote “commutative $(n+1)$-simplex” and I think he meant to write “commutative $(n+1)$-gon” generalising the commutative triangle you get when $n=2$...

John Baez (Mar 18 2021 at 16:26):

Amar is right - this was wrong:

John Baez said:

This "shift by 1" is a general thing: a chain of $n$ arrows is the same thing as a commutative $(n+1)$-simplex.

It's a commutative $n$-simplex.

The "shift by 1" comes in when you say it this way: a functor from a linearly ordered $n$-element set into a category $C$ is the same commutative $(n+1)$-simplex in that category.

As you can see, I often get tripped up by this shift.

Jason Erbele (Mar 18 2021 at 17:05):

Amar Hadzihasanovic said:

Jason Erbele said:

[...] I'd prefer my directed polygons to be cyclic, at least.

[...] that's in conflict with how category theorists use “commutative triangle”, “commutative square”, or Mac Lane's “pentagon”, which are never cyclic directed polygons.

Fair point. I retract my insistence on cyclic directed polygons.

Ulrik Buchholtz (Mar 18 2021 at 17:10):

Jason Erbele said:

Based on the teaser for multicategories and operads, I'm sure I'm a bit confused. My (mis?)understanding is that any rooted tree will be a planar graph, so I don't see how "planar rooted trees" and "rooted trees" are supposed to be different.

I think there's an unfortunate terminological ambiguity re “planar”. Here it's meant as a structure, meaning an ordering of the edges emanating from a node, rather than the mere property, as it is commonly used for graphs in general. (The structure could also be an actual embedding in the plane, but that's presumably not meant here.)

John Baez (Mar 18 2021 at 17:17):

For a traditional graph theorist, planarity is a property of a graph:

• Planar graph

For a lot of categorical work, like on operads, it's crucial to treat planarity as a structure.

I think Ross Street may have been the one to coin the term "plane tree" as a term for a tree with a planar structure. This is a great pun because there's a kind of tree called a plane tree.

John Baez (Mar 18 2021 at 17:18):

So one could follow suit and use "plane" for the structure, "planar" for the property.

John Baez (Mar 18 2021 at 17:23):

A plane tree of height $n$ is a functor $T: [n]^{\rm op} \to \Delta$, where $[n] = \{0,\dots,n\}$ is a linearly ordered set regarded as a category, such that $T(0) = [0]$. This captures the idea that branches merge as we go down the tree, finally all meeting in the root.

Joachim Kock (Mar 18 2021 at 19:02):

The terminology plane tree sounds like a good idea. I'll try to adopt it, but it is difficult to change terminology habits...
The trees I want to talk about are a bit different from those just mentioned by John though.

Joachim Kock (Mar 18 2021 at 19:07):

I want to copy over everything I wrote yesterday from the case of categories to the case of multicategories.

A multicategory is like a category, but where the source of an arrow is allowed to be a list of objects instead of a single object. And then you can compose, and composition is associative and there are identity arrows. Instead of talking about arrows, it is common to talk about operations. The arity of an operation is the number of sources. Operations are often pictured like a small tree with a single node, one output edge, and $n$ input edges Composition is now not just about two operations, but rather about feeding n operations into an $n$-ary operation, and of course it only makes sense if the target of each of these n operations matches the source slot it is fed in to. The configuration of operations required for a composition is thus a 2-level tree of operations: the receiving operation at the bottom node of the tree, and the n other operations at the nodes at the top level. Composition should be associative and there should be identity operations. Associativity is not just about three operations in a row, but rather about three levels: the relevant configuration of operations for stating the associative law is: at the lowest of the three levels a single operation, say of arity n. Then at the middle level, $n$ operations to feed into the bottom operation, and finally for each input slot of each of these $n$ operations, yet another operation. Altogether the configuration is that of a 3-level tree of operations. Identity operations must be unary. The identity law makes it viable to picture identity operations as a single edge (decorated by the object it is identity for), without any nodes. The associative and identity laws can be written out with a lot of symbols, but it is a lot more complicated than for ordinary categories. But the upshot is that a multicategory structure is something that allow you to take any plane tree of operations and contract it (by composition) to a single operation (that is, a single corolla decorated by an operation). The trees here are still plane, but thanks to the identity operations, it is not required that these trees are strictly levelled. They can be made levelled by padding with identity operations.

Joachim Kock (Mar 18 2021 at 19:07):

There is a canonical and very nice reference for this: the book of Tom Leinster *Higher operads, higher categories". It is a Cambridge University Press bestseller, but at the same time it is freely available on the arXiv.

Joachim Kock (Mar 18 2021 at 19:13):

The goal is to repeat all the yoga we did for categories --- linear orders, nerves, etc --- but now for multicategories. Categories are the special kinds of multicategories where there are only unary operations: an arrow has one input (its source) and one output (its target). But now we have a slight conflict of intuition: for categories it was important to talk about underlying directed graph, where the objects are vertices and the arrows are edges. For multicategories the operations are pictured as nodes, and the objects as edges! It is possible to revisit the tree interpretation, and invent something called multidirected graphs where there are multiedges with many in and one out vertices. But it is not a very nice route to take, and soon we will consider more general graphs than trees. And we should also think twice before we ditch the super useful string diagram notation that the trees are an example of. It is much better to go back to categories and revisit the combinatorics. It is not so bad: we didn't really use graphs very much, except for the fact that directed graphs are presheaves on $0 \rightrightarrows 1$, so let's forget about directed graphs. We can just interpret arrows as nodes and objects as edges. This means that every arrow is pictured as a node with one incoming edge and one outgoing edge. And then we can interpret $\Delta_{\text{inert}}$ as the category of linear trees. This is only a new graphical interpretation of the same thing: we picture $[n]$ which is $0 \to 1 \to 2 \to \cdots \to n$ as a tree with $n$ nodes (the old edges) and $n+1$ edges (the old vertices).

Joachim Kock (Mar 18 2021 at 19:15):

It is a nice exercise to repeat all the yoga we did for categories in this new language. Here is the revised memory card:

$\bullet$ categories are probed by linear trees and elementary linear trees.

$\bullet$ Presheaves on elementary linear trees are the same as sheaves on linear trees.

$\bullet$ The free-category monad lives on that presheaf category, and works by allowing more shapes, all linear trees instead of just elementary linear trees.

How fun is that!

Joachim Kock (Mar 18 2021 at 19:19):

Now the roadmap is clear: just repeat everything with general plane trees instead of just the linear ones. The main challenge is to get the combinatorics right. What do we actually mean by trees? So far we said the trees are rooted and plane. plane means that at every node, there is given a linear order on the set of input edges. Of course, every rooted tree admits such an order, but it is important that it is actually given as part of the structure. This is needed since operations of a multicategory have lists of inputs, not just a set of inputs. Before saying what rooted means, it is important to be clear about another thing, namely that these trees are allowed to have open-ended edges. Indeed, when we draw a corolla, it has only one node, and a number of incoming edges that do not come from any node (and a single outgoing edge, not leading to any node). Even more shockingly, we allow the tree without any nodes and only a single freefloating edge! This nodeless tree is super important, because it is used to model the identity operations, and indeed to model the objects. The root of a tree is an edge, not a node. It is the choice of an edge not leading to any node. For these reasons, the definitions of tree you find in combinatorics books, defined in terms of graphs or posets, are not well suited for the present purposes. The definitions you find in logic are not ideal either. It is really better to define the notion of tree from scratch, to get precisely what we want. We want trees to be models for configurations of operations in a multicategory. We want trees to be glued together from elementary trees. We can already guess what these should be: they should be the trees corresponding to objects and operations. (Recall that the elementary objects in the category case were $[0]$ for objects and $[1]$ for arrows.)

Joachim Kock (Mar 18 2021 at 19:19):

Let's postpone the good definition to the non-plane case.

Joachim Kock (Mar 18 2021 at 19:32):

Here is a short digression, which can be skipped by anyone unwilling to think about inductive definitions so early in the morning. Let's generate the plane trees as an inductive data type. This means that they should form the initial algebra for a (polynomial) endofunctor. The summands in the functor should correspond to the 'constructors' of the data type: there should be one for each possible arity, and then there should furthermore be one special tree, namely the one without nodes. So the polynomial functor should be $y \mapsto 1+y^* = 1+\sum_{n\in \mathbb{N}} y^n$. The $y^*$ part is the free-monoid monad, or the word monad, which to a given 'alphabet' $y$ assigns the set of all word in $y$. It is a monoid under concatenation. The initial algebra is the solution to the fixpoint equation $y = 1+ y^*$. Let's call the element in the solution set trees. This equation says that a tree is either the trivial tree (no nodes) or it has a bottom node, and on top of that a list of trees. This definition is actually correct, and defines the set of isoclasses of trees of the correct kind. It also gives us a clear picture of what the elementary trees are, namely the constructors. Unfortunately, it is not very combinatorial, and it does not give us interesting notions of morphisms of trees, needed as stand-in for $\Delta_{\text{inert}}$ and $\Delta$.

Spencer Breiner (Mar 18 2021 at 19:42):

You can find some good pictures of these trees (and a very gentle discussion) in our recent paper here.

image.png

Joachim Kock (Mar 18 2021 at 19:47):

But let's proceed without the precise definition, for a moment. We need a category of trees in which every tree is canonically the colimit of its elementary subtrees. In particular, for a tree with two nodes, we need to be able to express it as a gluing of two corollas along a common edge. So we need at least maps that express the inclusion of an edge into a tree. We would also like to do the same for a huge tree: pick and inner edge somewhere, and cut the tree at that edge to obtain two smaller trees. The whole tree should now be the pushout of the two smaller trees over the trivial tree given by the chosen edge. We quickly figure out that the morphism should be full subtree inclusions. Full means that if a node is in the subtree, then all adjacent edges are in the subtree too. In particular it is important that these inclusions are arity preserving: a node in the domain must map to a node in the codomain of the same arity (and the planar structure must be preserved too). Note that this is a local-isomorphism condition, and it makes sense to call such inclusions etale.

Assuming we have formalised this to get a category of trees, which optimistically we denote $\Omega^{\text{pl}}_{\text{inert}}$. The letter $\Omega$ was chosen by Ieke Moerdijk and Ittay Weiss. The decoration 'pl' means plane, and the decoration 'inert' is what makes us so hopeful. It has a full subcategory of elementary trees, which are: the trivial tree $\star$ (the nodeless tree) and all the corollas $C_n$, one for each $n\in \mathbb{N}$. The only full subtree inclusions are the inclusions of the trivial tree into the corollas. There are $n$ maps $\star\to C_n$ hitting the leaf edges, and $1$ map hitting the root edge. This defines a full subcategory $\Omega^{\text{pl}}_{\text{el}} \subset \Omega^{\text{pl}}_{\text{inert}}$.

Done correctly, one now checks that certain colimits exist in $\Omega^{\text{pl}}_{\text{inert}}$ and that every tree is a colimit (iterated pushout) of its elementary subtrees. One defines an obvious grothendieck topology based on this kind of cover, and see that we have

$PrSh(\Omega^{\text{pl}}_{\text{el}}) \simeq Sh(\Omega^{\text{pl}}_{\text{inert}})$

This is promising, but of course we cannot know for sure that we are making the right definition until we have proved the theorems we want. We should always be prepared to go back to the beginning and try something else from scratch.

Joachim Kock (Mar 18 2021 at 19:48):

Non-mathematicians are shocked when they hear we work like that: we decide the theorems in advance and then we just sit down to invent a fantasy world where those theorems are true. Thinking about it like this, it is really a huge privilege to be a mathematician. It's almost like being an engineer or a youtuber.

Joachim Kock (Mar 18 2021 at 19:50):

So, back to work. What's the free-multicategory monad and where does it live? It lives on the category of coloured collections. It is easier first to understand non-coloured collections, corresponding to the one-object multicategories. One object multicategories are the same thing as nonsymmetric operads (with only one colour). The colourless version of collection is just: a sequence of sets $(A_n \mid n\in \mathbb{N})$. So it's like an operad, sets of operations all arities, but without the ability to compose them. For a coloured collection, say with object set $I$, we also need to indicate the inputs and the output --- these are objects. This means that the input 'profile' of an operation must be indexed by a list of objects, or a word in the set of objects, and the output profile must be indexed by just a single object. So a collection is a cofiguration of sets $(A_{w,i} \mid w\in I^*, i \in I)$. (Note that the $\mathbb{N}$ that appears in the one-coloured case is really $1^*\times 1$, the set of pairs consisting of a word of ones and a single one.) It is also required to be able to extract the inputs and outputs from an operation, which is given simply by the projection maps sending an operation in $A_{w,i}$ to $(w,i)$.

Joachim Kock (Mar 18 2021 at 19:51):

All this is precisely to say that a coloured collection is a presheaf on $\Omega_{\text{el}}^{\text{pl}}$, the category of elementary plane trees. (Or equivalently, a sheaf on $\Omega_{\text{inert}}^{\text{pl}}$.)

Joachim Kock (Mar 18 2021 at 19:52):

$\Box$ I have read and understood this and agree [Cancel] [OK]

Joachim Kock (Mar 18 2021 at 19:57):

Now we can describe the free-multicategory monad. It takes as input a coloured collection $F: (\Omega_{\text{el}}^{\text{pl}})^{\text{op}} \to \mathbf{Set}$. The idea of the free multicategory is that it should just evaluate on general trees instead of just corollas. This is possible since we can also regard $F$ as a sheaf on $\Omega_{\text{inert}}^{\text{pl}}$ rather than a presheaf on $\Omega_{\text{el}}^{\text{pl}}$. And we should sum over all possible such trees. In the case of ordinary categories we did not have to say anything more, but now we have the arity to think about.

The formula for the free multicategory on $F$ is the coloured collection $\overline{F}$ given by:

--- nothing changes on the objects: $\overline{F}[\star] = F[\star]$. Remember that $\star$ is the trivial tree, which indexes the objects of a coloured collection or a multicategory.)

--- On a corolla $C$, it takes the value $\sum_{T\in C\text{-tree}} F[T]$. The whole point is to know what to sum over here. Let's say $C$ is the corolla with $n$ leaves. The a $C$-tree is a tree with $n$ leaves. More precisely, it is a tree $T$ with a monotone bijection from the set of leaves of $C$ to the set of leaves of $T$. But there is at most one possible monotone map between two linearly ordered sets, and it exists precisely when they are of the same size, in this case $n$. Finally it should be clarified that $C\text{-tree}$ is the set of iso-classes of $C$-trees.

To evaluate a coloured collection $F$ on a tree $T$ is to evaluate on all its elementary trees of $T$ and take the limit over all those evaluations. That's what it means to be a sheaf! So a good way to see it is to say that is to consider all $F$-decorations of the tree: each node must be decorated by an operation of $F$ (because $F[C]$ is the set of $n$-ary operations of $F$, if $C$ is an $n$-ary corolla), and each edge must be decorated by an object of $F$, since $F[\star]$ is the set of objects. These decorations must be compatible in the obvious way. So altogether $\sum_{T\in C\text{-tree}} F[T]$ is the set of $F$-trees with $n$ leaves (assuming as we do that $C$ is a corolla with $n$ leaves).

The operations of $F$ were the $F$-corollas. The operations of the free multicategory $\overline{F}$ are the $F$-trees.

So tree plays the role for multicategories the role that chains (or paths) played for categories.

Why is this a monad? Because $\overline{\overline{F}}$ has as operations $\overline{F}$-trees, meaning trees of $F$-trees. But a tree of $F$-trees can be flattened to a single $F$-tree, and that's the monad multiplication.

Exercise: figure out that the algebras for this monad are precisely multicategories.

Joachim Kock (Mar 18 2021 at 20:01):

Now we have the underlying presheaf category and the monad. Now we can construct the big category of trees, denoted $\Omega^{\text{pl}}$, which is the multi-version $\Delta$. It is defined as the Kleisli category of the monad, restricted to $\Omega^{\text{pl}}_{\text{inert}}$. The formal description of the new maps is: they are the multicategory-morphisms between free multicategories on plane trees. Unpack that a bit, and find that $\Omega^{\text{pl}}$ has node-refinement maps, whereby a node can map to a subtree with the same number of leaves. These new maps are called active maps, and the old ones are called inert. One checks that every map in $\Omega^{\text{pl}}$ factors uniquely as an active map followed by an inert map.

Going back to $\Delta$ and its arrows, which are functors between free categories on linear trees, we see that the active maps there could also be described as node refinements: the map $[1] \to [2]$ which picks out the long edge of a triangle can also be seen as the refinemen of a one-node linear tree to a two-node linear tree.

Finally, one can define the plane-dendroidal nerve of a multicategory $X$ as the presheaf on $\Omega^{\text{pl}}$ given by $T \mapsto Hom(T,X)$, in strict analogy with the nerve of a category. Presheaves on $\Omega^{\text{pl}}$ are called plane-dendroidal sets.

And then one can prove a nerve theorem stating that a plane-dendroidal set is the plane-dendroidal nerve of a multicategory if and only if its restriction to $\Omega^{\text{pl}}_{\text{inert}}$ is a sheaf. That's called the plane-dendroidal Segal condition. This theorem is a corollary of Weber's easy nerve theorem. All that is needed is to check that the free-multicategory monad is a local right adjoint monad.

Joachim Kock (Mar 18 2021 at 20:06):

Right now, at the polynomial workshop, Thorsten Altenkirch, is explaining initial algebras from the viewpoint of type theory...

Joachim Kock (Mar 18 2021 at 20:10):

I stop writing now, but it is my task to watch the chat.

Jason Erbele (Mar 18 2021 at 20:56):

This is very cool. I'm still digesting what you've said so far, but I'm beginning to see the broad strokes of a very nice story.

As a bit of an aside, it took me longer to parse "word of ones" here than I care to admit:
Joachim Kock said:

(Note that the $\mathbb{N}$ that appears in the one-coloured case is really $1^*\times 1$, the set of pairs consisting of a word of ones and a single one.)

But then it dawned on me, it's basically Woodstock talk.

Fabrizio Genovese (Mar 18 2021 at 22:18):

Ok, the most surprising thing for me is that the multicategory version is really much much easier to understand than the category version, at lest for me.

Fabrizio Genovese (Mar 18 2021 at 22:19):

I guess this is because its intuition and jargon is somewhat closer to things one can experience in programming. My geometric intuition is "I cannot really tell a triangle and a sphere apart", so once you remove geometric stuff from geometry, that works ok for me. :smile:

Fabrizio Genovese (Mar 18 2021 at 22:20):

(I intentionally picked a triangle and a sphere to avoid the usual sassy topologist chiming in and saying "oh, but a circle and a triangle are the same thing!" :stuck_out_tongue: )

John Baez (Mar 18 2021 at 22:21):

So you're like a super-topologist, who can't tell the difference between a coffee cup and a cinnamon bun.

Fabrizio Genovese (Mar 18 2021 at 22:26):

I am a supertopologist: All topological objects are the same thing, everything contracts to a point. To a question mark, really!

GhaS Shee (Mar 19 2021 at 04:27):

Thanks for the sharing!
Really, this thread could help me for extending my intuition of ∞-categories to ∞-operads, before reading Tom Leinster's book :big_smile:

Joachim Kock (Mar 21 2021 at 21:13):

There were interesting remarks about the possibility of getting a fully faithful nerve without using all of $\Delta$ but using only up to simplicial degree 2 or 3. This is indeed possible, and something similar can be said about multicategories and $\Omega^{\text{pl}}$. However, other nice features of the theory do not survive this reduction. In particular there is no monad :-( It is also a pity, if you only allow chains of length $3$ or trees of height at most $3$, that you would not be able to glue trees freely anymore. It would always be necessary to count before determining if a colimit exists. It is really much nicer to work with the whole thing without thinking about economy. That does not prevent you, in some isolated argument or computation or construction, to invoke one of those coskeletality facts, and say 'it is enough to check this up to simplicial degree $3$ since the Segal condition then takes care of all higher degrees'.

Joachim Kock (Mar 21 2021 at 21:16):

I mentioned a theorem I called Weber's easy nerve theorem. That's a silly name of course, and I already regret I called it that. It is just because it is an easy-to-use special case of the full theorem. Here is the easy version:

Let $T$ be a local right adjoint monad on a presheaf category $PrSh(C)$. Let $D$ be the Kleisli category of the monad, restricted to the representables. Then the nerve functor from $T$-algebras to presheaves on $D$ is fully faithful and the image is characterised by a Segal condition on $C$.

We saw two examples: first the free-category monad on the category of directed graphs, giving the classical nerve theorem for categories. Second, the free-multicategory monad on the category of coloured collections. Here are some more: for $n \geq 1$, the free-strict-$n$-category monad on the category of $n$-globular sets.

Joachim Kock (Mar 21 2021 at 21:18):

The nice thing about the situation of the 'easy' nerve theorem is that the local-right-adjointness of the monad gives a canonical notion of elementary objects called 'arities', and then there is a sheaf-presheaf relationship between the representables and the elementary objects just like in the two examples we have seen.

Joachim Kock (Mar 21 2021 at 21:20):

The general theorem abstracts this situation to allow more general monads on more general categories, at the price of having to specify the arities as part of the data, and then there are some more advanced condition required, in terms of left Kan extensions. The original reference is [Mark Weber: Familial 2-functors and parametric right adjoints, TAC 2007]. A good place to start reading about all this is [Clemens Berger, Paul-André Melliès, Mark Weber: Monads with arities and their associated theories, JPAA 2012]. It this paper there are some simplifications, and some very nice further examples regarding Lawvere theories.

Joachim Kock (Mar 21 2021 at 21:22):

Recently Hongyi Chu and Rune Haugseng have taken these ideas as an axiomatic basis for theories of generalised operads (in the more general setting of $\infty$-categories). But instead of starting with the monad (an algebraic structure), they start with purely combinatorical structure: a factorisation system (called active-inert) and a notion of elementary object. From there they 'reconstruct' monad and notions of operads and so on:

[Hongyi Chu and Rune Haugseng: Homotopy-coherent algebra via Segal conditions, arXiv:1907.03977].

Rune spoke about this Friday at the Workshop on Polynomial Functors. You can watch his nice talk on YouTube.

Joachim Kock (Mar 21 2021 at 21:24):

A related approach is in the recent work of Clemens Berger on moment categories, certain categories that can encode the combinatorics of various generalisations of operads:

[Clemens Berger: Moment categories and operads, arXiv:2102.00634]

Joachim Kock (Mar 21 2021 at 21:25):

But now I want to move on: the next case is operads.

Joachim Kock (Mar 21 2021 at 22:18):

Now for the case of operads, by which I mean coloured symmetric operads. Compared to a multicategory, an operad has symmetric-group actions on the input slots. This means that for a given operation, if the input slots are permuted, then the result should again be an operation. And then there are compatibility conditions ensuring that these symmetric-group actions behave well with composition.

Joachim Kock (Mar 21 2021 at 22:20):

The colours are like the objects of a multicategory. Many interesting operads have only one colour. For example, for any set $A$ we have the endomorphism operad denoted $End(A)$, whose $n$-ary operations are the set maps $A^n \to A$. Another important example is the terminal operad $Comm$, characterised by having only one operation in each arity (and hence trivial group actions).

Joachim Kock (Mar 21 2021 at 22:23):

An algebra for an operad $P$ is an operad map into an endomorphism operad. That is, it is the choice of a set $A$ and an operad map $P \to End(A)$. One can view an algebra as an concrete realisation of the operations of the operad. The structure can be spelled out to maps $A^n \times P_n \to A$ (subject to some nonsurprising axioms). For example, an algebra for $Comm$ is a commutative monoid. The interest in operads often comes from their algebras, and in this sense the focus of operads is a bit different from that of multicategories.

Joachim Kock (Mar 21 2021 at 22:26):

We repeat all the same movements once more, now for operads. An operad has an underlying (coloured) symmetric sequence (or symmetric collection). That's a sequence $(P_n \mid n\in \mathbb{N})$ of set-representations of the symmetric groups, but with colours. The one-colour case is just a sequence of symmetric-group representations. In combinatorics, this is called a species. There is a subtitutional monoidal structure on the category of species, for which the monoids are precisely operads.

Joachim Kock (Mar 21 2021 at 22:29):

In the coloured case, one has to keep track of the input colours and the output colour, so in arity $n$ there are actually $n+1$ colours to keep track of. One nice way to interpret this (suprise, surprise) is as a presheaf on a category of elementary trees. These are now trees without planar structure, and elementary means that they have no internal edges, hence at most one node. So they are just the trivial (node-less) tree and all the corollas. The object $$\star$ parametrises the colours of a coloured symmetric sequence, and the each object $C_n$ parametrises the $n$-ary operations. There are $n+1$ maps from the trivial tree $\star$ to each corolla $C_n$, and there are no maps between corollas of different arity. There are $n!$ self-maps of $C_n$ (which of course interchange the $n$ maps $\star\to C_n$ to the leaves). These account for the symmetric-group actions on the sets of operations.

Joachim Kock (Mar 21 2021 at 22:31):

The elementary trees are just a special case of general trees (which are rooted, but not given a planar structure). With morphisms given by full subtree inclusions, we get a category of trees $\Omega_{\text{inert}}$ and a full subcategory $\Omega_{\text{el}}$. Again, every tree is canonically the colimit of its elementary subtrees, and $PrSh(\Omega_{\text{el}}) \simeq Sh(\Omega_{\text{inert}})$.

Joachim Kock (Mar 21 2021 at 22:33):

The forgetful functor from operads to collections has a left adjoint, the free operad functor, which is given by evaluating on general trees instead of just evaluating on elementary trees. The Moerdijk--Weiss category of trees $\Omega$ is obtained as the Kleisli category of the resulting monad, restricted to $\Omega_{\text{inert}}$. In addition to the original maps (the inert maps) it has active maps, which are given by node refinement.

Joachim Kock (Mar 21 2021 at 22:35):

An operad has a dendroidal nerve, which is a presheaf on $\Omega$. There is a nerve theorem (due to Weber) characterising operads as those presheaves on $\Omega$ whose restriction to $\Omega_{\text{inert}}$ is a sheaf. That's the dendroidal Segal condition.

Joachim Kock (Mar 21 2021 at 22:40):

Because of the symmetries, this is already much more subtle than the multicategory case. For example, they prevent the free-operad monad from being a local right adjoint, and one can no longer get away with the easy version of Weber's theorem. Here is one problem. In the multicategory case, if $F$ is a collection, the free thing $\overline{F}$ is given on $C$ by $\overline{F}[C] = \sum_{T\in C\text{-tree}} F[T]$, and we detailed that the sum is over iso-classes of trees with $n$ leaves. In that case, passing to the set of isoclasses is harmless, because planar trees have no nontrivial automorphisms, which is to say that the set of isoclasses of $C$-trees is equivalent to the groupoid of $C$-trees. This is different in the nonplanar (symmetric) case: without the planar structure a tree generally has automorphisms, such as permuting some leaves, and even a $C$-tree can have automorphisms. A morphism of $C$-trees is required to fix the leaves, but if the tree has nullary nodes that are siblings, then permuting these small subtrees gives an automorphism that fixes all leaves!

The upshot is that there is some homotopically-notrivial quotienting going on. This is what prevents the free-operad monad from preserving pullbacks. This prevents it from being a local right adjoint.

Joachim Kock (Mar 21 2021 at 22:45):

The intuition is thus that the free operad on a collection $F$ adds new operations: where the operations of $F$ are $F$-corollas, the operations of $\overline{F}$ are $F$-trees. It is now clear that the notion of operad is purely combinatorial. Can we give it a more combinatorial description? One would like to describe all this in terms of polynomial functors and polynomial monads.

Joachim Kock (Mar 21 2021 at 22:47):

I don't want to be too detailed about polynomial functors here. Instead I refer to the lectures of David Spivak and Richard Garner in the Workshop on Polynomial Functors last week. The lectures are on YouTube.

I can also refer to all the other talks of the workshop, to give an idea of the breadth of applications and different aspects of the theory.

Joachim Kock (Mar 21 2021 at 22:50):

A functor from $Set/I$ to $Set/J$ is called polynomial if it is given by a diagram $I \stackrel{s}\leftarrow E \stackrel{p}\to B\stackrel{t}\to J$ by pullback along $s$, right adjoint to pullback along $p$, and left adjoint to pullback along $t$. The latter two constructions correspond to dependent products and dependent sums in type theory, respectively, and altogether a polynomial functor is thus a sum of products, whence the name. One crucial feature of the theory of polynomial functors is that many of their properties and constructions can be given combinatorially in terms of the representing diagram $I \leftarrow E \to B \to J$ (where the word representing can be formalised as in 'representable functors', but an indexed family of such). (A standard reference is my paper with Nicola Gambino [Polynomial functors and polynomial monads, Math. Proc. Cambridge Philos. Soc. 2013].)

Joachim Kock (Mar 21 2021 at 22:55):

Here is how one would like to represent an operad with a polynomial (with $I=J$): the set $I$ should be the set of colours (objects). The set $B$ should be the set of all operations, of all arities and all colours. Each operation has an output colour, and this is encoded in the maps $B \stackrel{t}\to I$. The input of an operation is not a single colour, but a symmetric list of colours. Since it is a symmetric list, we can index the slots by an arbitrary finite sets instead of a linearly ordered set (as would be required or multicategories). We encode this by taking $E$ to be the set of operations with a marked input slot. Then the map $p:E\to B$ just forgets the mark, and the fibre over a given operation is precisely its set of input slots. And the map $I \stackrel{s}{\leftarrow} E$ can now return the colour of the marked input slot. Now all the data is there, and it looks good and is indeed a very fruitful approach. However, not all collections are given in this way! It only gives those collections for which the symmetric-group actions are free. Equivalently, the stabiliser groups of the actions are trivial. These are called sigma-cofibrant collections, and sigma-cofibrant operads. In the theory of species, they are called flat species. That's still very interesting, and polynomial functors are very interesting, and have many applications. In particular, the sigma-cofibrant operads play a crucial role in the development of operad theory in topology.

(We already saw an example of an operad that is not sigma-cofibrant, namely the terminal operad $Comm$. Since it has only one operation in each arity, the symmetric group actions are trivial. That's as far as possible from being free.)

Joachim Kock (Mar 21 2021 at 22:59):

For polynomial endofunctors, the corresponding collection is sigma-cofibrant. For sigma-cofibrant operads, the corresponding polynomial endofunctor has a monad structure. In fact there is a one-to-one correspondence between monad structures on polynomial endofunctors and operad structures on their associated collections. So polynomial monads are essentially the same thing as sigma-cofibrant operads. The operad morphisms between sigma-cofibrant operads correspond to cartesian monad maps between polynomial monads. Finally it should be mentioned that the algebras for a sigma-cofibrant operad are the same thing as the (Eilenberg-Moore) algebras for the corresponding polynomial monad.

Joachim Kock (Mar 21 2021 at 23:10):

Next up are trees. So far we postponed the formal definition of trees. But Polynomial functors are a very nice language for talking about trees, and they give a very convenient formalism.

But since I am going to bed now, here is a cliff hanger:

A tree is a configuration of finite sets

$A \stackrel{s}\leftarrow M \stackrel{p}\to N \stackrel{t}\to A$

such that

(i)

(ii)

(iii)

Puzzle: figure out what the three conditions are.

Hint: think of the way a polynomial encodes operations.

Joachim Kock (Mar 24 2021 at 20:14):

Sorry for the delay, but now I am ready to continue. So far I talked about categories and linear orders, multicategories and plane trees, operads and trees. And then I started to talk about polynomial endofunctors.

One nice feature of polynomial endofunctors, is that it is an ideal language to talk about trees (of the form relevant here). In the discussion so far, it was left open what trees really are, with mention of the difficulty of using the standard definitions of tree from combinatorics and logic.

Joachim Kock (Mar 24 2021 at 20:17):

Here is the 'polynomial' definition, which works really well:

A tree is a diagram of finite sets

$A \stackrel{s}\leftarrow M \stackrel{p}\to N \stackrel{t}\to A$

for which

(i) $t$ is injective

(ii) $s$ is injective with singleton complement, denoted $1$. (That is, $A=M+1$.)

(iii) Under the walk-to-the-root function $\sigma: A \to A$ defined by $1 \mapsto 1$ and $\sigma(m) = s(p(m))$, you arrive at the root in finitely many steps: that is, $\forall x\in A \ \exists k\in \mathbb{N}: \sigma^k(x) = 1$.

The interpretation is that $A$ is the set of edges, $N$ is the set of nodes, and $M$ is the set of nodes with a marked input. The maps are easy to guess. Condition (i) says that an edge is outgoing of at most one node. Condition (ii) says that an edge is incoming to at most one node, and that all edges are incoming to some node except the root edge. Condition (iii) serves to force the incidences to give something simply-connected, and to ensure well-foundedness.

The definition, and the following discussion is from my paper [Polynomial functors and trees, IMRN 2011]

Joachim Kock (Mar 24 2021 at 20:20):

The point of the definition is that the diagram is the same shape as a polynomial endofunctor. There is a natural notion of morphism of trees which we call inert. They are morphisms between such diagrams such that the middle square is a pullback. Thus edges map to edges and nodes to nodes, the incidences are preserved, and the pullback conditions expresses that a node must map to a node of the same arity. One can deduce from the tree axioms that these maps are actually injective, so the maps are the 'full embeddings of trees'. This is the formal definition of $\Omega_{\text{inert}}$. (Note that this natural notion of map is also the one dictated by polynomial endofunctors, where they correspond to cartesian natural transformations (combined with basechange).

Joachim Kock (Mar 24 2021 at 20:24):

I mentioned that many combinatorial or logical definitions are not so convenient in this context. The main reason is that they don't naturally give the good notion of morphism. For example, if you encode a tree a a combinatorial tree with the open-ended edges represented as a special kind of node, then when you encode morphisms, you naturally end up with maps that preserve those special nodes, and for the sake of getting tree embeddings, in turn required to have the required colimits for expressing gluing. The polynomial formalism bypasses this by not encoding leaves and root as an explicit structure, and therefore the natural notion of maps does not tend to preserve them. Of course leaves and roots are still there, but as implied notions. It looks like this:

The trivial trees is $1001$. An edge in a tree $AMNA$ is a map from $1001$. Such an edge is the root if the right-most square of the inclusion map is a pullback. Such an edge is a leaf if the left-most square of the inclusion map is a pullback. (To see that this is correct is a small exercise.) Describing things will pullback conditions is a source of happiness in itself, but it is also very useful computationally.

Joachim Kock (Mar 24 2021 at 20:25):

In the previous discussions about trees, the properties of the category of trees were stated in a hand-wavy manner. With the precise definition, it is very easy to calculate the colimits required to glue trees, and say that every tree is a colimit of is elementary subtrees. In fact these colimits are calculated pointwise, meaning for $A$, $M$, and $N$ separately. It boils down to calculating some amalgamated sums of finite sets, and how they interact with pullbacks. It is really completely combinatorial and explicit.

Joachim Kock (Mar 24 2021 at 20:31):

Since this notion of tree is literally tailor-made to interact with polynomial functors, it is very easy to say what a $P$-tree is, for $P$ a polynomial endofunctor. Recall that a $P$-tree is supposed to be a tree in which edges are decorated by the colours of $P$, and nodes are decorated by operations of $P$, and with the compatibility condition saying that if operation $r$ decorates a node $x$ then the outgoing edge $px$ must be decorated by the outcolour of $r$, and finally the incoming edges must put in bijection with the input slots of $r$, with compatible colours. It is fun and useful to figure out how to formalise this. The answer in the polynomial formalism is very clean: let $P$ be the polynomial endofunctor given by $IEBI$, then a $P$-tree is a tree $AMNA$ with a cartesian map to $IEBI$. This takes care of all decorations and compatibilities and bijections at once! So the category of $P$-trees is just the comma category $\Omega_{\text{inert}}/P$, and all the important properties of $\Omega_{\text{inert}}$ (elementary trees, grafting, etc.) are the same again for $\Omega_{\text{inert}}/P$.

Joachim Kock (Mar 24 2021 at 20:33):

Every polynomial endofunctor $P$ defines a presheaf on elementary trees (or equivalently a sheaf on $\Omega_{\text{inert}}$), simply by $E \mapsto Hom(E,P)$, where the hom is now in the category of polynomial endofunctors. That's cool, and possible because trees really are polynomial endofunctors! But recall that only the sigma-cofibrant collections arise like this!

Joachim Kock (Mar 24 2021 at 20:43):

In any case, we can copy over all the constructions we did for collections and operads to the case of polynomial endofunctors and polynomial monads. And it works the same, and it produces the same Kleisli category $\Omega$ (the Moerdijk-Weiss category). (This is because if a collection is actually defined by a polynomial endofunctor, then the free operad on it is actually a polynomial monad.) Again there is a nerve theorem saying that a dendroidal set is the dendroidal nerve of a polynomial monad if and only if its restriction to $\Omega_{\text{inert}}$ is a sheaf AND sigma-cofibrant.

One could deduce this theorem from the general nerve theorem for operads, but the proof of the polynomial case is much more combinatorial: it is really about trees and $P$-trees, and since everything is explicitly encoded with configurations of finite sets, in the end all calculations take place in the category of finite sets, and amount to some compatibilities between pullbacks and certain colimits (expressing graftings).

Joachim Kock (Mar 24 2021 at 20:51):

One may think that it is a bit disappointing that the polynomial approach does not capture all operads. There is an intuition failing here :-( The reason the intuition fails is that the statement is true if sets are replaced by $\infty$-categories! Actually it is enough to go to $1$-groupoids. In the $\infty$-world, all collections are sigma-cofibrant, and all $\infty$-operads are polynomial monads! This is quite cool, because the theory of $\infty$-operads (as in Lurie's Higher algebra) is notoriously difficult, and full of technicalities, and you don't see many trees there :-( Thanks to this theorem (which is from the paper [Haugseng-Gepner-Kock, $\infty$-operads as analytic monads, IMRN 2021]) one can work with polynomial monads instead, and the theory is very combinatorial. It is another example of the viewpoint that the real thing is the $\infty$-category of $\infty$-groupoids. The category of set is just a suboptimal approximation with many deficiencies. (In particular the category of sets does not have optimal colimits. Examples of 'wrong' colimits in $Set$ are quotients of non-free group actions, which is what screws up the polynomial-monad operad correspondence.)

Joachim Kock (Mar 24 2021 at 20:58):

(That's a bit of a statement -- a bit provocative perhaps -- especially for category theorists raised in the tradition describing the category of sets as the most perfect of all categories, the coliit completion of the point, etc. I guess I owe some more substance to support this statement. Perhaps I should do that in another thread, and it is probably better I try to follow the current thread to the end first. It is still my intention to arrive at Petri nets -- it just takes longer than planned.)

Joachim Kock (Mar 24 2021 at 20:59):

The other nice thing about the polynomial viewpoint is that even over sets, the distinction between sigma-cofibrant and general operads goes away after slicing.

Joachim Kock (Mar 24 2021 at 20:59):

Sliced categories are the best thing since sliced bread!

Joachim Kock (Mar 24 2021 at 21:00):

For example, if we slice over $M$, the free-monoid monad (or the word monad), then we are talking operads cartesian over $M$ and $M$-trees. But these are precisely nonsymmetric operads, also called multicategories! And $M$-trees are precisely plane trees! So everything For any polynomial monad $T$ (or more generally cartesian monad) one can consider $T$-operads (also called $T$-multicategories). This is what Leinster's book is mostly about. By working relative to a fixed monad, the symmetry issues go away.

Joachim Kock (Mar 24 2021 at 21:23):

Maybe I should also mention that the inductive definition of trees comes in naturally when showing that the $P$-trees form the operations of the free monad on a polynomial endofunctor $P$.

This comes about as follows. One way to describe the free monad on an endofunctor (say over the category sets) is to figure out that its underlying endofunctor is given by sending a set $A$ to the initial algebra of the endofunctor $X \mapsto A+P(X)$. Now for any polynomial functor $P$ represented by a set map $E\to B$, the set $B$ can be reconstructed as $P(1)$. So if we are after the operations of the free monad on $P$, we need to compute the initial algebra for $1+P$. That is, we must solve the fixpoint equation $X=1+P(X)$. This is precisely how inductive data types work. In dependent type theory they are called $W$-types and in locally-cartesian-closed-categories semantics of dependent type theory they are precisely the initial algebras for polynomial functors. To prove that the $P$-trees are the operations of the free monad on $P$, it is enough to show that they solve the fixpoint equation, which is an explicit bijection given by grafting, hence about colimits in $\Omega_{\text{inert}}/P$. As already mentioned, this bijection can be verbalised by saying that a $P$-tree is either a trivial $P$-tree (and there is one for each colour), or it has a bottom node (an operation in $P$) and then for each input slot of that operation a $P$-tree whose root colour is the colour of that input slot. (Note the importance of solving $X=1+P(X)$ rather than just solving $X=P(X)$ as is more common in type theory: it is the $1$ in the equation that gives the trivial tree, in turn crucial for all arguments involving grafting.)

This connection is a good motivation for operad-theorist to learn a little bit of type theory (at least it was for me). I also find it cool that the inductive definition has a one-shot combinatorial description in terms of small configurations of finite sets. Let me stress again that the $W$-type description of $P$-trees does not seem to have any way of producing the correct notion of morphism, which drops out automatically from the combinatorics.

Joachim Kock (Mar 24 2021 at 21:26):

(I wrote that the $1$ in the fixpoint equation is responsible for the trivial trees, one of each colour. I see now that it looks a bit strange. The explanation is that if we work with colour set $I$, then the endofunctor is over the slice $Set/I$, and the $1$ in the equation denotes the terminal object $id:I \to I$, which has an element of each colour.)

Joachim Kock (Mar 24 2021 at 21:26):

Next up: from operads and trees, move on to properads and graphs. Now we are really getting close to Petri nets...

Ulrik Buchholtz (Mar 25 2021 at 19:33):

Thanks a lot for writing this out so nicely and leisurely, @Joachim Kock – I'm really enjoying it!
I have a question, which maybe you know the answer to: When working with simplicial objects, we can often get a lot of mileage from the direct subcategory $\Delta_{\mathrm{face}}$ of face maps. (E.g., we can recover $(\infty,1)$-categories as certain semisimplicial $\infty$-groupoids.)
Is something similar true for $\Omega_{\mathrm{face}}$ and $\infty$-operads? What is the dimension of a finite tree?

Joachim Kock (Mar 27 2021 at 17:38):

Thanks, Ulrik!

Ulrik Buchholtz said:

I have a question, which maybe you know the answer to: When working with simplicial objects, we can often get a lot of mileage from the direct subcategory $\Delta_{\mathrm{face}}$ of face maps. (E.g., we can recover $(\infty,1)$-categories as certain semisimplicial $\infty$-groupoids.)
Is something similar true for $\Omega_{\mathrm{face}}$ and $\infty$-operads? What is the dimension of a finite tree?

I don't know so much about this subcategory $\Omega_{\text{face}}$. In some respects its relationship with the whole $\Omega$ is similar to how the relationship between $\Delta_{\text{face}}$ and $\Delta$, but there are some new subtleties, due to symmetries: $\Omega_{\text{face}}$ is not a direct category. In particular, $\Omega$ is not a Reedy category. However, Berger and Moerdjik [On an extension of the notion of Reedy category, Math. Z. 2011] described the symmetries by showing that $\Omega$ is a crossed group on $\Omega_{\text{planar}}$ (which is a Reedy category), and developed Reedy theory for such things. A related issue is that the Moerdijk-Weiss model structure on dendroidal sets (presheaves on $\Omega$) is not a Cisinski model structure: not all its monos count as cofibrations!

(What dimension should mean depends on the motivation. I think the most natural notion of dimension is the number of nodes.)

Ulrik Buchholtz (Mar 27 2021 at 20:51):

Thanks, I'm familiar with the symmetry issue because it crops up for cubical sets as well. But $\Omega_{\mathrm{face}}$ is still a generalized direct category, right? (OT: the usual notion of a direct category is not invariant under equivalence of categories, but the notion of a generalized direct category is.)
Joachim Kock said:

(What dimension should mean depends on the motivation. I think the most natural notion of dimension is the number of nodes.)

I see; all the face maps add nodes, so this makes sense. The stump $\eta$ is then a kind of point, and the corolla with $n$ inputs is a 1-dimensional object with $n+1$ boundary points. I'll try to think about what the boundaries of the next low-dimensional trees look like.

Joachim Kock (Mar 28 2021 at 19:12):

Yes, $\Omega_{\text{face}}$ is a generalised directed category.

Joachim Kock (Mar 28 2021 at 19:24):

I wanted to move on to directed graphs and properads/props, but now I think I first want to talk about undirected graphs, since they are probably important in network theory. There is of course a huge literature on graph theory in combinatorics and computer science, with applications to all kind of sciences. Most of this theory deals with closed graphs, where each edge connects precisely two vertices. Here I want to allow open-ended edges: the end of an edge might lead to nowhere instead of leading to a vertex.

Joachim Kock (Mar 28 2021 at 19:28):

Since we are interested in compositional aspects, we want to glue smaller graphs together to form larger graphs, thinking for example of connecting devices along their interfaces. These interfaces can be modelled by specifying certain special nodes as ports, and then glue along those. In some situations, there is some notion of flow which makes the distinction of input and output ports natural. In other situations, there is no such natural distinction, but it can still be fruitful to impose the distinction, and designate some ports as outgoing and some as ingoing. In particular, this allows gluing to be interpreted as composition in a category. This is the case in the formalisms of decorated cospans and structured cospans, developed by Fong, Baez and Courser, and used by many people. Without being an expert on this, I think one reason for the sometimes-artificial-looking notions of in and out is that it gives some constraints on the gluings are allowed.

Joachim Kock (Mar 28 2021 at 19:36):

Here I want to take another approach. First of all, like in the discussions of trees, the idea is to model interfaces as open-ended edges, so that the act of connecting devices to each other can be modelled as gluing together graphs at the open-ended edges, in turn calculated as pushouts. Second, instead of having directed graphs, with the resulting notion of input and output, the gluings will be subjected to constraints given by involutive structure. This is a little bit difficult to motivate, but the idea is that when an input is connected to an output they cancel each other, in the sense that both ports vanish, so that nothing more can connect here. It is like a pairing. One can also think of a vector meeting a linear form -- a ket and a bra -- which when paired vanish to produce a scalar, which is something without interface. But a linear form is just a vector in another vector space (the linear dual), and the linear forms on that vector space are precisely the original vectors (assuming finite dimension). So instead of giving a global distinction of what is in and what is out, one can get away with just stipulating that two things are allowed to connect and vanish if they are dual to each other: instead of declaring that A is in and B is out, and therefore are allowed to connect and vanish, we just say that A and B are dual to each other, and therefore are allowed to connect and vanish.

So these ideas come from the category of finite-dimensional vector spaces, and more generally compact closed categories.

John Baez (Mar 28 2021 at 19:36):

Yes, I mainly separate interfaces into "inputs" and "outputs" to:

1. access the power of category theory, which then lets us treat open systems as morphisms,
2. give a really easy way to say which parts of an interface we're going to glue to which parts: you glue the output of one to the input of the other.

Then of course you can use the power of compact closed categories, etc., to change your mind about what's an input and what's an output.

John Baez (Mar 28 2021 at 19:38):

There are of course other ways to deal with these issues, e.g. operads.

Joachim Kock (Mar 28 2021 at 19:40):

OK, great. This is what I thought. Here I will continue with the involutive viewpoint as the primary viewpoint. This is a bit operadic, but modular-oepradic rather than classically operadic...

Joachim Kock (Mar 28 2021 at 19:45):

But now it is probably better just to jump into the definition:

A graph with open-ended edges is a diagram of finite sets

$i\circlearrowright A \stackrel{t}\leftarrow H \stackrel{p}\to V$

such that $t$ is injective and $i$ is a fixpoint-free involution. The latex is not perfect here: it is supposed to be an endomorphism $i: A \to A$.

The set $V$ is the set of vertices. The set $A$ is the set of arcs, which can be thought of as edges with a direction. The involution $i$ interchanges the directions. An edge is an orbit of this involution. The set $H$ is the set of half-edges, meaning pairs consisting of a vertex and an arc emanating from it. The maps $t$ and $p$ are the projections, returning the components of such pairs. The ports of such a graph are the arcs not in the image of $t$. (Note that this is similar to how the leaves of a trees $AMNA$ are the edges in the complement of $t$.) An inner edge is an orbit both of whose elements are in the image of $t$. Since $t$ is injective, this means that there are two half-edges in the preimage, and the fact that their images are interchanged by the involution is interpreted as these two half-edges being glued together to an edge. It is an edge between the vertices given by the images under $p$.

Joachim Kock (Mar 28 2021 at 19:46):

The definition is from [Joyal-Kock: Feynman graphs, and nerve theorem for compact symmetric multicategories (extended abstract), QPL 2009].

Joachim Kock (Mar 28 2021 at 19:50):

Here are some basic examples:

The trivial graph (a single edge without vertices) is given by

$i\circlearrowright 2 \stackrel{t}\leftarrow 0 \stackrel{p}\to 0$

Indeed, it has no vertices, and hence no half-edges. It has only one edge, the orbit consisting of the two arcs.

The corolla with $n$ ports is given by

$i\circlearrowright 2n \stackrel{t}\leftarrow n \stackrel{p}\to 1$

Indeed, there is only one vertex. Since the corolla has $n$ legs, there are $n$ half-edges. This set injects into the set $2n$ of all the arcs (twice as many as there are half-edges). Of these $2n$ arcs, $n$ of them are in the image of $t$, and the other $n$ are therefore ports, so the whole graph has $n$ ports.

The closed graph with one edge and two vertices is given by

$i\circlearrowright 2 \stackrel{t}\leftarrow 2 \stackrel{p}\to 2$

where the maps are invertible.

Indeed, there are two vertices (which is the right-most $2$), and each has a half-edge emanating (these form the set $2$ in the middle). There are no ports, (since it is a closed graph), so all the arcs (forming the left-most set $2$) are in the image of $t$. The involution interchanges the two half-edges, which therefore forms a single edge, which is the edge connecting the two vertices.

Joachim Kock (Mar 28 2021 at 19:55):

The definition does not come out of nowhere: it is an open version of the graph formalism introduced by Serre for use in group theory, in what is now called Bass-Serre theory, where a main activity is to glue together groups along subgroups. The reference for this is the book [Serre: Trees, Springer 1977]. It is a beautiful title :-) and also a beautiful book!

Serre's notion of graph concerns closed undirected graphs:

A Serre graph is a diagram

$i\circlearrowright A \stackrel{s, t}\rightrightarrows V$

for which $i$ is a fixpoint-free involution, interchanging $s$ and $t$.

In other words, the undirected graph is encoded as a directed graph in which all directed edges appear in pairs, one in each direction. It may seem strange why one would take this approach. It is actually a bit redundant: $s$ and $t$ determine each other uniquely. Equivalently, a Serre graph is a diagram $i\circlearrowright A \stackrel{t}\to V$ for which $i$ is a fixpoint-free involution.

Joachim Kock (Mar 28 2021 at 19:58):

Now the step from Serre's definition to the open-ended notion is clear: just allow $t$ to be a partial map instead of a everywhere-defined map. A partial map is just a span with the backward map injective, and we arrive at the open-ended definition. (I renamed the partial map $t$ to $p$ just to fit better with the polynomial formalism for trees!)

Joachim Kock (Mar 28 2021 at 20:01):

One nice thing about this definition of open-ended graph is that it leads naturally to a good notion of morphism: a morphism between two such diagrams consists of maps between the sets, with the condition that the rightmost square is a pullback. These are called etale maps. Just as for trees, the condition amounts to arity preservation at each vertex. The fact that the graphs are no longer simply-connected, as happened with trees, means that these maps are no longer necessarily injective. For example, the circle-shaped graph with one vertex admits a double cover of the circle-shaped graph with two vertices.

Joachim Kock (Mar 28 2021 at 20:09):

The etale condition is relevant whenever the vertices in a graph play some role of operation, as was the case for trees, where they were many-in/one-out operations. For graphs, this occurs quite a lot. For example, a transistor in an electrical network has tree ports -- base, collector and emittor. It makes sense that this 3-ness should be preserved under morphisms, so that if you want to describe a sub-circuit of an electrical circuit that includes a given transistor, it is reasonable to include all three ports of it (especially since we allow open-ended edges, so even if the sub-circuit does not involve any connections to base, collector or emittor, we still include it as an open-ended edge). Similarly, an relevant kind of vertex for Feynman graphs in quantum electrodynamics is the photon-electron-positron interaction. In a Feynman diagram of this kind, if we want to describe a sub-diagram containing such a vertex, we must include all three 'ports' -- for example, it does not make sense to have a subdiagram with a photon-electron vertex!

This digression was only to illustrate the naturalness of the etale condition in many situations.

Joachim Kock (Mar 28 2021 at 20:12):

As already done for trees https://categorytheory.zulipchat.com/#narrow/stream/235484-theory.3A-concurrency/topic/shapes.20and.20algebraic.20structures/near/231702586 I would like to stress again the importance of having the ports encoded not as an explicit structure, but as a derived notion. This is because in order to be able to express gluings as colimits, it is necessary that the subgraphs glued admit inclusion maps into the resulting big graph, and in particular, the ports they were glued along should no longer be ports of the big graph. In other words, morphisms should not necessarily send ports to ports. If ports are encoded as explicit structure, any naturally defined notion of morphism will tend to preserve ports :-(

Joachim Kock (Mar 28 2021 at 20:19):

To illustrate this problem, let me mention another notion of graph with open-ended edges, which is very common in the literature. It goes like this:

An graph with open-ended edges is a diagram of finite sets

$i\circlearrowright H \stackrel{p}\to V$

where $i$ is an involution. The idea is that $V$ is the set of vertices, and $H$ the set of half-edges. The involution expresses which half edges are glued together to produce an edge. The open-ended edges are encoded as fixpoints for the involution.

(Looks a lot like Serre's definition, but it is different!)

There are two 'problems' with this definition. One is that it does not allow for the trivial graph, which would be required to express gluings as pushouts over a trivial graphs. The second is that an edge being open-ended does not mean that it has been glued to itself! And fixpoints tend to he preserved by reasonable definitions of map, so the natural maps one can define will preserve ports :-( (The definition is OK if only invertible maps are involved.)

If you are curious about how one can work with this definition, the place to go is the paper [Borisov-Manin: Generalized operads and their inner cohomomorphisms, arXiv:math/0609748]. Their definition of morphism of graphs takes a whole page.

Joachim Kock (Mar 28 2021 at 20:26):

Back to work. I already talked about gluing graphs together. The category of etale maps allows this in the ideal way. Namely, if a trivial graph embeds into two graphs as ports, then the pushout exists -- provided that one arc of the trivial graph maps to the port in one graph and the other arc maps to a port in the other graph. In this case one can calculate the pushout pointwise and easily check the axioms (injectivity of the new $t$ and fixpoint-freeness of the new $i$).

Another important colimit is the coequaliser of two maps of a trivial graph mapping into two ports of a single graph. Again, the coequaliser exists under the above proviso. It is then calculated pointwise, and the resulting graph has the two ports connected up, forming a cycle in the graph.

Joachim Kock (Mar 28 2021 at 20:29):

Note that the individual ports of a graph do not have any sense of in or out, nor to they have any notion of who they are dual to. The involution is only present to control which gluings are allowed, and it does so reflecting our intuition quite accurately.

Joachim Kock (Mar 28 2021 at 20:38):

There is a notion of elementary graph (graphs without inner edges), and we define a graphical species to be a presheaf on the category of elementary graphs, or equivalently, a sheaf on the category of all graphs, for the etale topology. Readers of this thread can now nod and see it fit into the general patterns.

They are called graphical species because in the special case where they are required to take value 1 on the trivial graph, then they are just species in the usual sense of combinatorics, that is, encoding structures that can be put on finite sets, functorially in bijections. Without this requirement on the value on the trivial graph, there are compatibility conditions on what connects to what, and it is rather about what local structures can be put on graphs. For example, for each quantum field theory there is a graphical species specifying which local interactions are allowed (that is, the terms of the Lagrangian of the theory). Note that in a graphical species, the value on the trivial graph will be an involutive set, but not necessarily fixpoint free. The fixpoints will correpond to bosons, and the two-element orbits will correspond to fermions. But now I am digressing again...

Joachim Kock (Mar 28 2021 at 20:48):

Actually when we started to study these notions of graphs, we were not exactly motivated by Feynman diagrams, but rather wanted to understand what modular operads are, hoping to capture the notion in a Weber-like framework. Intuitively, they are algebraic structures that allow to compose any (connected) graph configuration of operations to a single operation. This is in analogy with all the previous cases in this thread. For example, an operad is an algebraic structure that allows to compose any rooted-tree configuration of operations to a single operation (rooted corolla).

There is a special case of modular operad, called cyclic operads, where only simply simply-connected graphs are involved. These are of course trees, but they are not rooted, so an alternative characterisation of cyclic operads is as ordinary operads where the distinction between inputs and output is abandonned.

Both cyclic and modular operads were introduced by Getzler and Kapranov, in connection with homological algebra, algebraic geometry and mathematical physics. They only studied these notions in the single-coloured case. We wanted to consider the coloured case, and this is what seemed to require involutive structure. Since we didn't really arrive at the same notion of modular operad as Getzler and Kapranov, we called it something else: compact symmetric multicategories.

Joachim Kock (Mar 28 2021 at 20:51):

The idea was that there should be a monad defined on the category of graphical species, given by upgrading from elementary graphs to general graphs, and that its algebras should be called compact symmetric multicategories and be a kind of modular operads. We claimed this in the QPL extended abstract, and promised to write up the details later. That never happened, though...

Joachim Kock (Mar 28 2021 at 20:55):

At this point, the story becomes trickier to tell. On one hand I want to advocate this nice definition of graph with open-ended edges, and on the other hand I now have to tell you that the main theorem about them has a serious bug: in fact the monad is not well defined :-(

Joachim Kock (Mar 28 2021 at 20:57):

Roughly the reason is that in a circle-shaped graph with only one vertex, one should be able to substitute a trivial graph into the vertex, but the result would then be a circle-shaped graph without any vertices. This graph is not an object in the category! This is a special case we had overlooked.

Joachim Kock (Mar 28 2021 at 21:01):

It turns out it spoils the definition of the monad :-( This was discovered gradually by several people, including Michael Batanin, Clemens Berger, Philip Hackney, Marcy Robertson, Donald Yau, and Sophie Raynor. Batanin-Berger and Hackney-Robertson-Yau invented fancier notions of graphs to circumvent the problem and include the vertex-less circle (in ad hoc ways). Raynor wrote her PhD thesis about the problem [Raynor: Compact symmetric multicategories and the problem of loops, PhD thesis, Aberdeen 2017], and found a way to adjust the above definition to get a well-defined monad and hence well-defined algebras.

Altogether it is a very subtle issue...

Joachim Kock (Mar 28 2021 at 21:07):

(The vertex-less loop is a very strange beast. In quantum field theory, it does not seem to play any role. Since it has no ports it is what is called a vacuum graph, with nothing to observe, and since it has no vertices, there are no interactions either. So it's like a non-interacting, non-observable particle. I wonder if it has any meaning. I would be happy if anynoe with more background in physics could comment on this. Michael Batanin convinced me that it is actually an important element mathematically: in some situations the vertex-less loop can be regarded as the trace of the identity morphism, which is called the dimension, in analogy with vector spaces.)

Joachim Kock (Mar 28 2021 at 21:20):

It is quite annoying and embarrassing to have a paper out whose main theorem involves an object that does not exist, even if it is only an extended abstract of a conference talk.

Maybe there are a couple of lessons to be learnt: one is that it is a bit dangerous to release half-baked work. I take the responsibility in this case: after giving the talk at QPL, I thought it would be nice to record it in an extended abstract for the proceedings, thinking that it might well take a long time before the final paper would come out. On the other hand, even though the main theorem of the extended abstract was wrong, it actually contained good ideas and it led to further developments.

Joachim Kock (Mar 28 2021 at 21:24):

The analogous theorem for cyclic operads is OK, because in this case there are only simply-connected graphs, and therefore no danger of vertex-less circle graphs. The proof steps were also good enough to tackle the case of directed graphs and properads, which I spelled out in detail some years later in [Graphs, hypergraphs, and properads, Collect. Math. 2016]. Finally, the graph formalism was also good enough to give a conceptual account of the Borisov-Manin category of graphs. Their difficult morphisms turn out to be certain cospans in (a slightly modified version of) the Joyal-Kock category [Cospan construction of the graph category of Borisov and Manin, Publ. Mat. 2018].

Joachim Kock (Mar 28 2021 at 21:26):

Even if the graphs were not good enough for the straightforward 'nerve theorem for compact symmetric multicategories', I still think the original definition has some merit. If anyone thinks it can be useful in some network context (or elsewhere), I will be happy to explain more details.

Joachim Kock (Mar 28 2021 at 21:29):

Coming up next: directed graphs and properads/props. Now we are getting really close to Petri nets.

John Baez (Mar 28 2021 at 21:54):

Joachim Kock said:

The vertex-less loop is a very strange beast. In quantum field theory, it does not seem to play any role. Since it has no ports it is what is called a vacuum graph, with nothing to observe, and since it has no vertices, there are no interactions either. So it's like a non-interacting, non-observable particle.

Vacuum bubbles are important in quantum field theory, but these are graphs with vertices and edges, just not any "open" edges, or "ports", or whatever you like to call edges that end at the "outside world". (Physicists call them "external lines").

John Baez (Mar 28 2021 at 21:56):

Vacuum bubbles cannot be directly observed, but they're important in a certain way in the formalism of quantum field theory.

Joachim Kock (Mar 28 2021 at 22:49):

Thanks, John.
I guess the more specific question I have is if there can be vacuum bubbles without vertices?

John Baez (Mar 28 2021 at 23:03):

I said a vacuum bubble has vertices. So I was trying to answer your question with a "no".

Vacuum bubbles are important in quantum field theory, but these are graphs with vertices and edges...

John Baez (Mar 28 2021 at 23:04):

To be more precise, there is no room in the formalism for a vacuum bubble with an empty set of vertices and a nonempty set of edges.

John Baez (Mar 28 2021 at 23:07):

(Technically, adding a constant to your Lagrangian would give a vacuum bubble with no vertices and no edges. Nobody calls this a vacuum bubble, but that's just like how nobody used to call 0 a number. This is just the empty graph - much less exciting than your graph with no vertices and yet still an edge.)

Joachim Kock (Mar 28 2021 at 23:50):

Thanks again, it was clear enough what you said. I only misunderstood it by my lack of confidence. I tend to get notions from physics wrong the first many times I try.
I am happy for Feynman diagrams that they don't have vertex-less loops.

Joachim Kock (Mar 29 2021 at 00:21):

In the discussion above, I meant to include some explanation of how involutive structure helps control gluings and maps, but I forgot. Here is an attempt: with rooted trees we saw that the only way to map to a tree is by embeddings. For example, the (rooted) corolla with one input and one output admits only maps from the trivial tree (node-less edge) and from itself via the identity map. The point is that the directedness prevents us from running up and down in zigzag in the tree. Now consider the same corolla, but consider it as an undirected graph. Maybe now we can run up and down in zigzag, since there is no longer any directedness? Try for example to run a seven-vertex linear graph into it: map the first node onto the unique node, and then the adjacent edge to the adjacent half edge, and then make a sharp turn and run back, so that the next vertex lands on the unique vertex again, but from the other side, and continue like that seven times. That would seem like a horrible seven-fold cover (ramified over the half-edges but etale over the vertices, as required). It's a thought experiment. Thanks to the involutive structure of edges, it cannot actually happen in the formalism: because the maps must preserve the involution, if a map enters an edge from one 'end' it has to leave at the other 'end'. It is not possible to leave a vertex in the direction of a half-edge and then make a sharp turn and run back to the same vertex. (I think this verbal explanation is not very convincing, but it is true nevertheless, as you can easily work out for yourself.) Similarly, it follows from the axioms that an etale map to a simply-connected graph must be injective. This is an important property. It implies for example that the free cyclic operad on a (non-rooted) tree has only finitely many operations, namely the set of subtrees.

Jade Master (Mar 31 2021 at 03:23):

I'm not sure if this is the same thing...but I've noticed something similar in the operational semantics of open graphs, Petri nets, and about a dozen other things in the cospan formalism. Thinking about graphs for example, suppose that G: X -> Y and H: Y -> Z are open graphs thought of as cospans D(X) -> G <- D(Y) and D(Y) -> H <- D(Z) where D gives the discrete graph on a set. Then they are composed via pushout along D(Y). You can take their free categories F(G) and F(H), and these free categories represent the operational semantics of G and H. What I mean by that is that the morphisms of these two categories are paths in the graphs that they came from...so roughly they contain everything you can do with each graph.

Jade Master (Mar 31 2021 at 03:27):

You can compose these two operational semantics in two ways, either by forming $G+_{D(Y)} H$ and then taking the free category $F(G+_{D(Y)} H)$ or by taking the free categories individually and then joining them together as $F(G)+_{F(D(Y))} F(H)$ and these two things should be the same because F is a left adjoint. However be careful, because the second pushout is in the category of categories and this is not the same as the pushout in Grph, where you glue your vertices and edges together along their shared boundary.

Jade Master (Mar 31 2021 at 03:29):

The trouble is that $F(G +_{D(Y)} H)$ contains paths which start in G, then go to H, then go back to G, then go back to H, and so on as many times as you like.

Jade Master (Mar 31 2021 at 03:30):

In other words, this free category contains morphisms which zig-zag back and forth many times before arriving at their destination.

Jade Master (Mar 31 2021 at 03:33):

This is why the pushout in Cat requires a second transitive closure, so $F(G) +_{D(Y)} F(H)$ should read something like: first close G and H under paths, then glue them together as if they were graphs, then take the free category of the result, then quotient out all the extra morphisms.

Jade Master (Mar 31 2021 at 03:34):

(and if you want to give this description some more formality, I am pretty sure it follows from Kelly's transfinite construction of free algebras)

Jade Master (Mar 31 2021 at 03:38):

Anyway, I'm thinking that this zig-zag behavior might be the same phenomenon as with these pushouts. Morally the operational semantics of a network G should be described as all morphisms from paths into G...as you were saying, without some sort of directionality on the boundaries these paths can zig zag back and forth between different components as much as they like.

Jade Master (Mar 31 2021 at 03:42):

There are things called functional Petri nets, introduced by Zaitsev (e.g. here). They are basically Petri nets with in and out boundaries such that tokens can only flow in on the in boundaries and out on the out boundaries.

Jade Master (Mar 31 2021 at 03:44):

You can generalize functional Petri nets to lots of other types of networks and it turns out that functional open networks have operational semantics which compose without needing the second transitive closure...because paths simply cannot zig zag back and forth between components.

Jade Master (Mar 31 2021 at 03:45):

I could go on about this for a while but I'll stop here :sweat_smile:

John Baez (Mar 31 2021 at 21:02):

All this stuff is very beautiful. People who don't understand this stuff but might want to should check out this paper:

• Jade Master, The open algebraic path problem.

It explains everything very clearly, I think.

What sort of generalization of functional Petri nets are you thinking about?

Jade Master (Mar 31 2021 at 23:19):

Thank you John, that paper doesn't contain everything I claim but my thesis will. The generalization of functional Petri net I'm thinking of doesn't require much imagination I think... but the idea is

• An open Petri net $P: X \to Y$ is functional if there are no transitions of P which output an element of X and no transitions of P which take an element of Y as input.
• $Q$-nets still have transitions in the same way so you don't need to change anything to generalize to them.
• An open graph $G: X \to Y$ is functional if there are no edges of G going into an element of X and no edges of G going out of an element of Y.
• An open weighted graph $H : X \to Y$ is functional if the weight from any other node to an element of X is 0 and the weight from an element of Y to any other node is 0.

Jade Master (Mar 31 2021 at 23:20):

So yeah basically an open network is functional if the inputs are all sources and the outputs are all sinks.