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.

February 28, 2018

Hypergraph Categories of Cospans

Posted by John Baez

guest post by Jonathan Lorand and Fabrizio Genovese

In the Applied Category Theory Seminar, we most recently read Brendan Fong’s article on decorated cospans. This construction is part of a larger framework, developed in Brendan Fong’s PhD thesis, for studying interconnected, open, network-style systems. A paradigmatic example: systems composed of electric circuits having input and output terminals, allowing for composition of smaller circuits into larger. An aim of Brendan’s framework is to give, for any such kind of system, a unified categorical way to describe both the formal, symbolic language of such systems (their “syntax”) as well as the behavior of the systems that these formal symbols represent (the “semantics”). For circuits: syntax is formal rules for combining circuit diagram nomenclature; semantics is a (mathematical) description of how real-life circuits behave in the presence of voltages, currents, etc.. Decorated cospans are a tool ideal for “syntax”; decorated corelations are designed to handle “semantics” and are flexible enough to model any so-called hypergraph category. We’ll focus on the former, and hint at the latter.

John Baez has written several nice blog posts already about decorated cospans, corelations, and his work with Brendan Fong on passive linear networks of circuits; we hope the present post navigates a course which complements these. We set the scene with hypergraph categories, then discuss (decorated) cospans, and give a very brief introduction to corelations.

We’d like to thank Brendan for his many helpful comments, his technical support, and diagram sharing. Also thanks to Brendan, Nina and the whole “Adjoint team” for a great seminar experience so far.

Hypergraph categories

The name “hypergraph category” is rather new, introduced in [F1] and [K]. The concept itself is apparently older, going back at least to Carboni and Walters.

First of all, why “hypergraph”? There are several notions which fall under the name “hypergraph”, and we do not follow conventions too closely here. For us, a hypergraph is simply a kind of graph which has different types of nodes and edges, with edges allowed to be possibly “open” in the sense that they are attached only on one end to some node. Composition of such graphs to build new graphs is possible by connecting open edges together (though we only allow edges of the same type to connect). The following picture illustrates such a composition, with different types of edges indicated by different types of lines.

A hypergraph category is a categorical version of hypergraphs, where we think of edges as objects and nodes as morphisms. Here is a concise definition, we’ll then do some unpacking: a hypergraph category is a symmetric monoidal category such that each object is equipped with the structure of a special commutative Frobenius monoid, and such that these structures satisfy a certain compatibility with the monoidal product.

We’ll use the string diagram language for symmetric monoidal categories, and introduce four new symbols corresponding to (co)monoid maps. A special commutative Frobenius monoid structure (SCFM structure) on an object XX of a symmetric monoidal category (C,)(C, \otimes) is given by maps

(called the multiplication, unit, comultiplication, and counit), satisfying the axioms of a commutative monoid

and cocommutative comonoid

as well as the “Frobenius” and “special” axioms

This set of axioms is not minimal; in particular, if a monoid and comonoid structure satisfies the Frobenius law, then commutativity and cocommutativity imply each other. Thus the term “commutative” Frobenius monoid entails “bicommutativity”.

Suppose an object XX in (C,)(C, \otimes) carries a SCFM structure. A coherence result know as the “spider theorem” tells us, roughly, that any morphism f:X mX nf: X^m \rightarrow X^n described by a connected string diagram, and defined only using operations and canonical maps coming from (C,)(C,\otimes) and the maps (μ,η,δ,ϵ)( \mu, \eta, \delta, \epsilon), can be depicted simply as a “spider”: a diagram with one node, mm input legs and nn output legs.

This result, though, is only about maps between monoidal powers of a single object XX. The interaction of SCFM structures on different objects of a hypergraph category is provided by the following compatibility axioms: in a hypergraph category we require

In this way one obtains a kind of category whose calculus of string diagrams reflects the initial intuition given by hypergraphs. More details, in particular on diagrammatics, can be found in [BGKSZ] and [K].

As indicated above, hypergraphs are a natural structure for describing open, network-like systems. The word “open” means that one has a notion of input, output and composition/interaction. Here is a summary of this “network intuition” in terms of hypergraph categories

