Todd Trimble category of simple graphs

Contents

Introduction

Both category theory? and graph theory? study patterns based on diagrams? consisting of nodes and edges. Despite this surface impression, there is in fact very little interaction between the scientific communities of category theorists and of graph theorists.

This article is a modest bridge, indicating that the category? of graphs? (in the usual graph-theorist’s sense – see for example Diestel) has some very nice properties.

Simple graphs as relations

By a simple graph?, we mean a set? $V$ equipped with a symmetric? reflexive? relation? $E$. Morphisms? between simple graphs are functions? which preserve the given relations. Elements of $V$ are called vertices. Write $E(x, y)$ to say $(x, y) \in E$.

When drawing graphs, we put an edge between vertices $x$, $y$ iff $x \neq y$ and $E(x, y)$. In particular, we will not bother drawing an edge between $x$ and itself; we can think of it as tacitly there if we like. Perhaps better yet, that tacit edge can be thought of as a path of length $0$ from $x$ to itself (and who bothers drawing a path of length $0$?). In any case, it is clear that there is a natural bijection between

• simple graph structures on $V$ in the graph-theorist’s sense (i.e., graphs that are undirected, loop-free, and with at most one edge between two vertices), and

• reflexive symmetric relations on $V$;

thus we are within our rights to identify these two concepts.

This maneuver allows a simple definition of morphism? as a function? (between the sets of vertices) that preserves the edge relation:

This then includes natural operations like edge contractions as quotients. Namely, if $f \colon G \to H$ is a morphism as defined above, and if we have $G(x, y)$ and $f(x) = f(y) = v$, we still have $H(f(x), f(y))$ by default, so we can think of $f$ as contracting the edge between $x$ and $y$ in $G$ down to an edge of length $0$ between $v$ and itself in $H$.

The category? of simple graphs is denoted by $SimpGph$.

Properties of $SimpGph$

The category $SimpGph$ has very good properties. For example,

It is easy to describe monos? and epis? in $SimpGph$. For, let $\Gamma = \hom(1, -): SimpGph \to Set$ be the underlying vertex-set forgetful functor?.

We omit the easy proof. Next we have two easy results:

It follows that $\Gamma: SimpGph \to Set$ both preserves and reflects monos and epis. As a result, we can prove various simple exactness results in $SimpGph$. For instance:

As already observed, there is a chain of adjoint functors $\Delta \dashv \Gamma \dashv \nabla: Set \to SimpGph$. But in fact there is a fourth functor in the chain: $\Delta$ has a left adjoint $\Pi: SimpGph \to Set$, the connected components? functor. If $E$ is the simple graph consisting of two vertices $a, b$ with an edge between them, then there is a reflexive fork

and $\Pi$ is formed as a reflexive coequalizer? of the induced diagram:

Equalizers and coequalizers

If $f, g \colon G \stackrel{\to}{\to} H$ are maps in $SimpGph$, then their equalizer? $Eq(f, g) = i \colon K \to G$ is given at the vertex level by

and at the edge level by $K(x, y) \Leftrightarrow G(i(x), i(y))$; in other words, if $x, y$ belong to $K$ and there is an edge between them in $G$, then that edge lies in $K$. To express this last condition, we say the subgraph $i$ is full (at the edge level).

Thus, $i$ is a regular mono in $SimpGph$ iff both $\Gamma(i)$ is monic in $Set$ and $i$ is full at the edge level.

The coequalizer? of $f$ and $g$, say $Coeq(f, g) = q \colon H \to Q$, is given at the vertex level by

and at the edge level by taking the image of the composite $E_H \hookrightarrow Vert(H)^2 \stackrel{q^2}{\to} Vert(Q)^2$, so that

Thus, $q$ is a regular epimorphism? if it is surjective at both the vertex and edge levels.

Ternary factorization

The category of simple graphs has a ternary factorization system? as follows: each morphism $f \colon G \to H$ factors as

where

• $q$ is a surjection between vertex-sets and at the edge level, i.e., is a regular epi?;

• $a$ induces an identity between vertex-sets (hence is jointly monic and epic?), but without necessarily being full at the edge level;

• $i$ is given by an injection between vertex-sets and is full at the edge level, and (thus) is a regular mono?.

The factorization of $f$ into $q$ followed by $i \circ a$ is the (regular epi)-mono factorization, while the factorization of $f$ into $a \circ q$ followed by $i$ is the epi-(regular mono) factorization. To round out the discussion, we prove that regular monos are stable under pushout (which ensures that the epi-(regular mono) factorization is an orthogonal factorization system?).

References

• Reinhard Diestel, Graph Theory (Second Edition), Graduate Texts in Mathematics 173, Springer (2000).

• Jiri Adamek? and H. Herrlich, Cartesian closed categories, quasitopoi, and topological universes. Comm. Math. Univ. Carol., Vol. 27, No. 2 (1986), 235-257. (web)