Graphs in Poly
polynomial functors
Abstract
It’s really amazing to me that comonoids in Poly are categories, and I think it would be cool if more people understood that on a gut level. But explaining it takes more time than people are sometimes prepared to give. So today, I want to explain a much simpler case—one which gives a lot of the intuition—namely that of graphs.
1 Intro
It’s really amazing to me that comonoids in \mathbf{Poly} are categories, and I think it would be cool if more people understood that on a gut level. But explaining it takes more time than people are sometimes prepared to give. So today, I want to explain a much simpler case—one which gives a lot of the intuition—namely that of graphs.
Polynomial functors are closed under composition. I notate the composition of polynomials using the \mathbin{\triangleleft} symbol for a variety of reasons (one is a normative claim: non-symmetric monoidal structures should have non-symmetric symbols!). So for example if p=\mathcal{y}^2+1 and q=\mathcal{y}^3+2\mathcal{y}, then their composite is: p\mathbin{\triangleleft}q =q^2+1 =(\mathcal{y}^3+2\mathcal{y})^2+1 \cong\mathcal{y}^6+4\mathcal{y}^4+4\mathcal{y}^2+1.
A comonoid in \mathbf{Poly} consists of a polynomial c equipped with two maps \epsilon\colon c\to\mathcal{y}\qquad\text{and}\qquad\delta\colon c\to c\mathbin{\triangleleft}c satisfying some conditions; the amazing claim is that these are exactly categories. The idea is that if c=\sum_{v\in c(1)}\mathcal{y}^{c[v]} then the object-set of the corresponding category is c(1) and the set of morphisms emanating from v\in c(1) is c[v]. You get the identities from \epsilon and the codomains and composition from \delta. But I don’t want to explain that here. I want to give you the basic intuition for it by explaining a simpler case: graphs.
2 Graphs in Poly
Graphs are like categories, but they don’t have identities and they don’t have composition. They’re just tuples (V,A,s,t) where V,A\in\mathbf{Set} and s,t\colon A\to V. The idea is that V is the set of vertices, A is the set of arrows, and s,t take each arrow to its source/target vertex.
We can encode a graph as a pair (g,\kappa) where g\in\mathbf{Poly} \qquad\text{and}\qquad \kappa\colon g(1)\to g\mathbin{\triangleleft}g(1) subject to a single commutative diagram:
You’re presumably asking: “how in the world is this a graph??”
Suppose you start with a graph in standard form, G=(V,A,s,t); what is the associated (g,\kappa)? First, for any v\in V, define A_v\coloneqq s^{-1}(v) to be the set of arrows emanating from v. Then define the emanation polynomial for G as: g\coloneqq\sum_{v\in V}\mathcal{y}^{A_v} This polynomial g encodes all of the vertices as summands, i.e. g(1)\cong V. The polynomial g also somehow encodes the set A and the source map s, in that every arrow is in A_v for exactly one v\in V. For example, you could check that A can be obtained as A\cong\dot{g}(1), the derivative of g at 1, if that sounds like an interesting exercise to you. We’re still missing the target map, but we’ll see that can be encoded in the function \kappa. To understand it, first let’s unpack g\mathbin{\triangleleft}g(1). It is the set \begin{aligned} g\mathbin{\triangleleft}g(1)&\cong \sum_{v\in V}\prod_{a\in A_v}\sum_{v'\in V}\prod_{a'\in A_{v'}}1\\&\cong \sum_{v\in V}\prod_{a\in A_v}\sum_{v'\in V}1\\&\cong \sum_{v\in V}\mathbf{Set}(A_v, V). \end{aligned} In other words, an element of g\mathbin{\triangleleft}g(1) is a vertex v, and for every emanating arrow a\in A_v an element of V. Thus \kappa\colon g(1)\to g\mathbin{\triangleleft}g(1) is just a function V\to \sum_{v\in V}\mathbf{Set}(A_v, V).
At this point we’ve got a graph G, we’ve defined the emanation polynomial, which tells us about V, A, and s, and we’re looking to encode t inside \kappa somehow. So given v\in V, define \kappa(v)\coloneqq (v, a\mapsto t(a)), where t is the target map from above (restricted to A_v\subseteq A). Thus we’ve used \kappa to encode the target map. The condition from (\star) forces the first coordinate of \kappa(v) to be v, as it was; in other words, it forces the only data in \kappa to be the target map.
3 Maps and monoidal products of graphs
The maps of graphs you get this way are not graph homomorphisms. Maybe they should be called graph co-homomorphisms. A seasoned category theorist would already know how they want to define a map between graphs as defined above: given (g,\kappa) and (g',\kappa'), a map between them should be a polynomial map \varphi\colon g\to g' such that the diagram \begin{CD} g(1) @>>> g\mathbin{\triangleleft}g(1) \\@V{\varphi(1)}VV @VV{\varphi\mathbin{\triangleleft}\varphi(1)}V \\g'(1) @>>> g'\mathbin{\triangleleft}g'(1) \end{CD} commutes. If g,g' correspond to graphs G,G' with standard notation, this turns out to be equivalent to the following:
- a function \varphi_1\colon V\to V' on vertices;
- for every vertex v and arrow a'\in A'_{\varphi_1(v)} emanating from its image, an arrow a\coloneqq\varphi^\sharp(v,a')\in A_v emanating from v; and
- a verification that the target of a is sent to the target of a'.
The slogan is: a graph co-homomorphism goes forwards on vertices and backwards on emanating arrows, respecting targets.
The usual coproduct of graphs is given by sums, (g+g',\kappa+\kappa'), where we have \begin{aligned} (g+g')(1)& \cong g(1)+g'(1)\\&\xrightarrow{\kappa+\kappa'} (g\mathbin{\triangleleft}g)(1)+(g'\mathbin{\triangleleft}g')(1)\\&\xrightarrow{\text{inc}} g\mathbin{\triangleleft}(g+g')(1)+g'\mathbin{\triangleleft}(g+g')(1)\\&= (g+g')\mathbin{\triangleleft}(g+g')(1). \end{aligned} The usual product of graphs is given by Dirichlet product (g\otimes g',\kappa\otimes\kappa'), where we have \begin{aligned} (g\otimes g')(1)&\cong (g(1))\otimes (g'(1))\\&\xrightarrow{\kappa\otimes\kappa'} (g\mathbin{\triangleleft}g(1))\otimes (g'\mathbin{\triangleleft}g'(1))\\&\xrightarrow{\text{duoidal}} (g\otimes g')\mathbin{\triangleleft}(g\otimes g')(1). \end{aligned}
I know I haven’t explained all this, e.g. duoidal stuff. I’m just putting it here in case someone knows that stuff or wants to think about sums or products of graphs and is willing to read about duoidality elsewhere.
4 Free categories
One thing we like to do with graphs is to consider their free categories. We can do that here, but to explain it we’ll need to go faster (assume more of the reader) and use a bit of notation, namely the “coclosure” for \mathbf{Poly}. This coclosure says that a morphism \kappa\colon g(1)\to g\mathbin{\triangleleft}g(1) into a composite can be identified with a morphism of the form: \begin{bmatrix}{\vphantom{f_f^f}g(1)} \\ {\vphantom{f_f^f}g(1)} \end{bmatrix} \to g. Since \left[\begin{smallmatrix}{\vphantom{f}p}\\{\vphantom{f}p}\end{smallmatrix}\right] is a comonoid (i.e. a category) for any p, we can factor the above map through the cofree comonoid on g, i.e. as \begin{bmatrix}{\vphantom{f_f^f}g(1)} \\ {\vphantom{f_f^f}g(1)} \end{bmatrix} \nrightarrow\mathfrak{c}_g. Then, factoring this comonoid map too, this time using the vertical-cartesian factorization system \begin{bmatrix}{\vphantom{f_f^f}g(1)} \\ {\vphantom{f_f^f}g(1)} \end{bmatrix} \nrightarrow f_g\nrightarrow\mathfrak{c}_g the comonoid f_g in the middle will be the free category on g.
5 Conclusion
I know that graphs are so simple that one may never want to think about them in terms of polynomial functors, since the latter seems so much more complicated. To me, however, it’s nice to just know that so much of what I want to do in category theory has an expression in \mathbf{Poly}. Sometimes we get a funny sort of map, e.g. here the maps between \mathbf{Poly}-encoded graphs are more naturally co-homomorphisms. But my bet is that these sorts of maps are more common than people think, and we just don’t see them because we don’t know to look.
Hopefully, this post also gives some readers a bit of intuition for why comonoids in \mathbf{Poly} are categories. If you want an exercise, see if you can encode reflexive graphs in \mathbf{Poly}. (Hint: use \epsilon together with some new condition.)