One wishes also to compare/translate between different hypergraph categories. A hypergraph functor (C,)(C,)(C, \otimes) \rightarrow (C', \boxtimes) between hypergraph categories is a strong symmetric monoidal functor (F,φ)(F, \varphi) such that, for each object XX of CC, the SCFM structure (FX,μ FX,η FX,δ FX,ϵ FX)(F X, \mu_{F X}, \eta_{F X} ,\delta_{F X} , \epsilon_{F X}) on FXF X must coincide with the one induced by FF:

(FX,Fμ Xφ X,X,Fη Xφ I,φ X,X 1Fδ X,φ I 1Fϵ X) (F X, F \mu_{X} \circ \varphi_{X,X}, F \eta_{X} \circ \varphi_I, \varphi_{X,X}^{-1} \circ F \delta_{X} , \varphi_I^{-1} \circ F\epsilon_{X})

An equivalence of hypergraph categories is an equivalence of symmetric monoidal categories which is built of hypergraph functors.

An important remark about hypergraph categories is that the SCFM maps (μ X,η X,δ X,ϵ X)(\mu_X, \eta_X, \delta_X, \epsilon_X) on each object XX in CC are not required to be natural in XX. Morphisms in CC need not interact in a coherent way with the SCFM structures. In particular, a given symmetric monoidal category may admit two hypergraph structures which are hypergraph inequivalent.

Another remark is that hypergraph categories are automatically compact closed, with every object self-dual: the maps

and

(think: cup and cap) satisfy

as well as the vertically reflected equations (think: snake!). The first equality uses the Frobenius law, the second the (co)unital laws.

Cospan Categories

Cospans lead to hypergraph categories following a familiar construction. One starts with a category CC having finite colimits, viewing it as a symmetric monoidal category (C,+)(C, +) with the coproduct as monoidal product. From this we define a category whose objects are the objects of CC, and whose morphisms XYX \rightarrow Y are cospans in CC

considered up to a notion of isomorphism. The source and target of the cospan are the “feet”, while NN is the “apex”. Cospans are isomorphic for us if they have the same feet and if there exists an isomorphism between their apexes which makes the evident triangles commute. The maps ii and oo (the “legs” of the cospan) are labeled to hint at the interpretation that we are thinking of XX as representing inputs, and YY as representing outputs.

Composition of cospans Xi XNo YYX \overset{i_X}{\rightarrow} N \overset{o_Y}{\leftarrow} Y and Yi YMo ZZY \overset{i_Y}{\rightarrow} M \overset{o_Z}{\leftarrow} Z is given by taking a pushout over the shared foot

Considering only isomorphism classes of cospans makes this composition well-defined and associative, and one checks that this builds us a category. It’s called Cospan(C)Cospan(C).

Cospan(C)Cospan(C) has a symmetric monoidal structure induced from CC, and comes with a canonical hypergraph structure. To see roughly how this works, note that we have an “identity on objects” embedding CCospan(C)C \hookrightarrow Cospan(C) defined by sending a morphism f:XYf: X \rightarrow Y in CC to the cospan XfY1 YYX \overset{f}{\rightarrow} Y \overset{1_Y}{\leftarrow} Y. This gives us a copy of CC inside Cospan(C)Cospan(C) and induces a monoidal structure on Cospan(C)Cospan(C).

The directional symmetry in the definition of a cospan means that cospans actually come in pairs

Call such cospans opposites of one another. Note that, alongside the above embedding, there is an analogous embedding C opCospan(C)C^{op} \hookrightarrow Cospan(C), sending f op:YXf^{op}: Y \rightarrow X to Y1 YYfXY \overset{1_Y}{\rightarrow} Y\overset{f}{\leftarrow} X.

For each object XX in (C,+)(C,+) we have the copairing [1 X,1 X]:X+XX[1_X, 1_X]: X + X \rightarrow X and a unique map !:X! : \emptyset \rightarrow X from our initial object \emptyset in (C,+)(C,+). The images of these morphisms under CCospan(C)C \hookrightarrow Cospan(C) give us a multiplication map μ\mu and a unit map η\eta for a commutative monoid structure on XX. By defining comultiplication δ\delta and counit ϵ\epsilon via the cospans which are opposite to μ\mu and η\eta, respectively, one obtains a SCFM on each object of Cospan(C)Cospan(C), with compatibility making Cospan(C)Cospan(C) a hypergraph category.

As a simple example to play with, consider the category FinSetFinSet whose objects are the sets \emptyset, {1}\{1\}, {1,2}\{1, 2 \}, {1,2,3}\{1,2,3\}, … and whose morphisms are functions between these sets. This category has finite colimits, with initial object \emptyset and coproduct defined by

{1,2,...,n}+{1,2,...,m}={1,2,..,n+m};\{1,2,...,n\} + \{1,2,...,m\} = \{1,2,..,n+m \};

these make (FinSet,+)(FinSet,+) a symmetric strict monoidal category. We think of {1}\{1\} as the generator of the objects; all other objects may be built from this one using the coproduct (thinking of \emptyset as the zero-th monoidal power of {1}\{1\}). Graphically we depict {1}\{1\} as a black dot, and any object {1,2,...,n}\{1,2,...,n\} as a cloud of nn dots (since our monoidal product is strictly commutative, the order of how we juxtapose our dots doesn’t matter, so we just use “clouds”).

Suppose we are composing cospans Xi XNo YYX \overset{i_X}{\rightarrow} N \overset{o_Y}{\leftarrow} Y and Yi YMo ZZY \overset{i_Y}{\rightarrow} M \overset{o_Z}{\leftarrow} Z in FinSetFinSet. The pushout over the shared foot YY implements the merging of the two apexes according to the “instructions” given by the output function o Yo_Y of the first cospan and the input function i Yi_Y of the second, as illustrated below in red

In this image, the bottom “cloud” is YY, on the left is NN, on the right is MM, and above is N+ YMN +_Y M, while XX and ZZ, and the maps from them, are not depicted.

Decorated cospans

In the setting of electrical circuits, one may view circuit diagrams as a set of nodes NN which is “decorated” by the other symbols of the circuit diagram. For given NN, this information may be encoded mathematically by specifying, for example, a set of edges E with target and source maps s,t:ENs,t : E \rightarrow N, as well as other information, such as an assignment of resistances to edges by specifying a function r:E(0,)r : E \rightarrow (0, \infty).

Thinking of the set of nodes NN as the apex of a cospan in FinSetFinSet, the images in NN of the feet XX and YY correspond to choices of input and output terminals, respectively, and the legs of the cospan allow further flexibility in connecting, for example, multiple inputs of one circuit to an output terminal of another, as illustrated above. John Baez’s blog post has nice examples of circuits being composed.

Decorated cospans are designed to capture this intuitive notion of composition of network diagrams. This must be done in such a way that the cospans and their decorations compose together in the desired manner.

Formally, Brendan achieves this using a lax monoidal functor (F,φ):(C,+)(Set,×)(F, \varphi) : (C, +) \rightarrow (Set, \times) to encode the decorations on the apexes of cospans in Cospan(C)Cospan(C). (One may actually use any monoidal category (D,)(D, \otimes) in place of (Set,×)(Set, \times)). Given such a functor FF, he constructs a category FCospan(C)F Cospan(C) of “FF-decorated cospans in CC” where the objects are the objects of CC, and morphisms are represented by pairs consisting of a cospan XiNoYX \overset{i}{\rightarrow} N \overset{o}{\leftarrow} Y in CC and an element sFNs \in F N of the image of the apex NN under FF. This element is the decoration of the apex. On the nose, morphisms in FCospan(C)F Cospan(C) are isomorphism classes of such pairs; two such pairs are isomorphic if their constituting cospans are isomorphic via an isomorphism n:NNn : N \rightarrow N' between their apexes which is also compatible with the decorations: (Fn)(s)=s(F n)(s) = s'.

Composition of decorated cospans works, on representatives of morphisms in FCospan(C)F Cospan(C), by composing the constituent cospans and composing the decorations ss and tt by sending (s,t)FN×FM(s, t) \in F N \times F M to a decoration on the composed apex N+ YMN +_Y M via the map

F[j N,j M]:FN×FMF(N+ YM) F[j_N,j_M]: F N \times FM \rightarrow F(N+_Y M)

(recall that j Nj_N and j Mj_M denote the pushout maps involved in composing our cospans). A key point is that we can use the copairing [j N,j M]:N+MN+ YM[j_N, j_M] : N + M \rightarrow N +_Y M to implement the “merging” of the decorations on NN and MM.

Under the assumptions that the “decoration category” (D,)(D, \otimes), and FF, are braided (we keep these assumptions now), the category FCospan(C)F Cospan(C) inherits a monoidal and hypergraph structure from Cospan(C)Cospan(C). Here is a summary:

In [F1] (see Theorem 4.1) a method is given for constructing hypergraph functors between decorated cospan categories FCospan(C)F Cospan(C) and GCospan(C)G Cospan(C'), starting from the data of a natural transformation which relates CC and FF to CC' and GG.

In [F2], decorated cospans are generalized to decorated corelations, and in this setting a theorem is proved which is analogous to the one mentioned above. This gives, in particular, a way of constructing functors from hypergraph categories of decorated cospans (think: syntax) to hypergraph categories of corelations (think: semantics).

Although we won’t have the space to explain decorated corelations properly, we’ll conclude our post by introducing the basic idea of corelations and indicating their potential for describing the “semantics”, or behavior, of open, network-like systems.

Corelations

The corelation approach to describing the behavior of open systems is linked to the idea of “black-boxing”. Suppose one has two different circuit diagrams - described in a decorated cospan category as above - which have the same set of input and output terminals XX and YY, and suppose we build these circuits. The real-life circuits will impose certain relations on the values of the voltages and currents which may be simultaneously measured at all of the terminals. Not every configuration of possible values is realizable because circuits obey certain laws, such as Ohm’s law relating currents, voltages and resistances.

Note that two different circuits might impose the same relations between their terminals. With respect to an agreed upon mode of measurement, the relations imposed by a circuit on its terminals may be called the (external) “behavior” of a circuit. We’ll say that two circuits behave the same way if they are indistinguishable by making measurements at their terminals. In other words, if each circuit were covered by an opaque black box, with only the terminals exposed, we would not know which circuit is which.

Decorated corelations are designed to capture exactly the information about the “black-box behavior” of open, network-style systems. Brendan gives at least two reasons why one might wish to keep track only of this “behavioral” information, rather than all of the internal workings of components of open systems. One reason is conceptual clarity: the focus is kept on the behaviorally relevant information. A second reason is computational: when smaller components are composed into larger, the amount of syntactical information may increase explosively, while semantically relevant information may be more stable. As a simplified illustration: in the below composition of circuit diagrams, the parts of the resulting larger circuit which have no paths to any terminals are not relevant for the behavior of the circuit.

To give a sketch of how corelations work, let’s use the category FinSet mentioned above. Suppose we have cospans in FinSet Xi XNo YYX \overset{i_X}{\rightarrow} N \overset{o_Y}{\leftarrow} Y and Yi YMo ZZY \overset{i_Y}{\rightarrow} M \overset{o_Z}{\leftarrow} Z, ready to be composed as so

Their composite

is the cospan Xj No YN+ YMj Mi YZX \overset{j_N o_Y}{\rightarrow} N +_Y M \overset{j_M i_Y}{\leftarrow} Z. The union of the images of the legs of this cospan is precisely the image of the copairing [j No Y,j Mi Y]:X+ZN+ YM[j_N o_Y, j_M i_Y]: X + Z \longrightarrow N+_Y M. Points outside of this image may be irrelevant, we may wish to “discard” them. A way of implementing “discarding” is to focus our attention on cospans XiNoYX \overset{i}{\rightarrow} N \overset{o}{\leftarrow} Y for which [i,o]:X+YN[i,o]: X + Y \rightarrow N is surjective. These are called corelations. To compose corelations Xi XNo YYX \overset{i_X}{\rightarrow} N \overset{o_Y}{\leftarrow} Y and Yi YMo ZZY \overset{i_Y}{\rightarrow} M \overset{o_Z}{\leftarrow} Z, we compose them as cospans to obtain Xj Ni NN+ YMj Mo MZX \overset{j_N i_N}{\rightarrow} N +_Y M \overset{j_M o_M}{\leftarrow} Z and then restrict the map [j No Y,j Mi Y][j_N o_Y, j_M i_Y] to its “surjective part”, to obtain again a corelation.

Factorization systems (,)(\mathcal{E}, \mathcal{M}) in a category give a way to make this idea precise and general; in [F2] factorization systems are used define a general notion of corelation which is modeled on the above example. Then, given a category CC with finite colimits and a factorization system (,)(\mathcal{E}, \mathcal{M}) with suitable properties, one can build a hypergraph category (Corel (,)(C),+)(Corel_{(\mathcal{E}, \mathcal{M})}(C), +) where objects are those of CC and morphisms are so-called (,)(\mathcal{E}, \mathcal{M})-corelations. As in the case of cospans, corelations can be decorated, leading to decorated corelation categories. The scope of this construction turns out to be quite general: in [F3] it is proved that any hypergraph category is hypergraph equivalent to some decorated corelation category.

Further reading

Posted at February 28, 2018 4:19 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3023

4 Comments & 0 Trackbacks

Re: Hypergraph Categories of Cospans

I see no pictures when I view this page with experimental Firefox 60 (Nightly 60.0a1 (2018-02-21) (32-bit)), but it works fine in Chrome. The problem seems to be that the page is secure (“https”) while the images are not (“http”). The console log has lots of error messages like

Nightly is upgrading an insecure display request

‘http://math.ucr.edu/home/baez/mathematical/ACT2018/lorand/hypergraph_comp.png’

to use ‘https’

This seems like an overly aggressive security fix that will break lots of old pages but the security concerns could probably be complied with.

Posted by: RodMcGuire on March 1, 2018 5:11 PM | Permalink | Reply to this

Re: Hypergraph Categories of Cospans

I see lots of pictures when I view this page with non-experimental Firefox. I suppose it’s to be expected that not everything will work smoothly with experimental software.

Posted by: Tom Leinster on March 1, 2018 7:18 PM | Permalink | Reply to this

Re: Hypergraph Categories of Cospans

As a general comment, there must be many hundreds of http images that are linked to from Cafe posts. If browsers start objecting to the fact that this site is https but some images linked to are http, that would be a pain.

Posted by: Tom Leinster on March 1, 2018 7:50 PM | Permalink | Reply to this

Re: Hypergraph Categories of Cospans

There are also other https websites besides the nn-Café that link to http images! Like, millions. So I believe this problem will be solved.

Posted by: John Baez on March 1, 2018 7:57 PM | Permalink | Reply to this

Post a New Comment