1.2.6 Example: The Path Category of a Directed Graph

Let $S_{\bullet }$ be a simplicial set of dimension $\leq 1$. In this section, we will show that the homotopy category $\mathrm{h} \mathit{S}_{\bullet }$ of Notation admits a concrete description, which can be conveniently described using the language of directed graphs.

Construction (The Path Category). Let $G$ be a directed graph (Definition 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_1, \dots , e_ m)$ 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 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) = e_ i$; we can represent $G$ graphically by the diagram

\[ \xymatrix { 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 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 Example Note that the elements of $M$ can be identified with (possibly empty) sequences of elements of the set $\operatorname{Edge}(M)$, 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 below).

Example 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 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 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 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 map of simplicial sets, in the sense of Definition 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}}) \]

agrees with $F$. Unwinding the definitions, we see that this agreement imposes the following requirements on $F$:


For each vertex $v \in \operatorname{Vert}(G)$, we have $F(x) = f(x)$ (as objects of $\operatorname{\mathcal{C}}$).


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). \]

Remark In the proof of Proposition, we have implicitly invoked the fact that every category $\operatorname{\mathcal{C}}$ satisfies the generalized associative law: every sequence of composable morphisms

\[ X_0 \xrightarrow {f_1} X_1 \xrightarrow {f_2} X_2 \rightarrow \cdots \xrightarrow {f_ n} X_ n \]

has a well-defined composition $f_ n \circ f_{n-1} \circ \cdots \circ f_1$, which can be computed in terms of the binary composition law by inserting parentheses arbitrarily. One might object that this logic is circular: the generalized associative law is essentially equivalent to Proposition (applied to the graph $G$ described in Example In ยง1.4.7, we will establish an $\infty $-categorical generalization of Proposition (Theorem, whose proof will avoid this sort of circular reasoning (see Remark

Definition A category $\operatorname{\mathcal{C}}$ is free if it is isomorphic to $\operatorname{Path}[G]$, for some graph $G$.

We close this section with a characterization of those categories which are free in the sense of Definition

Definition 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 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 Definitions and 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 with a functor $F: \operatorname{Path}[ \mathrm{Gr}_0(\operatorname{\mathcal{C}}) ] \rightarrow \operatorname{\mathcal{C}}$.

Proposition Let $\operatorname{\mathcal{C}}$ be a category. The following conditions on $\operatorname{\mathcal{C}}$ are equivalent:


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]$.


The functor $F: \operatorname{Path}[ \mathrm{Gr}_0(\operatorname{\mathcal{C}})] \rightarrow \operatorname{\mathcal{C}}$ an isomorphism of categories.


The functor $F: \operatorname{Path}[ \mathrm{Gr}_0(\operatorname{\mathcal{C}})] \rightarrow \operatorname{\mathcal{C}}$ is an equivalence of categories.


The functor $F: \operatorname{Path}[ \mathrm{Gr}_0(\operatorname{\mathcal{C}})] \rightarrow \operatorname{\mathcal{C}}$ is fully faithful.


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 $\square$