Kerodon

$\Newextarrow{\xhookrightarrow}{10,10}{0x21AA}$

1.1.4 Directed Graphs as Simplicial Sets

We now generalize Example 1.1.3.12 to obtain a concrete description of simplicial sets having dimension $\leq 1$ (Proposition 1.1.4.9).

Definition 1.1.4.1. A directed graph $G$ consists of the following data:

  • A set $\operatorname{Vert}(G)$, whose elements we refer to as vertices of $G$.

  • A set $\operatorname{Edge}(G)$, whose elements we refer to as edges of $G$.

  • A pair of functions $s,t: \operatorname{Edge}(G) \rightarrow \operatorname{Vert}(G)$ which assign to each edge $e \in \operatorname{Edge}(G)$ a pair of vertices $s(e)$, $t(e) \in \operatorname{Vert}(G)$ that we refer to as the source and target of $e$, respectively.

Warning 1.1.4.2. The terminology of Definition 1.1.4.1 is not standard. Note that a directed graph $G$ can have distinct edges $e \neq e'$ having the same source $s(e) = s(e')$ and target $t(e) = t(e')$ (for this reason, directed graphs in the sense of Definition 1.1.4.1 are sometimes called multigraphs). Definition 1.1.4.1 also allows graphs which contain loops: that is, edges $e$ satisfying $s(e) = t(e)$.

Remark 1.1.4.3. It will sometimes be convenient to represent a directed graph $G$ by a diagram, having a node for each vertex $v$ of $G$ and an arrow for each edge $e$ of $G$, directed from the source of $e$ to the target of $e$. For example, the diagram

\[ \xymatrix@R =50pt@C=50pt{ & \bullet \ar@ (l,ul) \ar@ /^2pc/[dr] \ar [dr] & \\ \bullet \ar@ /^1.5pc/[rr] \ar [ur] & & \bullet \ar [ll] } \]

represents a directed graph with three vertices and six edges.

Example 1.1.4.4. To every simplicial set $X_{\bullet }$, we can associate a directed graph $G( X_{\bullet } )$ as follows:

  • The vertex set $\operatorname{Vert}( G(X_{\bullet } ) )$ is the set of $0$-simplices of the simplicial set $X_{\bullet }$.

  • The edge set $\operatorname{Edge}( G(X_{\bullet } ) )$ is the set of nondegenerate $1$-simplices of the simplicial set $X_{\bullet }$.

  • For every edge $e \in \operatorname{Edge}( G(X_{\bullet }) ) \subseteq S_1$, the source $s(e)$ is the vertex $d_1(e)$, and the target $t(e)$ is the vertex $d_0(e)$ (here $d_0, d_1: S_1 \rightarrow S_0$ are the face maps of Notation 1.1.1.6).

It will be convenient to construe Example 1.1.4.4 as providing a functor from the category of simplicial sets to the category of directed graphs. First, we need an appropriate definition for the latter category.

Definition 1.1.4.5. Let $G$ and $G'$ be directed graphs (in the sense of Definition 1.1.4.1). A morphism from $G$ to $G'$ is a function $f: \operatorname{Vert}( G ) \amalg \operatorname{Edge}(G) \rightarrow \operatorname{Vert}(G') \amalg \operatorname{Edge}(G')$ which satisfies the following conditions:

$(a)$

For each vertex $v \in \operatorname{Vert}(G)$, the image $f(v)$ belongs to $\operatorname{Vert}(G')$.

$(b)$

Let $e \in \operatorname{Edge}(G)$ be an edge of $G$ with source $v = s(e)$ and target $w = t(e)$. Then exactly one of the following conditions holds:

  • The image $f(e)$ is an edge of $G'$ having source $s( f(e) ) = f(v)$ and target $t( f(e) ) = f(w)$.

  • The image $f(e)$ is a vertex of $G'$ satisfying $f(v) = f(e) = f(w)$.

We let $\operatorname{Graph}$ denote the category whose objects are directed graphs and whose morphisms are morphisms of directed graphs (with composition defined in the evident way).

Warning 1.1.4.6. Note that part $(b)$ of Definition 1.1.4.5 allows the possibility that a morphism of directed graphs $G \rightarrow G'$ can “collapse” edges of $G$ to vertices of $G'$. Many other notions of morphism between (directed) graphs appear in the literature; we single out Definition 1.1.4.5 because of its close connection with the theory of simplicial sets (see Proposition 1.1.4.7 below).

Let $X_{\bullet }$ be a simplicial set and let $G( X_{\bullet } )$ be the directed graph of Example 1.1.4.4. Then the disjoint union $\operatorname{Vert}( G(X_{\bullet }) ) \amalg \operatorname{Edge}( G( X_{\bullet } ) )$ can be identified with the set $X_1$ of all $1$-simplices of $X_{\bullet }$ (where we identify $\operatorname{Vert}( G(X_{\bullet } ) )$ with the collection of degenerate $1$-simplices via the degeneracy map $s_0: X_0 \rightarrow X_1$).

Proposition 1.1.4.7. Let $f: X_{\bullet } \rightarrow Y_{\bullet }$ be a map of simplicial sets. Then the induced map

\[ \operatorname{Vert}( G(X_{\bullet }) ) \amalg \operatorname{Edge}( G(X_{\bullet }) ) \simeq X_1 \xrightarrow {f} Y_1 \simeq \operatorname{Vert}( G(Y_{\bullet } ) ) \amalg \operatorname{Edge}( G(Y_{\bullet }) ) \]

is a morphism of directed graphs from $G( X_{\bullet } )$ to $G( Y_{\bullet } )$, in the sense of Definition 1.1.4.5.

Proof. Since $f$ commutes with the degeneracy operator $s_0$, it carries degenerate $1$-simplices of $X_{\bullet }$ to degenerate $1$-simplices of $Y_{\bullet }$, and therefore satisfies requirement $(a)$ of Definition 1.1.4.5. Requirement $(b)$ follows from the fact that $f$ commutes with the face operators $d_0$ and $d_1$. $\square$

It follows from Proposition 1.1.4.7 that we can regard the construction $X_{\bullet } \mapsto G( X_{\bullet } )$ as a functor from the category $\operatorname{Set_{\Delta }}$ of simplicial sets to the category $\operatorname{Graph}$ of directed graphs.

Proposition 1.1.4.8. Let $X_{\bullet }$ and $Y_{\bullet }$ be simplicial sets. If $X_{\bullet }$ has dimension $\leq 1$, then the canonical map

\[ \operatorname{Hom}_{\operatorname{Set_{\Delta }}}( X_{\bullet }, Y_{\bullet } ) \rightarrow \operatorname{Hom}_{ \operatorname{Graph}}( G( X_{\bullet }), G( Y_{\bullet } ) ) \]

is bijective.

Proof. If $X_{\bullet }$ has dimension $\leq 1$, then Proposition 1.1.3.11 provides a pushout diagram

\[ \xymatrix { \underset { e \in \operatorname{Edge}( G(X_{\bullet }) )}{\coprod } \operatorname{\partial \Delta }^{1} \ar [r] \ar [d] & \underset { e \in \operatorname{Edge}( G(X_{\bullet }) )}{\coprod } \Delta ^{1} \ar [d] \\ \underset { v \in \operatorname{Vert}( G(X_{\bullet }) )}{\coprod } \ar [r] & X_{\bullet }. } \]

It follows that, for any simplicial set $Y_{\bullet }$, we can identify $\operatorname{Hom}_{\operatorname{Set_{\Delta }}}( X_{\bullet }, Y_{\bullet } )$ with the fiber product

\[ ( \underset { e \in \operatorname{Edge}( G(X_{\bullet }) )}{\prod } Y_1) \underset { \prod _{ e \in \operatorname{Edge}( G(X_{\bullet }) )} (Y_0 \times Y_0) }{\times } (\underset { v \in \operatorname{Vert}( G(X_{\bullet }) )}{\prod } Y_0), \]

which is precisely the set of morphisms of directed graphs from $G( X_{\bullet } )$ to $G( Y_{\bullet } )$. $\square$

It follows from Proposition 1.1.4.8 that the theory of simplicial sets of dimension $\leq 1$ is essentially equivalent to the theory of directed graphs.

Proposition 1.1.4.9. Let $\operatorname{Set_{\Delta }}$ denote the category of simplicial sets and let $\operatorname{\mathcal{C}}\subseteq \operatorname{Set_{\Delta }}$ denote the full subcategory spanned by the simplicial sets of dimension $\leq 1$. Then the construction $X_{\bullet } \mapsto G( X_{\bullet } )$ induces an equivalence of categories $\operatorname{\mathcal{C}}\rightarrow \operatorname{Graph}$.

Proof. It follows from Proposition 1.1.4.9 that the functor $X_{\bullet } \mapsto G(X_{\bullet } )$ is fully faithful when restricted to simplicial sets of dimension $\leq 1$. It will therefore suffice to show that is essentially surjective. Let $G$ be any directed graph, and form a pushout diagram of simplicial sets

\[ \xymatrix { \underset { e \in \operatorname{Edge}( G )}{\coprod } \operatorname{\partial \Delta }^{1} \ar [r] \ar [d]^{s,t} & \underset { e \in \operatorname{Edge}( G)}{\coprod } \Delta ^{1} \ar [d] \\ \underset { v \in \operatorname{Vert}( G )}{\coprod } \ar [r] & X_{\bullet }. } \]

Then $X_{\bullet }$ is a simplicial set of dimension $\leq 1$, and the directed graph $G( X_{\bullet } )$ is isomorphic to $G$. $\square$

Remark 1.1.4.10. The proof of Proposition 1.1.4.9 gives an explicit description of the inverse equivalence $\operatorname{Graph}\simeq \operatorname{\mathcal{C}}\hookrightarrow \operatorname{Set_{\Delta }}$: it carries a directed graph $G$ to the $1$-dimensional simplicial set given by the pushout

\[ ( \underset { v \in \operatorname{Vert}( G )}{\coprod } ) \amalg _{ \underset { e \in \operatorname{Edge}( G )}{\coprod } \operatorname{\partial \Delta }^{1} } ( \underset { e \in \operatorname{Edge}( G)}{\coprod } \Delta ^{1} ). \]