Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

July 8, 2017

A Bicategory of Decorated Cospans

Posted by John Baez

My students are trying to piece together general theory of networks, inspired by many examples. A good general theory should clarify and unify these examples. What some people call network theory, I’d just call ‘applied graph invariant theory’: they come up with a way to calculate numbers from graphs, they calculate these numbers for graphs that show up in nature, and then they try to draw conclusions about this. That’s fine as far as it goes, but there’s a lot more to network theory!

There are many kinds of networks. You can usually create big networks of a given kind by sticking together smaller networks of this kind. The networks usually do something, and the behavior of the whole is usually determined by the behavior of the parts and how the parts are stuck together.

So, we should think of networks of a given kind as morphisms in a category, or more generally elements of an algebra of some operad, and define a map sending each such network to its behavior. Then we can study this map mathematically!

All these insights (and many more) are made precise in Fong’s theory of ‘decorated cospans’:

Kenny Courser is starting to look at the next thing: how one network can turn into another. For example, a network might change over time, or we might want to simplify a complicated network somehow. If a network is morphism, a process where one network turns into another could be a ‘2-morphism’: that is, a morphism between morphisms. Just as categories have objects and morphisms, bicategories have objects, morphisms and 2-morphisms.

So, Kenny is looking at bicategories. As a first step, Kenny took Brendan’s setup and souped it up to define ‘decorated cospan bicategories’:

In this paper, he showed that these bicategories are often ‘symmetric monoidal’. This means that you can not only stick networks together end to end, you can also set them side by side or cross one over the other—and similarly for processes that turn one network into another! A symmetric monoidal bicategory is a somewhat fearsome structure, so Kenny used some clever machinery developed by Mike Shulman to get the job done:

I would love to talk about the details, but they’re a bit technical so I think I’d better talk about something more basic. Namely: what’s a decorated cospan category and what’s a decorated cospan bicategory?

First: what’s a decorated cospan? A cospan in some category CC is a diagram like this:

where the objects and morphisms are all in C.C. For example, if CC is the category of sets, we’ve got two sets XX and YY mapped to a set Γ.\Gamma.

In a ‘decorated’ cospan, the object Γ\Gamma is equipped or, as we like to say, ‘decorated’ with extra structure. For example:

Here the set Γ\Gamma consists of 3 points—but it’s decorated with a graph whose edges are labelled by numbers! You could use this to describe an electrical circuit made of resistors. The set XX would then be the set of ‘input terminals’, and YY the set of ‘output terminals’.

In this example, and indeed in many others, there’s no serious difference between inputs and outputs. We could reflect the picture, switching the roles of XX and Y,Y, and the inputs would become outputs and vice versa. One reason for distinguishing them is that we can then attach the outputs of one circuit to the inputs of another and build a larger circuit. If we think of our circuit as a morphism from the input set XX to the output set Y,Y, this process of attaching circuits to form larger ones can be seen as composing morphisms in a category.

In other words, if we get the math set up right, we can compose a decorated cospan from XX to YY and a decorated cospan from YY to ZZ and get a decorated cospan from XX to Z.Z. So with luck, we get a category with objects of CC as objects, and decorated cospans between these guys as morphisms!

For example, we can compose this:

and this:

to get this:

What did I mean by saying ‘with luck’? Well, there’s not really any luck involved, but we need some assumptions for all this to work. Before we even get to the decorations, we need to be able to compose cospans. We can do this whenever our cospans live in a category with pushouts. In category theory, a pushout is how we glue two things together.

So, suppose our category CC has pushouts. IF we then have two cospans in C,C, one from XX to YY and one from YY to Z:Z:

we can take a pushout:

and get a cospan from XX to Z:Z:

All this is fine and dandy, but there’s a slight catch: the pushout is only defined up to isomorphism, so we can’t expect this process of composing cospans to be associative: it will only be associative up to isomorphism.

What does that mean? What’s an isomorphism of cospans?

I’m glad you asked. A map of cospans is a diagram like this:

where the two triangles commmute. You can see two cospans in this picture; the morphism ff provides the map from one to the other. If ff is an isomorphism, then this is an isomorphism of cospans.

To get around this problem, we can work with a category where the morphisms aren’t cospans, but isomorphism classes of cospans. That’s what Brendan did, and it’s fine for many purposes.

But back around 1972, when Bénabou was first inventing bicategories, he noticed that you could also create a bicategory with

  • objects of CC as objects,
  • spans in CC as morphisms, and
  • maps of spans in CC as 2-morphisms.

