Pullbacks and pushouts in the category of digraphs?

Question

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.

Please help me to examine existence of pullbacks and pushouts in the category of digraphs.

Answer 1

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.)

Answer 2

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 limits. 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.

[Thanks for the comments!]