Contents

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

## 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:

$(x,y) \in E_G \;\Rightarrow\; (f(x),f(y)) \in E_H .$

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,

###### Theorem

$SimpGph$ is a Grothendieck quasitopos?. In particular, it is a regular category? and even a logos?, and $SimpGph^{op}$ is also regular. It is also $\infty$-extensive?.

###### Proof

(See also Adamek and Herrlich.) Let $C$ be the category of sets (or cardinality) $1$ and $2$ and functions between them. A presheaf on $C$ is a directed reflexive (multi)graph equipped with a direction-reversing involution on the set of edges. For this presheaf topos, there is just one nontrivial $\neg\neg$-dense sieve, namely the inclusion

$(s, t): \hom(-, 1) + \hom(-, 1) \to \hom(-, 2)$

and so the category of $\neg\neg$-separated presheaves? is equivalent to the category of presheaves $X$ such that the induced map

$X(2) \cong Set^{C^{op}}(\hom(-, 2), X) \stackrel{(s, t)^\ast}{\to} Set^{C^{op}}(\hom(-, 1) + \hom(-, 1), X) \cong X(1) \times X(1),$

which is the source-target pairing $X(2) \to X(1) \times X(1)$, is monic. Such a structure is tantamount to a set $V = X(1)$ equipped with a reflexive symmetric binary relation. On the other hand, a Grothendieck quasitopos is, essentially by definition, the category of separated presheaves for a topology on a presheaf topos, in this case the $\neg\neg$-topology.

Being a quasitopos with small coproducts, it is $\infty$-extensive provided that coproducts are disjoint. However, this is trivial to check (it even suffices to check, according to Elephant? 2.6.5, that $0 \to 1$ is a regular monomorphism?, or that $1 + 1$ is a disjoint coproduct, which it obviously is).

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

###### Proposition

The forgetful functor $\Gamma = \hom(1, -): SimpGph \to Set$ is faithful, in fact exhibits $SimpGph$ as a topological concrete category?.

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

###### Proposition

$\Gamma$ reflects? monos and epis (because $\Gamma$ is faithful).

###### Proposition

$\Gamma$ preserves? limits? and colimits? (because it has a left adjoint? $\Delta$ and a right adjoint? $\nabla$).

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:

###### Lemma

In $SimpGph$, the pushout? of any mono is a mono.

###### Proof

Suppose we have a pushout diagram in $SimpGph$:

$\array{ G & \to & H \\ ^\mathllap{mono} \downarrow & & \downarrow^\mathrlap{k} \\ G' & \to & H' }$

Since $\Gamma$ preserves both pushouts and monos, and since the pushout of a mono in $Set$ is a mono, we have that $\Gamma(k)$ is monic in $Set$. Since $\Gamma$ reflects monos, this means $k$ is monic in $SimpGph$.

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

$a, b: 1 \rightrightarrows E \stackrel{!}{\to} 1$

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

$\hom(1, -) \to hom(E, -) \rightrightarrows hom(1, -) \to \Pi$
###### Proposition

$\Pi \dashv \Delta$, and $\Pi$ preserves products.

###### Proof

$\Pi$ preserves products because being a reflexive coequalizer, it is a sifted colimit? of product-preserving functors. For graphs $G$, there is a natural map $u G: G \to \Delta \Pi G$ which at the underlying vertex-set level sends a vertex to its connected component; if $S$ is any set, then a graph map $f: G \to \Delta S$ must send any two vertices with an edge between them to the same point, and so $f$ factors as $G \stackrel{u G}{\to} \Delta \Pi G \stackrel{\Delta g}{\to} \Delta S$ for a unique map $g: \Pi G \to S$, and this establishes the adjunction $\Pi \dashv \Delta$.

### 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

$\Gamma(i) = Eq(\Gamma(f), \Gamma(g))$

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

$\Gamma(q) = Coeq(\Gamma(f), \Gamma(g))$

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

$Q(x, y) \Leftrightarrow \exists_{u, v} H(u, v) \wedge q(u) = x \wedge q(v) = y.$

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

$G \stackrel{q}{\to} G' \stackrel{a}{\to} H' \stackrel{i}{\to} H$

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)
category: category
Created on June 13, 2017 at 11:04:24 by Todd Trimble