Bicategories are perfectly happy for composition of 1-morphisms to be associative only up to isomorphism, so this solves the problem in a somewhat nicer way. (Taking equivalence classes of things when you don’t absolutely need to is regarded with some disdain in category theory, because it often means you’re throwing out information—and when you throw out information, you often regret it later.)

So, if you’re interested in decorated cospan categories, and you’re willing to work with bicategories, you should consider thinking about decorated cospan bicategories. And now, thanks to Kenny Courser’s work, you can!

He showed how the decorations work in the bicategorical approach: for example, he proved that whenever CC has finite colimits and

F:(C,+)(Set,×) F : (C,+) \to (\mathrm{Set}, \times)

is a lax symmetric monoidal functor, you get a symmetric monoidal bicategory where a morphism is a cospan in C:C:

with the object Γ\Gamma decorated by an element of F(Γ).F(\Gamma).

Proving this took some virtuosic work in category theory. The key turns out to be this glorious diagram:

For the explanation, check out Proposition 4.5 in his paper.

I’ll talk more about applications of cospan bicategories when I blog about some other papers Kenny Courser and Daniel Cicala are writing.

Posted at July 8, 2017 11:59 PM UTC

TrackBack URL for this Entry:

14 Comments & 0 Trackbacks

Re: A Bicategory of Decorated Cospans

Does “insertion” of networks also fit into this picture somehow? By that I mean that if I have a network NN and a node nNn\in N, and another network MM such that the connections of nn match up with the inputs/outputs of MM, then I can make a new network in which nn is removed and all of MM is “inserted” in its place.

I don’t know what the appropriate generality is in which to define that, but recently I happened to be thinking about something similar for a different purpose, and it seemed convenient to think about it in terms of composition in a bicategory of “decorated relations” in which a network is a morphism from its “input/output type” to its “node types”. I wonder whether anyone has written down something like that before?

Posted by: Mike Shulman on July 9, 2017 12:29 PM | Permalink | Reply to this

Re: A Bicategory of Decorated Cospans

Wouldn’t that just be inverse coarse-graining? The inverse of simplifying a network?

At least that’s what I’d assume “simplifying a network” to usually mean.

Posted by: kram1032 on July 10, 2017 2:06 PM | Permalink | Reply to this

Re: A Bicategory of Decorated Cospans

Maybe; I’m not familiar with the phrase “simplifying a network”. (John said something about simplifying networks in his post, but I assumed it was just an informal usage.) In any case, that seems to just rephrase the question.

Posted by: Mike Shulman on July 10, 2017 9:56 PM | Permalink | Reply to this

Re: A Bicategory of Decorated Cospans

Hi Mike!

I don’t know if your insertion of networks idea would fit into this particular framework, but it might be able to be captured using double pushout graph rewriting. I’m not an expert on this, but the idea is that we start with a monic span (meaning that both legs are monic)

ABMA \leftarrow B \rightarrow M

and a morphism BDB \to D. Here, AA is the node nn together with all the nodes adjacent to nn as well as edges between those nodes and the node nn. We take BB to be just the collection of nodes adjacent to nn and MM is the network that we want to insert in place of nn. DD is the original network NN with the node nn (and obviously any edges incident with it) removed, so DD can be thought of as the “frame” in which we are removing nn and replacing it with MM. All the morphisms are just inclusions. This gives us two adjacent cospans with a shared leg. If we take the pushout of the cospan

ABDA \leftarrow B \rightarrow D

we get the original network NN that we started with and if we take the pushout of the other cospan

DBMD \leftarrow B \rightarrow M

we get a new network that has the network MM in place of the node nn.

The span ABMA \leftarrow B \rightarrow M above is an example of a graph rewrite, which says “replace AA by MM if BB is present”, so your condition of the inputs and outputs of MM matching up with those of nn would be captured by this span.

If CC is a topos so that we may push and pull as we please, Daniel Cicala has shown in Spans of cospans that monic spans like the one above can be seen as 2-morphisms in a bicategory MonicSp(Csp(C))MonicSp(Csp(C)), whose objects are that of CC, morphisms are cospans in CC and 2-morphisms are (isomorphism classes of) monic spans of cospans in CC. Then he and I showed that this bicategory is symmetric monoidal (compact closed, actually) in Bicategories of spans and cospans using a result of some guy named Shulman :)

Posted by: Kenny Courser on July 11, 2017 3:34 AM | Permalink | Reply to this

Re: A Bicategory of Decorated Cospans

Ah, wonderful! Thanks so much, I think double pushout graph rewriting is exactly what I wanted. I remember now reading your paper “spans of cospans” and not really understanding section 4, and likewise not really understanding the double-pushout rewriting section of the Lack-Sobocinski paper about adhesive categories. But (as seems to happen so often) now that I have an application of my own in mind and have come halfway towards reinventing the concept myself, I can appreciate it much better.

