1.3.7 Example: The Path Category of a Directed Graph
Let $S$ be a simplicial set of dimension $\leq 1$. In this section, we will show that the homotopy category $\mathrm{h} \mathit{S}$ of Notation 1.3.6.3 admits a concrete description, which can be conveniently described using the language of directed graphs.
Construction 1.3.7.1 (The Path Category). Let $G$ be a directed graph (Definition 1.1.6.1). For each edge $e \in \operatorname{Edge}(G)$, we let $s(e), t(e) \in \operatorname{Vert}(G)$ denote the source and target of $e$, respectively. If $x$ and $y$ are vertices of $\operatorname{Vert}(G)$, then a path from $x$ to $y$ is a sequence of edges $(e_ n, e_{n-1}, \ldots , e_1)$ satisfying
\[ s(e_1) = x \quad \quad t(e_ i) = s(e_{i+1}) \quad \quad t(e_ m) = y, \]
By convention, we regard the empty sequence of edges as a path from each vertex $x \in \operatorname{Vert}(G)$ to itself.
We define a category $\operatorname{Path}[G]$ as follows:
The objects of $\operatorname{Path}[G]$ are the vertices of $G$.
For every pair of vertices $x,y \in \operatorname{Vert}(G)$, we let $\operatorname{Hom}_{ \operatorname{Path}[G]}(x,y)$ denote the set of all paths $(e_ m, \dots , e_1)$ from $x$ to $y$.
For every vertex $x \in \operatorname{Vert}(G)$, the identity morphism $\operatorname{id}_{x}$ in the category $\operatorname{Path}[G]$ is the empty path from $x$ to itself.
Let $x,y,z \in \operatorname{Vert}(G)$. Then the composition law
\[ \circ : \operatorname{Hom}_{\operatorname{Path}[G]}( y, z) \times \operatorname{Hom}_{\operatorname{Path}[G]}(x,y) \rightarrow \operatorname{Hom}_{\operatorname{Path}[G]}( x,z) \]
is described by the formula
\[ (e_ n, \cdots , e_1 ) \circ (e'_{m}, \ldots , e'_{1} ) = (e_{n}, \cdots , e_1, e'_{m}, \ldots , e'_{1}). \]
In other words, composition in $\operatorname{Path}[G]$ is given by concatentation of paths.
We will refer to $\operatorname{Path}[G]$ as the path category of the directed graph $G$.
Example 1.3.7.2. Fix an integer $n \geq 0$. Let $G$ be the directed graph with vertex set $\operatorname{Vert}(G) = \{ v_0, v_1, \ldots , v_ n \} $, and edge set $\operatorname{Edge}(G) = \{ e_1, \ldots , e_ n \} $, where each edge $e_{i}$ has source $s(e_ i) = v_{i-1}$ and target $t(e_ i) = v_ i$; we can represent $G$ graphically by the diagram
\[ \xymatrix@R =50pt@C=50pt{ v_0 \ar [r]^-{ e_1 } & v_1 \ar [r]^-{e_2} & \cdots \ar [r]^-{e_{n-1}} & v_{n-1} \ar [r]^-{e_ n} & v_ n. } \]
Let $v_ i$ and $v_ j$ be a pair of vertices of $G$. Then:
If $i \leq j$, there is a unique path from $v_ i$ to $v_ j$, given by the sequence of edges $(e_{j}, e_{j-1}, \ldots , e_{i+1})$.
If $i > j$, then there are no paths from $v_ i$ to $v_ j$.
It follows that the path category $\operatorname{Path}[G]$ is isomorphic to the linearly ordered set $[n] = \{ 0 < 1 < 2 < \cdots < n \} $ (regarded as a category).
Example 1.3.7.3. Let $G$ be a directed graph having a single vertex $\operatorname{Vert}(G) = \{ x \} $. Then the path category $\operatorname{Path}[G]$ has a single object $x$, and can therefore be identified with the category $BM$ associated to the monoid $M = \operatorname{End}_{\operatorname{Path}[G]}(x) = \operatorname{Hom}_{\operatorname{Path}[G]}(x,x)$ (see Construction 1.3.2.5). Note that the elements of $M$ can be identified with (possibly empty) sequences of elements of the set $\operatorname{Edge}(G)$, and that the multiplication on $M$ is given by concatenation of sequences. In other words, $M$ can be identified with the free monoid generated by the set $\operatorname{Edge}(M)$ (this identification is not completely tautological: it can be regarded as a special case of Proposition 1.3.7.5 below).
Example 1.3.7.4. Let $G$ be a directed graph having a single vertex $\operatorname{Vert}(G) = \{ x\} $ and a single edge $\operatorname{Edge}(G) = \{ e \} $ (necessarily satisfying $s(e) = x = t(e)$). Then the path category $\operatorname{Path}[G]$ has a single object $x$ whose endomorphism monoid $\operatorname{End}_{\operatorname{Path}[G]}(x) = \operatorname{Hom}_{\operatorname{Path}[G]}(x,x)$ can be identified with the set $\operatorname{\mathbf{Z}}_{\geq 0}$ of nonnegative integers (with monoid structure given by addition).
Let $G$ be a directed graph, and let $G_{\bullet }$ denote the associated $1$-dimensional simplicial set (see Proposition 1.1.6.9). Then there is an evident map of simplicial sets $u: G_{\bullet } \rightarrow \operatorname{N}_{\bullet }(\operatorname{Path}[G] )$, which carries each vertex $v \in \operatorname{Vert}(G)$ to itself and each edge $e \in \operatorname{Edge}(G)$ to the path consisting of the single edge $e$.
Proposition 1.3.7.5. Let $G$ be a directed graph. Then the map of simplicial sets $u: G_{\bullet } \rightarrow \operatorname{N}_{\bullet }(\operatorname{Path}[G] )$ exhibits $\operatorname{Path}[G]$ as the homotopy category of the simplicial set $G_{\bullet }$, in the sense of Definition 1.3.6.1. In other words, for every category $\operatorname{\mathcal{C}}$, the composite map
\[ \operatorname{Hom}_{\operatorname{Cat}}( \operatorname{Path}[G], \operatorname{\mathcal{C}}) \rightarrow \operatorname{Hom}_{ \operatorname{Set_{\Delta }}}( \operatorname{N}_{\bullet }( \operatorname{Path}[G] ), \operatorname{N}_{\bullet }(\operatorname{\mathcal{C}}) ) \xrightarrow {\circ u} \operatorname{Hom}_{\operatorname{Set_{\Delta }}}(G_{\bullet }, \operatorname{N}_{\bullet }(\operatorname{\mathcal{C}})) \]
is a bijection.
Proof.
Let $f: G_{\bullet } \rightarrow \operatorname{N}_{\bullet }(\operatorname{\mathcal{C}})$ be a morphism of simplicial sets. We wish to show that there is a unique functor $F: \operatorname{Path}[G] \rightarrow \operatorname{\mathcal{C}}$ for which the composite map
\[ G_{\bullet } \xrightarrow {u} \operatorname{N}_{\bullet }( \operatorname{Path}[G] ) \xrightarrow { \operatorname{N}_{\bullet }(F)} \operatorname{N}_{\bullet }(\operatorname{\mathcal{C}}) \]
coincides with $f$. Unwinding the definitions, we see that this agreement imposes the following requirements on $F$:
- $(a)$
For each vertex $v \in \operatorname{Vert}(G)$, we have $F(x) = f(x)$ (as objects of $\operatorname{\mathcal{C}}$).
- $(b)$
For each edge $e \in \operatorname{Edge}(G)$ having $x = s(e)$ and target $y = t(e)$, the functor $F$ carries the path $(e)$ to the morphism $f(e): f(x) \rightarrow f(y)$ in $\operatorname{\mathcal{C}}$.
The existence and uniqueness of the functor $F$ is now clear: it is determined on objects by property $(a)$, and on morphisms by the formula
\[ F( e_ n, e_{n-1}, \cdots , e_1 ) = f(e_ n) \circ f(e_{n-1} ) \circ \cdots \circ f(e_1). \]
$\square$
Definition 1.3.7.7. A category $\operatorname{\mathcal{C}}$ is free if it is isomorphic to $\operatorname{Path}[G]$, for some directed graph $G$.
We close this section with a characterization of those categories which are free in the sense of Definition 1.3.7.7.
Definition 1.3.7.8. Let $\operatorname{\mathcal{C}}$ be a category. We will say that a morphism $f: X \rightarrow Y$ in $\operatorname{\mathcal{C}}$ is indecomposable if $f$ is not an identity morphism, and for every factorization $f = g \circ h$ have either $g = \operatorname{id}_{Y}$ (so $h=f$) or $h = \operatorname{id}_{X}$ (so $g=f$).
Example 1.3.7.9. Let $G$ be a directed graph and let $\vec{e}$ be a morphism in the path category $\operatorname{Path}[G]$, given by a sequence of edges $(e_ n, e_{n-1}, \ldots , e_1)$ satisfying $t(e_ i) = s(e_{i+1})$. Then $\vec{e}$ is indecomposable if and only if $n=1$.
Warning 1.3.7.10. Definitions 1.3.7.7 and 1.3.7.8 are not invariant under equivalence of categories. If $F: \operatorname{\mathcal{C}}\rightarrow \operatorname{\mathcal{D}}$ is an equivalence of categories and $\operatorname{\mathcal{C}}$ is free, then $\operatorname{\mathcal{D}}$ need not be free; if $f$ is an indecomposable morphism in $\operatorname{\mathcal{C}}$, then $F(f)$ need not be an indecomposable morphism of $\operatorname{\mathcal{D}}$.
Let $\operatorname{\mathcal{C}}$ be any category. We define a directed graph $\mathrm{Gr}_0(\operatorname{\mathcal{C}})$ as follows:
The vertices of $\mathrm{Gr}_0(\operatorname{\mathcal{C}})$ are the objects of $\operatorname{\mathcal{C}}$.
The edges of $\mathrm{Gr}_0(\operatorname{\mathcal{C}})$ are the indecomposable morphisms of $\operatorname{\mathcal{C}}$ (where an indecomposable morphism $f: X \rightarrow Y$ is regarded as an edge with source $s(f) = X$ and target $t(f) = Y$).
By construction, the graph $\mathrm{Gr}_0(\operatorname{\mathcal{C}})$ comes equipped with a canonical map $\mathrm{Gr}_0(\operatorname{\mathcal{C}})_{\bullet } \rightarrow \operatorname{N}_{\bullet }(\operatorname{\mathcal{C}})$, which we can identify (by means of Proposition 1.3.7.5) with a functor $F: \operatorname{Path}[ \mathrm{Gr}_0(\operatorname{\mathcal{C}}) ] \rightarrow \operatorname{\mathcal{C}}$.
Proposition 1.3.7.11. Let $\operatorname{\mathcal{C}}$ be a category. The following conditions on $\operatorname{\mathcal{C}}$ are equivalent:
- $(a)$
The category $\operatorname{\mathcal{C}}$ is free. That is, there exists a directed graph $G$ and an isomorphism of categories $\operatorname{\mathcal{C}}\simeq \operatorname{Path}[G]$.
- $(b)$
The functor $F: \operatorname{Path}[ \mathrm{Gr}_0(\operatorname{\mathcal{C}})] \rightarrow \operatorname{\mathcal{C}}$ is an isomorphism of categories.
- $(c)$
The functor $F: \operatorname{Path}[ \mathrm{Gr}_0(\operatorname{\mathcal{C}})] \rightarrow \operatorname{\mathcal{C}}$ is an equivalence of categories.
- $(d)$
The functor $F: \operatorname{Path}[ \mathrm{Gr}_0(\operatorname{\mathcal{C}})] \rightarrow \operatorname{\mathcal{C}}$ is fully faithful.
- $(e)$
Every morphism $f$ in $\operatorname{\mathcal{C}}$ admits a unique factorization $f = f_{n} \circ f_{n-1} \circ \cdots \circ f_1$, where each $f_{i}$ is an indecomposable morphism of $\operatorname{\mathcal{C}}$.
Proof.
The functor $F$ is bijective on objects, which shows that $(b) \Leftrightarrow (c) \Leftrightarrow (d)$. The equivalence of $(d)$ and $(e)$ follows from the definition of morphisms in the path category $\operatorname{Path}[ \mathrm{Gr}_0(\operatorname{\mathcal{C}})]$. The implication $(b) \Rightarrow (a)$ is immediate, and the converse follows from Example 1.3.7.9.
$\square$