I have a couple of questions motivated by the following exercise from Emily Riehl's Category Theory In Context,
Exercise 3.5.iii. Prove that the category $\operatorname{DirGraph}$ of directed graphs is complete and cocomplete and explain how to construct its limits and colimits.
For this the author suggests using a previous proposition,
Proposition 3.3.9. If $A$ is small, then the forgetful functor $C^A \to C^{\operatorname{ob} A}$ strictly creates all limits and colimits that exist in $C$. These limits are defined objectwise, meaning that for each $a \in A$, the evaluation functor $ev_a : C^A \to C$ preserves all limits and colimits existing in $C$.
I am aware that it usually is bad practice to include more than one question in the same post, but these are all related and probably too simple to be asked individually.
I have failed to see how this result proves the aforementioned excersice, so I have instead tried to show that $\operatorname{DirGraph}$ has (co) products and (co) equalizers, since implies (co) completeness (as shown in Theorem 3.4.12 in the book).
So far I have managed to define products, coproducts, and equalizers as
- $\prod_i G_i$ with $(x_i)(y_i) \in E \iff x_iy_i \in E_i$ for all $i$ and the projections,
-
$\coprod_iG_i$ with the usual inclusions, and
-
$ E \hookrightarrow G \rightrightarrows^f_g H $ with $E = \{v \in V(G) : f(v) = g(v) \}$.
but I can't seem to define the coequalizer properly, nor 'extend' the construction in $\operatorname{Set}$ which, if I recall correctly, is defined as the quotient which identifies each image of $f$ with its corresponding of $g$. Hence I have the following questions:
- how can we prove this as intended by the author? That is, do you have any hints on how to connect the proposition with this particular exercise?
- what is the 'canonical' description of coequalizers in this category?
- and finally, trying to define the latter I have found out that I do not have much intuition for epimorphisms of graphs (where as monomorphisms I can think of 'ways of embedding a graph onto a subgraph of the codomain'). How can I think of these, in terms of intuition?
Thanks in advance!
Best Answer
The category of directed multigraphs is a closely related category that has a very compact and relevant description. Let $A$ be the category consisting of two objects and two parallel arrows between them (and identities), then the category of directed multigraphs is $\mathbf{Set}^A$ (or often $\mathbf{Set}^{A^{op}}$ so we get the category of presheaves on $A$, but that doesn't really make much of a difference in this case). By the proposition, we immediately have that the category of directed multigraphs is complete and cocomplete (because $\mathbf{Set}$ is). Your category of directed graphs is a full subcategory of this category where the images of the two arrows happen to be jointly monic.
We can make a directed multigraph into a directed graph via identifying all edges between those any pair of vertices. Basically, we quotient the set of edges by an equivalence relation that identifies two edges whenever they share source and target. You can verify that this is a left adjoint to the inclusion. This makes the category of directed graphs a reflective subcategory of the category of directed multigraphs. Call the left adjoint, the reflector, $R$ and the inclusion $I$, so $R\dashv I$. We have the counit $\varepsilon : R\circ I \cong Id$. We can then calculate colimits of directed graphs by including them into multigraphs, taking the colimit there, and reflecting the colimit back. That is, $R\mathsf{Colim}(I\circ D)\cong\mathsf{Colim}(R\circ I\circ D)\cong\mathsf{Colim}D$. The upshot is that colimits are calculated by calculating the corresponding colimits of the edge and vertex sets. This may produce vertices with multiple arrows between them, i.e. a directed multigraph, which we then quotient to get a directed graph.
Before doing anything about limits we have from the fact that $I$ is a right adjoint that it preserves limits. Since $I$'s action is basically trivial, any limits that exist in the category of directed graphs have to look the same as the limits of those graphs as multigraphs which are computed pointwise. The question, in this case, becomes only whether those limits exist. The least "sophisticated" approach is to simply check that the pointwise limits actually work. [Note, the next sentence and the next paragraph go way not what Riehl was expecting.] Another approach is to recognize that the category of directed graphs is a category of models for an essentially algebraic theory on $\mathbf{Set}$, and those are always complete and have limits computed pointwise.
However, there's a different approach that sticks to this reflective subcategory view. Define $T=I\circ R$. We readily have $T\circ T \cong T$ and that $T$ is a monad, so $T$ is an idempotent monad. (It turns out reflective subcategories and idempotent monads are basically the same thing.) Let's consider an object of the Eilenberg-Moore category for this monad. In this case, an object of that category is a directed multigraph $G$ and a multigraph homomorphism $\varphi:TG\to G$ that satisfies some laws , in particular, that $\varphi\circ\eta_G=id_G$ where $\eta:Id\to I\circ R = T$ is the unit of the adjunction. But think about this for a second. This law can only be satisfied if $G$ is already a directed graph, i.e. if $\eta_G:G\cong TG$, the law then forces $\varphi=\eta_G^{-1}$. (Note, $\eta_G$ is not invertible for arbitrary multigraphs $G$.) The upshot is that the category of Eilenberg-Moore algebras for $T$ is equivalent to the category of directed graphs. This situation is what it means for $I$ to be monadic. General results about categories of Eilenberg-Moore algebras imply that it has all limits that the underlying category does. It's actually fairly easy to prove this, so I recommend doing so.
I recommend the nLab page I referenced before on reflective subcategories for several abstract nonsense results that imply the above or other useful statements. Very little of the above depended on the fact that we were talking about directed graphs.
Riehl was probably expecting something along the lines of the first two and a half paragraphs above, though perhaps not in quite so general terms, particularly since adjunctions haven't been introduced yet. (They are in Chapter 4, but in the meantime you could use properties of representable functors.) This covers everything except whether the category of directed graphs has limits. If it does, you know what they are supposed to look like, so you can just verify that the suggested limits actually work. This basically amounts to showing that the limit of edge sets that have at most one edge between any pair of vertices has itself at most one edge between any pair of vertices. This is particularly easy to see if you think of a directed multigraph as having a family of edge sets indexed by pairs of vertices – very much like hom-sets for categories. The remaining stuff about essentially algebraic theories and monadicity is very unlikely what Riehl was expecting as those are covered in Chapter 5.
To answer your last question, an epimorphism of directed graphs just means you can lay the source graph over the target graph so that the source graph completely covers the target, possibly collapsing some edges and identifying some vertices.