What I really want is a nice abstract notion of the associativity and unitality of this sort of rewriting, and it seems natural to try to incorporate it into a bicategory. (This is not really germane to this post, but I hope you won’t mind my asking you questions about it here.) I think that in my situation I want to “compose” such rewrites using “dependency relations” as described in Definition 5.6 of Lack-Sobocinski, but in the special case where the morphism tt is an isomorphism. This suggests to me that maybe I should be looking at a bicategory constructed from some adhesive category C\mathbf{C} whose objects are those of C\mathbf{C} and whose morphisms from XX to YY are diagrams like

XlKrRsY X \xleftarrow{l} K \xrightarrow{r} R \xleftarrow{s} Y

in which l,rl,r are monic and perhaps some other condition holds. They would be composed like in Definition 5.8 of “concurrent production” in Lack-Sobocinski, with the “some other condition” ensuring that the pushout-complement E 2E_2' exists. Do you know whether anything like this exists in the literature? Lack-Sobocinski don’t mention any sort of associativity for the “concurrent production” construction.

Posted by: Mike Shulman on July 14, 2017 11:22 PM | Permalink | Reply to this

Re: A Bicategory of Decorated Cospans

Hi Mike.

How are you composing morphisms of the form LKRY L \leftarrow K \rightarrow R \leftarrow Y with the dependency relations? I don’t immediately see how one would stick another such morphism on the end of that. I can see more clearly, however, composing morphisms of the form XLKRYX \rightarrow L \leftarrow K \rightarrow R \leftarrow Y. Then given a morphism like YLKRZY \rightarrow L' \leftarrow K' \rightarrow R' \leftarrow Z, and assuming enough colimits, we can pushout over RYLR \leftarrow Y \rightarrow L' which is a piece of the composition. But as you mentioned, we still need to ensure the pushout complement exists. Sorry, but I’m not aware of any sufficient conditions for this.

However here is what crossed my mind; hopefully it is helpful for your needs. For the sake of concreteness, I’ll say I’m working in the category of directed graphs. Consider those morphisms I mentioned above and take all of the maps to be monic. Then a morphism from XX to YY is a double pushout graph rewrite from a graph LL to a graph RR, where XLX \subseteq L and YRY \subseteq R. But this means that rewrites from LL to RR are scattered throughout as many hom-sets as there are subgraphs of LL and RR. Anyway, assuming we have successfully composed two of these morphisms (i.e. the pushout complements are there) then what we get is a rewrite from LL to R+ YLR +_Y L' followed by another from R+ YLR +_Y L' to RR' . So we can capture this composite rewrite with the spans LKR+ YLL \leftarrow K \rightarrow R +_Y L' and R+ YLKRR +_Y L' \leftarrow K' \rightarrow R'. Of course, this composition would be associative up to isomorphism. In a nutshell, maybe you can capture what you want with merely spans. The downside to this is that you might be getting far too many spans than you want.

I have a preprint where I run through an example of a bicategory whose 1-cells are from the zx-calculus and the 2-cells are their rewrites. There are rewrite rules, using just spans, that replace a single node with a more complex system. It might be closely enough related to what you’re doing to be of help. The construction is based on my ‘spans of cospans’ paper Kenny mentioned above.

Posted by: Daniel Cicala on July 17, 2017 7:26 AM | Permalink | Reply to this

Re: A Bicategory of Decorated Cospans

