category of paths on a graph

A nice class of illustrative examples of some notions of category theoryis provided by categories of paths on a graph.

Let $G$ be an undirected graph. Denote the set of vertices of $G$ by “$V$”and denote the set of edges of $G$ by “$E$”.

A path of the graph $G$ is an ordered tuplet of vertices $(x_1,x_2,\mathrm{\dots }{x}_n)$such that, for all $i$ between $1$ and $n-1$, there exists an edge connecting$x_i$ and $x_{i+i}$. As a special case, we allow trivial paths which consistof a single vertex — soon we will see that these in fact play an importantrole as identity elements in our category.

In our category, the vertices of the graph will be the objects and themorphisms will be paths; given two of these objects $a$ and $b$, we set$\mathrm{Hom}(a,b)$ to be the set of all paths $(x_1,x_2,\mathrm{\dots }{x}_n)$such that $x_1=a$ and $x_n=b$. Given an object $a$, we set $1_a=(a)$,the trivial path mentioned above.

To finish specifying our category, we need to specify the composition operation.This operation will be the concatenation of paths, which is defined as follows:Given a path $(x_1,x_2,\mathrm{\dots },x_n)\in \mathrm{Hom}(a,b)$ and a path$(y_1,y_2,\mathrm{\dots },y_m)\in \mathrm{Hom}(a,b)$, we set

$$a\circ b=(x_1,x_2,\mathrm{\dots }{x}_n,y_2,\mathrm{\dots },y_m).$$

(Remember that $x_n=y_1=b$.) To have a bona fide category, we need tocheck that this choice satisfies the defining properties (A1 - A3 in theentry http://planetmath.org/node/965category). This is rather easily verified.

A1: Given a morphism $(x_1,x_2,\mathrm{\dots }{x}_n)$, it can onlybelong to $\mathrm{Hom}(a,b)$ if $x_1=a$ and $x_n=b$, hence$\mathrm{Hom}(a,b)\cup \mathrm{Hom}(c,d)=\mathrm{\varnothing }$ unless$a=c$ and $b=d$.

A2: Suppose that we have four objects $a,b,c,d$ and threemorphisms, $(x_1,x_2,\mathrm{\dots }{x}_n)\in \mathrm{Hom}(a,b)$,$(y_1,y_2,\mathrm{\dots }{y}_m)\in \mathrm{Hom}(b,c)$, and$(z_1,z_2,\mathrm{\dots }{z}_k)\in \mathrm{Hom}(c,d)$. Then,by the definition of the operation $\circ$ given above,

$((x_1,x_2,\mathrm{\dots },x_n)\circ ($$y_1,y_2,\mathrm{\dots },y_m))\circ (z_1,z_2,\mathrm{\dots },z_k)$

$=(x_1,x_2,\mathrm{\dots },x_n,y_2,\mathrm{\dots },y_m)\circ (z_1,z_2,\mathrm{\dots },z_k)$

$=(x_1,x_2,\mathrm{\dots },x_n,y_2,\mathrm{\dots },y_m,z_2,\mathrm{\dots },z_k)$

$(x_1,x_2,\mathrm{\dots },x_n)\circ ($$(y_1,y_2,\mathrm{\dots },y_m)\circ (z_1,z_2,\mathrm{\dots },z_k))$

$=(x_1,x_2,\mathrm{\dots },x_n)\circ (y_1,y_2,\mathrm{\dots },y_m,z_2,\mathrm{\dots },z_k)$

$=(x_1,x_2,\mathrm{\dots },x_n,y_2,\mathrm{\dots },y_m,z_2,\mathrm{\dots },z_k).$

Since these two quantities are equal, the operation is associative.

A3: It is easy enough to check that paths with a singlevertex act as identity elements:

$(x_1)\circ (x_1,x_2,\mathrm{\dots },x_n)$$=(x_1,x_2,\mathrm{\dots },x_n)$

$(x_1,x_2,\mathrm{\dots },x_n)\circ (x_n)$$=(x_1,x_2,\mathrm{\dots },x_n)$

It is also possible to consider the equivalence class of pathsmodulo retracing. To introduce this category, we first definea binary relation $\approx$ on the class of paths as follows:Let $A$ and $B$ be any two paths such that the right endpointof $A$ is the same as the left endpoint of $B$, i.e. $A\in \mathrm{Hom}(a,b)$ and $B\in \mathrm{Hom}(b,c)$for some vertices $a,b,c$ of our graph. Let $d$ be any vertexwhich shares an edge with $d$. Then we set $A\circ B\approx A\circ (c,d,c)\circ B$.

Let $\sim$ be the smallest equivalence relations which contains$\approx$. We will call this equivalence relation retracing.

As defined above, it may not intuitively obvious what thisequivalence amounts to. To this end, we may consider a differentdescription. Define the reversal of a path to be thepath obtained by reversing the order of the vertices traversed:

$${(x_1,x_2,\mathrm{\dots },x_{n-1},x_n)}^{-1}=(x_n,x_{n-1},\mathrm{\dots },x_2,x_1)$$

Then we may show that two paths are equivalent under retracingif they may both be obtained from a third path by insertingterms of the form $X{X}^{-1}$. In symbols, we claim that $A\sim B$if there exists an integer $nÃ\mathrm{¯}Â\mathrm{¼}\AA \mathrm{¾}0$ and paths $X_1,\mathrm{\dots }{X}_{n+1},Y_1,\mathrm{\dots }{Y}_{n-1},Z_1,\mathrm{\dots }{Z}_n$ such that

$$A=X_1\circ X_1^{-1}\circ Z_1\circ X_2\circ X_2^{-1}\circ \mathrm{\cdots }\circ X_{n-1}\circ X_{n-1}^{-1}\circ Z_n\circ X_n\circ X_n^{-1}\circ Z_n\circ X_{n+1}\circ X_{n+1}^{-1}$$

and

$$B=Y_1\circ Y_1^{-1}\circ Z_1\circ Y_2\circ Y_2^{-1}\circ \mathrm{\cdots }\circ Y_{n-1}\circ Y_{n-1}^{-1}\circ Z_n\circ Y_n\circ Y_n^{-1}\circ Z_n\circ Y_{n+1}\circ Y_{n+1}^{-1}$$

This characterization explains the choice of the term “retracing” —we do not change the equivalence class of the path if we happen towander off somewhere in the course of following the path but thenbacktrack and pick the path up again where we left off on ourdigression.

Rather than presenting a detailed formal proof, we will sketch howthe two definitions may be shown to be equivalent.