The Category of Graphs
May 03, 2017
The main goal of this post is to show how some of the main ingredients of category theory - categories, functors, natural transformations, and so on, can provide a satisfying foundation for the theory of graphs. My hope is that this post will provide the reader with some intuition and a rich source of examples for more sophisticated category theoretic constructions.
Categories and Functors
To begin, let us review the definition of a category and of a functor between categories. This discussion will culminate in an abstract but useful way to think about graphs.
A category $C$ is a class $\ob(C)$ of objects together with a class $\hom(a,b)$ of morphisms between each pair $a, b$ of objects and a composition map $\circ \colon \hom(a,b) \times \hom(b,c) \to \hom(a,c)$ which has the following properties:
- Existence of identies: for each object $a$ there is a morphism $1_a$ in $\hom(a, a)$ which satisfies:
for every morphism $f \colon x \to a$ and every morphism $g \colon a \to x$.
- Associativity: given morphisms $f \colon a \to b$, $g \colon b \to c$, and $h \colon c \to d$ the triple composition is well-defined independently of parentheses:
Note that we do not insist that the objects or morphisms form sets; this is to avoid paradoxes in set theory which arise when one tries to sloppily use set theoretic language to construct very large sets.
One of the most important examples of a category is the category $\Set$ whose objects are sets and whose morphisms are functions between sets. For each set $S$ the identity morphism $1_S \colon S \to S$ is the function $1_S(x) = x$, and the composition law for morphisms is just ordinary composition of functions.
Every category $\mathcal{C}$ has an opposite, denoted $\mathcal{C}^{op}$, which is obtained by reversing the morphisms in $\mathcal{C}$. Thus the objects in $\mathcal{C}^{op}$ are the same, but for every morphism $f \colon a \to b$ in $\mathcal{C}$ there is a morphism $f^{op} \colon b \to a$ in $\mathcal{C}^{op}$.
There is a natural notion of mapping from one category to another, given as follows:
Let $\mathcal{C}$ and $\mathcal{D}$ be categories. A (covariant) functor $F \colon \mathcal{C} \to \mathcal{D}$ is a mapping which associates to each object $a$ in $\ob(\mathcal{C})$ an object $F(a)$ in $\ob(\mathcal{D})$ and to each morphism $f \colon a \to b$ in $\mathcal{C}$ a morphism $F(f) \colon F(a) \to F(b)$ according to the following properties:
- $F(1_a) = 1_{F(a)}$
- $F(g \circ f) = F(g) \circ F(f)$
Given any category $\mathcal{C}$ the identity functor on $\mathcal{C}$ is the functor $\mathcal{C} \to \mathcal{C}$ which maps each object to itself and each morphism to itself.
Let $\mathcal{C}$ and $\mathcal{D}$ be categories, and fix an object $d$ in $\mathcal{D}$. The mapping which sends every object in $\mathcal{C}$ to $d$ and every morphism to $1_d$ is a functor $\mathcal{C} \to \mathcal{D}$, called a constant functor.
We conclude with an exercise which introduces a category theoretic way to think about graphs.
Let $X$ denote the category with exactly two objects $a$ and $b$ and exactly two distinct morphisms $s, t \colon a \to b$ (together with the identity morphisms $1_a$ and $1_b$). Show that a directed multigraph (often called a quiver in the literature) is the same thing as a functor $X \to \Set$.
Recall that a directed multigraph consists of a set $V$ of vertices together with a set $E$ of edges. Each edge has a source vertex and a target vertex, though in general one allows different edges to have the same source and target; thus part of the structure of the graph is a function $g \colon E \to V \times V$ sending an edge to its source and target vertices.
Now, let $F \colon X \to \Set$ be a functor. Since $F$ maps objects to objects we have two sets $F(a)$ and $F(b)$, and since $F$ maps morphisms to morphisms we also have two functions $F(s), F(t) \colon F(a) \to F(b)$. From these ingredients we aim to manufacture a graph.
The idea is as follows: let $E = F(a)$, $V = F(b)$, and define $g \colon E \to V \times V$ by
\[g(e) = (F(s)(e), F(t)(e))\]In other words, $F(a)$ is the edge set of the graph, $F(b)$ is the vertex set of the graph, and the maps $F(s)$ and $F(t)$ determine the source and target, respectively, of each edge.
This process is of course reversible: starting with a graph $G = (V, E, g)$ where $g \colon E \to V \times V$ is the source-and-target map, we can construct a functor $F \colon X \to \Set$ as follows. The values of $F$ on objects is given by $F(a) = E$ and $F(b) = V$. To define $F$ on morphisms let $\pi_1$ and $\pi_2$ be the functions $V \times V \to V$ which project onto the first and second factors, respectively, so that $\pi_1(v_1, v_2) = v_1$ and $\pi_2(v_1, v_2) = v_2$. Finally, define:
\[F(s) = \pi_1 \circ g, \quad F(t) = \pi_2 \circ g\]Ordinarily we would need to check that $F$ preserves compositions of morphisms, but since there are no nontrivial compositions in $X$ we are done.
Given a category $\mathcal{C}$, a presheaf on $\mathcal{C}$ is by definition a functor $F \colon \mathcal{C}^{op} \to \Set$. So the previous exercise shows that a graph is the same thing as a presheaf on the category $X^{op}$.
A sheaf is a presheaf with some additional structure; thanks to the work of Alexander Grothendieck much of modern algebraic geometry (and increasingly the rest of geometry) is organized around the theory of sheaves. I have also seen sheaves in some computer science papers and so we may need to confront them more seriously later on, but for now we will get by with this parenthetical remark.
Natural Transformations
In the previous section we precisely defined the notion of a category and of a functor between categories, and we concluded by arguing that a directed multigraph can be thought of as a functor $X \to \Set$ where $X$ is a well-chosen category. In this section we will develop the functorial perspective on graphs further by introducing the concept of a graph homomorphism.
Informally, a graph homomorphism is a mapping from one graph to another which sends vertices to vertices and edges to edges. To be more precise we will use the definition of a directed multigraph introduced in the last section, wherein a graph is a triple $G = (V, E, g)$ consisting of a vertex set, an edge set, and a source-and-target map $g \colon E \to V \times V$.
Let $G_1 = (V_1, E_1, g_1)$ and $G_2 = (V_2, E_2, g_2)$ be directed multigraphs. A graph homomorphism $\phi \colon G_1 \to G_2$ is a pair of functions $\phi_V \colon V_1 \to V_2$ and $\phi_E \colon E_1 \to E_2$ which are compatible with the source-and-target maps in the sense that:
\[g_2 \circ \phi_E = (\phi_V \times \phi_V) \circ g_1\]Informally, the compatibility condition is the statement that if we map an edge in $G_1$ to an edge in $G_2$ along $\phi_E$ and then find its source and target vertices, we get the same answer as if we had first found the source and target vertices of the original edge in $G_1$ and then mapped them to $G_2$ along $\phi_V$. This sort of compatibility condition is quite common, and they are often expressed using diagrams:
\[\begin{CD} E_1 @>{g_1}>> V_1 \times V_1 \\ @V{\phi_E}VV @VV{\phi_V \times \phi_V}V \\ E_2 @>{g_2}>> V_2 \times V_2 \\ \end{CD}\]The compatibility condition is equivalent to the statement that this diagram commutes, meaning any chain of morphisms which start and end in the same place will produce the same result.
This defines the notion of a graph homomorphism using classical graph theory language. But we saw in the last section that a graph can be thought of as a functor; what is a graph homomorphism according to this perspective? It turns out that there is a general notion of a mapping between functors called a “natural transformation”, defined as follows:
Let $F$ and $G$ be functors from a category $\mathcal{C}$ to a category $\mathcal{D}$. A natural transformation $\eta$ from $F$ to $G$ is a family of morphisms $\eta_C \colon F(C) \to G(C)$ in $\mathcal{D}$ parametrized by the objects $C$ of $\mathcal{C}$ which is compatible with the morphisms of $\mathcal{C}$ in the sense that:
\[\eta_{C_2} \circ F(f) = G(f) \circ \eta_{C_1}\]for every morphism $f \colon C_1 \to C_2$ in $\mathcal{C}$. The morphism $\eta_C$ is called the component of $\eta$ at $C$.
As before it may be clearer to express the compatibility condition as the commutativity of a diagram; in this case the diagram is:
\[\begin{CD} F(C_1) @>{F(f)}>> F(C_2) \\ @V{\eta_{C_1}}VV @VV{\eta_{C_2}}V \\ G(C_1) @>{G(f)}>> G(C_2) \\ \end{CD}\]Let $G_1$ and $G_2$ be directed multigraphs, and let $F_1$ and $F_2$ be the corresponding functors $X \to \Set$ (under the identification between graphs and functors at the end of the previous section). Show that a graph homomorphism $\phi \colon G_1 \to G_2$ is the same thing is a natural transformation $\eta \colon F_1 \to F_2$.
Let us begin with a graph homomorphism $\phi \colon G_1 \to G_2$ and construct the corresponding natural transformation $\eta \colon F_1 \to F_2$. Recall that $\phi$ consists of a pair of functions $\phi_V \colon V_1 \to V_2$ and $\phi_E \colon E_1 \to E_2$ which are compatible with the source-and-target maps.
To construct $\eta$ we must specify morphisms $\eta_a \colon F_1(a) \to F_2(a)$ and $\eta_b \colon F_1(b) \to F_2(b)$ corresponding to the objects $a$ and $b$ of $X$. Since $F_1$ and $F_2$ each send $a$ to the edge sets of the corresponding graphs, let $\eta_a = \phi_E$; similary, since $b$ maps to vertex sets we may define $\eta_b = \phi_V$. To show that $\eta_a$ and $\eta_b$ together define a natural transformation, we must check the compatibility condition:
\[\eta_b \circ F_1(f) = F_2(f) \circ \eta_a\]for any morphism $f \colon a \to b$. To verify this, we will use the compatibility condition between $\phi_E$ and $\phi_V$ from the definition of a graph homomorphism, which asserts:
\[\begin{equation} \label{compatible} g_2 \circ \phi_E = (\phi_V \times \phi_V) \circ g_1 \end{equation}\]Projecting both sides of this equation onto the first factor of $V_2 \times V_2$, we get:
\[\pi_1 \circ g_2 \circ \phi_E = \pi_1 \circ (\phi_V \times \phi_V) \circ g_1 = \phi_V \circ \pi_1 \circ g_1\]But according to the correspondence between graphs and functors we have that $\pi_1 \circ g_2 = F_2(s)$ and $\pi_1 \circ g_1 = F_1(s)$ where $s$ is one of the two morphisms $a \to b$ in $X$.
Substituting $\phi_E = \eta_a$ and $\phi_V = \eta_b$, we get:
This is the compatibility condition between $\eta$ and $s$. Compatibility between $\eta$ and $t$ follows by projecting the compatibility equation \eqref{compatible} onto the second factor of $V_2 \times V$. There are no further morphisms (other than the identities) in $X$, so we have shown that $\eta$ is indeed a natural transformation.
To complete the exercise, we must also show that every natural transformation $\eta \colon F_1 \to F_2$ determines a graph homomorphism $G_1 \to G_2$. This amounts to reversing the construction above: the component $\eta_a$ is a function $E_1 \to E_2$, the component $\eta_b$ is a function $V_1 \to V_2$, and the compatibility condition in the definition of graph homomorphism follows from the compatibility condition in the definition of natural transformation. The details are left to the reader.
Let us conclude this section with a bit of language. Given natural transformations $\eta \colon F \to G$ and $\mu \colon G \to H$, one can define the composition $\mu \circ \eta \colon F \to H$: the component of the composition at a given object is the composition of the components at that object. (It is left as an exercise to check that the composition defined in this way satisfies the required compatibility condition.) It is fairly straightforward to check that composition of natural transformations is associative, and it is also straightforward to define an identity natural transformation (whose component at every object is the identity morphism).
Thus there is a category $\text{Fun}(\mathcal{C}, \mathcal{D})$ (also written $\mathcal{D}^\mathcal{C}$ or $[\mathcal{C}, \mathcal{D}]$) whose objects are functors between the categories $\mathcal{C}$ and $\mathcal{C}$ and whose morphisms are natural transformations between functors. Categories of this form are called functor categories, and they are generally nice categories to work with - at least, they often inherit nice properties from $\mathcal{D}$. One of the most powerful techniques in category theory is to embed a poorly behaved category into a well-chosen functor category; the added flexibility available in the functor category can then be used to deduce nontrivial statements about the objects and morphisms in the original category.
An important special case involves the category of presheaves over a small category $\mathcal{C}$:
\[\text{PSh}(\mathcal{C}) = \text{Fun}(\mathcal{C}^{op}, \Set)\]The Yoneda Lemma - an important result in category theory which we will revisit in a later post - constructs an embedding of $\mathcal{C}$ into its presheaf category. The upshot of the two exercises on graphs in this post is that the category of directed multigraphs equipped with graph homomorphisms is equivalent to the category of presheaves over the seemingly innocuous category $X^{op}$ with two objects and two morphisms from one object to the other. This is a useful way to think about graphs, and it also shows that the category of presheaves over a category $\mathcal{C}$ can be much richer and more interesting that $\mathcal{C}$ itself.