# Pullbacks and pushouts in the category of digraphs?

By definition the category of digraphs is:

• Objects are endomorphisms of the category $\mathbf{Rel}$ (that is sets equipped with a binary relation on that set).
• Morphisms from an object $\mu$ to an object $\nu$ are discretely continuous functions, that is functions $f$ such that $f\circ\mu\subseteq\nu\circ f$. (This formula is equivalent to $\mu\subseteq f^{-1}\circ\nu\circ f$ and to $f\circ\mu\circ f^{-1}\subseteq\nu$.)
• Composition is the composition of functions.

I have proved that in categories like this all small products and all small coproducts are defined.

To prove that this category is (co)complete it remains to show existence of pullbacks and pushouts.

-

Let $\mathbf{Dig}$ be your category of digraphs, and let $\mathbf{Gph}$ denote the category of `multigraphs', i.e., presheaves over the usual category $[0] \rightrightarrows [1]$ (please ask if that's unclear). $\mathbf{Dig}$ is a full, reflective subcategory of $\mathbf{Gph}$, spanning simple graphs, i.e., all $G$ such that $G(x,y)$ is $\emptyset$ or $1$ for all $x,y$. The left adjoint, intuitively, keeps vertices unchanged and identifies all parallel edges.

Thus, for any diagram in $\mathbf{Dig}$, view it as a diagram in $\mathbf{Gph}$, compute its colimit there (that's a presheaf cat!), and then reflect it back to $\mathbf{Dig}$ via the left adjoint. This yields a colimit for the original diagram, because left adjoints preserve colimits.

For limits, it's easy to check that arbitrary products of digraphs, computed in $\mathbf{Gph}$, are again digraphs. The same holds for equalisers, which shows that not only limits do exist in $\mathbf{Dig}$, but also that they are computed as in $\mathbf{Gph}$. In other terms, the right adjoint creates limits.

Finally, here's a counterexample to the left adjoint preserving colimits. Consider the two morphisms from the terminal graph to the graph with one vertex and two edges. Their equaliser is the discrete graph with one vertex, which is a digraph. However, applying the left adjoint to our morphisms, we get twice the identity on the terminal digraph, whose equaliser is not discrete.

-
There are some typos. Left adjoints preserve colimits, not limits. In fact, this particular left adjoint does not preserve limits. (Exercise.) –  Zhen Lin Oct 2 '13 at 13:42
Nice answer; +1. It might be worth adding that $\mathbf{Dig}$ ought to be a quasitopos as well, as a category of concrete sheaves on a concrete site. For some related examples, see ncatlab.org/nlab/show/quasitopos#examples_28. –  user43208 Oct 2 '13 at 13:47
The conclusion of your last paragraph should be "the right adjoint creates limits", not "the left adjoint preserves limits". –  Zhen Lin Oct 2 '13 at 14:07
@TomHirschowitz I'm not seeing the problem. Note that a reflective subcategory is the category of algebras for the monad induced by the adjunction (with right adjoint the inclusion functor). Then a category of algebras inherits limits (i.e., has its limits reflected) from the base category, in this case $\mathbf{Gph}$. –  user43208 Oct 2 '13 at 14:27
No, it doesn't imply that. For another, perhaps more familiar example: $\text{Cat}$ is a reflective subcategory of simplicial sets, but the reflector doesn't preserve general limits. Similarly, the associated sheaf functor from a category of presheaves does not preserve general limits; it's the same type of situation. –  user43208 Oct 2 '13 at 14:36

Since it might be of interest to porton or others, I'll expand on my earlier comment, that the category of digraphs is in fact a Grothendieck quasitopos. Hence it is not only complete and cocomplete, it is also locally cartesian closed, among other things.

First, recall that the category of 'multigraphs' $\mathbf{Gph}$ (as in Tom Hirschowitz's answer) is the topos of presheaves $G^{op} \to \mathbf{Set}$ on the category

$$G = (0 \stackrel{\overset{s}{\longrightarrow}}{\underset{t}{\longrightarrow}} 1).$$

Then, I claim that the inclusion $i: \mathbf{Dig} \to \mathbf{Gph}$ in Tom's answer is the same as the inclusion of separated presheaves for the $\neg\neg$-topology. It is well-known that separated presheaves for a Grothendieck topology form a Grothendieck quasitopos (see for example Johnstone's Elephant).

The claim is not very hard to check. The representable $\hom_G(-, 1)$ is the digraph $\bullet \to \bullet$, and the representable $\hom_G(-, 0)$ is the digraph $\bullet$; it may be calculated that the only $\neg\neg$-dense subpresheaf of $\hom(-, 0)$ is $\hom(-, 0)$ itself, and that the only $\neg\neg$-dense subpresheaf of $\hom(-, 1)$ besides itself is the digraph inclusion

$$(\bullet \;\;\; \bullet) \hookrightarrow (\bullet \to \bullet).$$

Now a presheaf $X$ on $G$ is separated if, for each object $c$ and each $\neg\neg$-dense inclusion $i: F \hookrightarrow \hom(-, c)$, the induced map

$$X(c) \cong \mathbf{Set}^{G^{op}}(\hom(-, c), X) \stackrel{\mathbf{Set}^{G^{op}}(i, X)}{\to} \mathbf{Set}^{G^{op}}(F, X)$$

is injective. Since we have only one non-trivial dense inclusion (the digraph inclusion displayed above), the separation condition on $X$ boils down to saying that the canonical map

$$X(1) \to \hom((\bullet \;\;\; \bullet), X) \cong X(0) \times X(0)$$

is injective, which is to say that the map taking each edge $e \in X(1)$ to the source-target pair $(s^\ast(e), t^\ast(e))$ is injective. But this just means $X$ is isomorphic to a digraph (in the sense of this post), so we are done. (Details can be made available on request.)

-
Beautiful! Thanks for sharing (I'd probably never have checked this up). –  Tom Hirschowitz Oct 3 '13 at 6:48