To compose XlKrRsYX \xleftarrow{l} K \xrightarrow{r} R \xleftarrow{s} Y with YlKrRsZY \xleftarrow{l'} K' \xrightarrow{r'} R' \xleftarrow{s'} Z, write the following diagram:

X Y Z K R (1) K R (3) (2) K E R \array{ X &&&&&& Y &&&&&& Z \\ &\nwarrow &&&& \swarrow && \nwarrow &&&& \swarrow\\ && K & \to & R && (1) && K' & \to & R' \\ &&& \nwarrow & (3) & \nwarrow && \swarrow & (2) & \swarrow\\ &&&& K'' & \to & E & \to & R'' }

in which (1) is a pushout complement, (2) is a pushout, and (3) is a pullback.

I don’t follow your description using only spans. In particular, where does the pushout complement happen?

Posted by: Mike Shulman on July 18, 2017 11:40 PM | Permalink | Reply to this

Re: A Bicategory of Decorated Cospans

In my description, I was essentially casting a wide net. Instead of finding a condition that would restrict to a situation in which the pushout complements would hold, I gave (I believe) a situation in which all pushout complements have already been taken (which is why they didn’t show up explicitly). However, many spans that don’t satisfy the dependence relation would also be composable here which, perhaps, is undesirable for your needs.

I’m having a bit of trouble understanding how your composition relates to definition 26 (concurrent production) of Lack-Sobocinski. I tried fitting ll, rr, ll', and rr' into the diagram from definition 26 assuming they are monic and that tt is an isomorphism. After manipulating the diagram, I couldn’t figure out how to bring it to your diagram, though I came close.

That being said, I do have an idea for a condition to get you the pushout complement in the case of taking Graph to be your base category. It may be a bit unwieldy, but it’s a start. My thinking is, because you’re assuming that ll' is monic, (1) in your diagram will be a pushout and pullback with the map ERE \rightarrow R being monic also. This is because, in adhesive categories, pushouts preserve monics and pushouts over monics are also pullbacks (Lemma 4 + Defn 5, Axiom 3 in Lack-Sobo). It follows, if you also assume s:YRs : Y \rightarrow R to be monic, that KEK' \rightarrow E in (1) will also be monic. Therefore, necessarily KERK' \subseteq E \subseteq R. Now, I haven’t thoroughly checked this, but a seemingly sufficient condition for EE to exist is that any edge in Rs(Y)R - s(Y) must have its source and target live in sl(K)s \circ l'(K') or in Rs(Y)R - s(Y). I’m guessing that one can make this precise and extend it to any topos, all of which are adhesive, by playing with the subobject classifier.

About references on the subject, the beginning of the line of double pushout graph rewriting was this paper by Ehrig, Pfender, and Schneider. Also there is a nice survey by Corradini, et. al..

Posted by: Daniel Cicala on July 21, 2017 7:27 PM | Permalink | Reply to this

Re: A Bicategory of Decorated Cospans

In the case I’m interested in, which I don’t want to take the time to describe in detail right now, the maps are naturally of a restricted sort for which I believe all the pushout complements exist, although ss is not necessarily monic. So I’m not worried about whether or not the pushout complements exist, but just wondering whether the question of associativity has been studied assuming the complements exist. (In particular, I’ve written out the associativity diagrams for my composition, and I think they agree because of the commutative cube associated to a van Kampen pushout.)

The diagram at the top of p19 of Lack-Sobocinski has two objects labeled DD', and I don’t see a reason why they would be the same. If we call them D middleD'_{middle} and D rightD'_{right}, then to translate from my diagram to theirs, set X=L 1=CX=L_1=C', K=K 1=E 1K=K_1=E'_1, R=R 1=D middleR=R_1=D'_{middle}, Y=X=L 2Y=X=L_2, K=K 2K'=K_2, R=R 2R'=R_2, E=E 2E=E_2', R=D rightR''=D'_{right}, and K=PK''=P'.

Posted by: Mike Shulman on July 22, 2017 12:09 AM | Permalink | Reply to this

Re: A Bicategory of Decorated Cospans

The diagram at the top of p19 of Lack-Sobocinski has two objects labeled D′ D’, and I don’t see a reason why they would be the same.

I think you’re correct. That seems like a typo.

So I’m not worried about whether or not the pushout complements exist, but just wondering whether the question of associativity has been studied assuming the complements exist.

The closest thing to a study of associativity that I’ve come across is Section 5 of this survey. The authors construct `models of computation’. These are categories with graphs as objects and various types of derivations – that is, rewrite rules – as morphisms. They start with a category of all derivations from some generating set then place various restrictions and relations on the morphisms to obtain other models of computation. I’m not certain that what you need is in there, but it may be worth looking at.

Posted by: Daniel Cicala on July 24, 2017 8:35 PM | Permalink | Reply to this

Re: A Bicategory of Decorated Cospans

Thanks! At first glance it looks like their “derivations” are formal composites of “direct” derivations, which means that associativity comes for free and the operation of actually composing rewrite rules isn’t addressed. But I’ll look more closely in case it’s encoded in some of their more complicated definitions.

Posted by: Mike Shulman on July 26, 2017 3:53 PM | Permalink | Reply to this

Re: A Bicategory of Decorated Cospans

Here is an excellent book on network theory.

Network Science by Albert-Laszlo Barbasi Cambridge University Press (2016)

Posted by: Jeffery Winkler on July 24, 2017 4:44 PM | Permalink | Reply to this

Re: A Bicategory of Decorated Cospans


Posted by: John Baez on August 1, 2017 3:21 PM | Permalink | Reply to this

Re: A Bicategory of Decorated Cospans

You can see the book online here.

Posted by: Jeffery Winkler on July 25, 2017 3:30 PM | Permalink | Reply to this

Post a New Comment