A Model of Directed Graph Cofiber

Abstract

In the homotopy theory of spaces, the image of a continuous map is contractible to a point in its cofiber. This property does not apply when we discretize spaces and continuous maps to directed graphs and their morphisms. In this paper, we give a construction of a cofiber of a directed graph map whose image is contractible in the cofiber. Our work reveals that a category-theoretically correct construction in continuous setup is no longer correct when it is discretized and hence leads to look at canonical constructions in category theory in a different perspective.

1. Introduction

Directed graphs are everywhere. They are fundamental mathematical objects not only for mathematical interests but also for applications including electric circuits, neural networks, social relationships, etc. [1,2]. Naturally classifying directed graphs through algebraic invariants is an important problem, and there have been various attempts (see [3] and references therein). Among them, a recent development of path-space homology and cohomology for directed graphs by Grigor’yan, Lin, Muranov, and Yau [3,4,5] is of particular interest. Their constructions are not too trivial, not too hard to compute, can be non-trivial for degrees greater than one, and satisfy similar properties to those invariants in the continuous and smooth setup. It turns out that path-space homology satisfies discrete analogs of Eilenberg–Steenrod axioms [6], i.e., the Künneth formula [7]; it is generalized to multigraphs and quivers [8] and has applications to discretizing Morse theory [9].

An interesting result regarding the path space homology is that it satisfies homotopy invariance. The history of homotopy theory for directed graphs goes back to [10,11] and more recently to [12]. In 2014, Grigor’yan, Lin, Muranov, and Yau [13] considered digraph homotopy as a notion of a discrete analog of homotopy in topology and proved that their path-space homology is invariant under this version of homotopy. Indeed, their homotopy theory for directed graphs is a natural “discretization” that is leading to establishing a dictionary between homotopy theory of spaces and its discrete counterpart. For example, several theorems in classical homotopy theory, such as van Kampen theorem, Hurewicz theorem, and Brown representability theorem [14,15], are successfully discretized (see [13,16]), and model structures in the category of directed graphs and related questions are currently being investigated [17].

From the perspective of homotopy theory and category theory, the homotopy theory for directed graphs is an interesting source to understand existing classical results. Any time a classical construction or theory fails to be discretized or satisfy expected properties, the failure itself or remedies to it reveal the essence of the classical theory. For example, the path-space homology satisfies all discrete analogs of Eilenberg–Steenrod axioms, but these axioms are not complete (see [6]), and we note that the completeness of Eilenberg–Steenrod axioms has a topological nature in it. Another example is a failure of homotopy extension property for directed graphs [16], which reveals that the Brown representability theorem for not-necessarily-finite CW complexes is likely to be a special feature of CW complexes rather than a consequence of generalities in category theory.

In [16], the authors have proven Brown representability theorem for finite directed graphs by adopting the methodology of J. F. Adams [18]. The gist of technical innovation was the use of digraph cofibers and mapping tubes (see [16] (Definitions 2.21 and 2.25)). It means that a natural discretization of Adams’ proof itself does not yield Brown representability theorem, but by appropriately modifying category-theoretic and homotopy-theoretic constructions, one can obtain this result. Accordingly, searching for constructions in directed graphs that satisfy general homotopy-theoretic properties lies at the technical core of discretizing classical results.

This paper is a brief note on a possible construction of a cofiber of directed graph map satisfying the property that the image of the directed graph map can be homotoped to a point. A cofiber of continuous map in the category of spaces satisfies this property in an obvious manner. However, in the category of directed graphs, any time there is an edge from a vertex in the range of the directed graph map to a vertex outside, it prevents defining a directed graph homotopy. We have constructed a model of cofiber that is free from such issues.

This paper is organized as follows. Section 2 collects preliminaries to work in the category of directed graphs. Section 3 and Section 4 review necessary operations in the category of directed graphs and homotopy theory for directed graphs. In Section 5, we give a construction of a directed graph cofiber proposed above and prove that it satisfies the desired property.

2. The Category of Directed Graphs

In this section, we shall review basic definitions and notations comprising the category of directed graphs.

Definition 1

([13]). A directed graph (or digraph for short) $\overrightarrow{G}$ is a pair $(V,E)$ consisting of a set of vertices V and a set E of ordered pairs of distinct vertices in V called edges.

Note that our digraphs do not allow loop-edges or multiple edges with the same source and target. A point is a digraph $(V,E)$ with V a singleton and E an empty set.

Definition 2.

Let $n\in {\mathbb{Z}}^{+}$. Ann-step line digraphis a digraph consisting of vertices labeled by 0, 1, ⋯, n and exactly one edge at every two consecutive vertices, i.e., either $(i-1,i)$ or $(i,i-1)$ for all $i\in {\mathbb{Z}}^{+}$ such that $1\le i\le n$.

An n-step line digraph is also called a path digraph or a linear digraph. When $n=1$, there are two possible line digraphs, $I^{+}:=0\to 1$ and $I^{-}:=0\leftarrow 1$.

Notation 1.

We will denote by $I_n$ an arbitrary n-step line digraph and by ${\mathcal{I}}_n$ the totality of all possible n-step line digraphs. The set of all line digraphs of any length will be denoted by $\mathcal{I}={\bigcup }_n{\mathcal{I}}_n$.

Definition 3.

Adigraph map, $f:\overrightarrow{G}\to \overrightarrow{H}$, is a function from the vertex set of $\overrightarrow{G}$ to the vertex set of $\overrightarrow{H}$ such that whenever $(x,y)$ is an edge in $\overrightarrow{G}$ either $f\left(x\right)=f\left(y\right)$ in $\overrightarrow{H}$ or $(f\left(x\right),f\left(y\right))$ is an edge in $\overrightarrow{H}$.

Definition 4.

Theimage digraph$Im\left(f\right)$ of a digraph map $f:\overrightarrow{G}\to \overrightarrow{H}$ is a directed graph consisting of a vertex set $f\left(V_{\overrightarrow{G}}\right)$ and an edge set $E_{\overrightarrow{G}}=\{(f\left(x\right),f\left(y\right)):x,y\in V_{\overrightarrow{G}},f\left(x\right)\ne f\left(y\right),and(x,y)\in E_{\overrightarrow{G}}\}$.

Definition 5.

Thecategory of directed graphs$\mathcal{D}$ is a category in which the objects are directed graphs, $\overrightarrow{G}$, and the morphisms are digraph maps, $f:\overrightarrow{G}\to \overrightarrow{H}$.

3. Operations in Directed Graphs

In this section, we review operations in directed graphs. The definition of an identification digraph is central in yielding homotopy-theoretic constructions in the category of directed graphs.

Definition 6.

Asub-digraph$\overrightarrow{X}$ of a digraph $\overrightarrow{G}$ denoted $\overrightarrow{X}\subset \overrightarrow{G}$ is a digraph for which $V_{\overrightarrow{X}}\subset V_{\overrightarrow{G}}$ and $E_{\overrightarrow{X}}\subset E_{\overrightarrow{G}}$.

Note that even if $u,v\in V_{\overrightarrow{X}}$ and $(u,v)\in E_{\overrightarrow{G}}$, it is not necessarily the case that $(u,v)\in E_{\overrightarrow{X}}$.

Definition 7.

Aninduced sub-digraph$\overrightarrow{X}$ of a digraph $\overrightarrow{G}$ denoted $\overrightarrow{X}⊏\overrightarrow{G}$ is a sub-digraph in which whenever $u,v\in V_{\overrightarrow{X}}$ and $(u,v)\in E_{\overrightarrow{G}}$, then $(u,v)\in E_{\overrightarrow{X}}$ as well.

Definition 8.

Thevertex boundary of a sub-digraph $\overrightarrow{X}\subset \overrightarrow{G}$ is

$$\partial \overrightarrow{X}:=\{g\in V_{\overrightarrow{G}}\backslash V_{\overrightarrow{X}}|\mathit{either}(g,x)\in E_{\overrightarrow{G}}\mathit{or}(x,g)\in E_{\overrightarrow{G}},\mathit{where}x\in V_{\overrightarrow{X}}\}.$$

Definition 9.

Theintersection of digraphs $\overrightarrow{G}$ and $\overrightarrow{H}$, denoted by $\overrightarrow{G}\cap \overrightarrow{H}$, is the digraph consisting of $V_{\overrightarrow{G}\cap \overrightarrow{H}}=V_{\overrightarrow{G}}\cap V_{\overrightarrow{H}}$ and $E_{\overrightarrow{G}\cap \overrightarrow{H}}=E_{\overrightarrow{G}}\cap E_{\overrightarrow{H}}$.

Definition 10.

Theunion of digraphs $\overrightarrow{G}$ and $\overrightarrow{H}$, denoted by $\overrightarrow{G}\cup \overrightarrow{H}$, is the digraph consisting of $V_{\overrightarrow{G}\cup \overrightarrow{H}}=V_{\overrightarrow{G}}\cup V_{\overrightarrow{H}}$ and $E_{\overrightarrow{G}\cup \overrightarrow{H}}=E_{\overrightarrow{G}}\cup E_{\overrightarrow{H}}$.

Definition 11.

Thedisjoint union of two digraphs $\overrightarrow{G}$ and $\overrightarrow{H}$, denoted $\overrightarrow{G}\coprod \overrightarrow{H}$ is given by the disjoint union of their respective vertex sets and edge sets, as sets.

Definition 12.

Thegraph Cartesian product □ of two directed graphs $\overrightarrow{G}$ and $\overrightarrow{H}$ is a directed graph $\overrightarrow{G}\square \overrightarrow{H}$, where the vertices are all ordered pairs $(u,v)$ such that $u\in V_{\overrightarrow{G}}$ and $v\in V_{\overrightarrow{H}}$, and $(u_1,v_1)\to (u_2,v_2)$ is an edge in $\overrightarrow{G}\square \overrightarrow{H}$ if either $u_1=u_2$ and $v_1\to v_2$ in $\overrightarrow{H}$, or $u_1\to u_2$ in $\overrightarrow{G}$ and $v_1=v_2$.

Remark 1.

Given a fixed vertex $v_0\in V_{\overrightarrow{H}}$, we will denote by $\overrightarrow{G}\square \left\{v_0\right\}$ the $v_0$-slice of $\overrightarrow{G}\square \overrightarrow{H}$. It is the induced sub-digraph where the vertices are all ordered pairs $(u,v_0)$ such that $u\in V_{\overrightarrow{G}}$ and the edges are those resulting from the edges of $\overrightarrow{G}$.

Definition 13.

Let $\overrightarrow{G}$ and $\overrightarrow{H}$ be digraphs and ∼ an equivalence relation on vertex sets of $\overrightarrow{G}$ and $\overrightarrow{H}$ such that whenever $(g_1,g_2)\in E_{\overrightarrow{G}}$, $g_1\sim h_1$, and $g_2\sim h_2$, then either $h_1=h_2$ or $(h_1,h_2)\in E_{\overrightarrow{H}}$. Theidentification digraph resulting from the relation ∼ is a digraph $\overrightarrow{G}\coprod \overrightarrow{H}/\sim$ whose vertices are equivalence classes and whose edges are the edges between the representatives of the classes.

Definition 14.

Aquotient digraph$\overrightarrow{G}/\overrightarrow{X}$, for $\overrightarrow{X}\subset \overrightarrow{G}$ and $\overrightarrow{X}$ not necessarily connected, is an identification digraph $\overrightarrow{G}\coprod \ast /\sim$ where $x\sim \ast$ for all $x\in V_{\overrightarrow{X}}$.

4. Homotopy for Digraphs

In this section, we review the notion of homotopy a là Grigor’yan, Lin, Muranov, and Yau [13].

Definition 15.

Two digraph maps $f,g:\overrightarrow{G}\to \overrightarrow{H}$ arehomotopic, denoted $f\simeq g$, if there exists an $n\ge 1$ and a digraph map $F:\overrightarrow{G}\square I_n\to \overrightarrow{H}$, for some line digraph $I_n\in {\mathcal{I}}_n$ (recall Notation 1), such that $F{\mid }_{\overrightarrow{G}\times \left\{0\right\}}=f$ and $F{\mid }_{\overrightarrow{G}\times \left\{n\right\}}=g$.

Definition 16.

Two digraphs are said to behomotopically equivalent (or to be of the same homotopy type) if there exist two digraph maps, $g:\overrightarrow{G}\to \overrightarrow{H}$ and $h:\overrightarrow{H}\to \overrightarrow{G}$, such that $h\circ g\simeq {id}_{\overrightarrow{G}}$ and $g\circ h\simeq {id}_{\overrightarrow{H}}$.

Example 1.

Let $f:\overrightarrow{G}\to \overrightarrow{H}$ be a digraph map. The mapping cylinder ${\overrightarrow{M}}_f$ and the digraph $\overrightarrow{H}$ are homotopically equivalent. This can be shown by taking a homotopy $F:{\overrightarrow{M}}_f\square I^{-}\to {\overrightarrow{M}}_f$ defined by $F(-,0)={id}_{{\overrightarrow{M}}_f}$, $F\left(\right(g,0),1)=\left(f\right(g),1)$ for all $g\in V_{\overrightarrow{G}}$ and $F\left(\right(h,1),1)=(h,1)$ for all $h\in V_{\overrightarrow{H}}$.

Definition 17.

A digraph $\overrightarrow{G}$ is said to becontractible if there exists a homotopy between ${id}_{\overrightarrow{G}}$ and a constant digraph map.

Definition 18.

Thehomotopy category of directed graphs , denoted $\mathrm{Ho}\mathcal{D}$, is a category in which the objects are directed graphs and the morphisms are equivalence classes of digraph maps where $f\simeq g$ whenever f and g are homotopic.

5. Main Construction

In this section, we give a construction of a digraph cofiber satisfying the property that the image of a digraph map is contractible in the digraph cofiber. To this end, we set up extensions of a mapping cylinder and a cone that enables lifting edges. The main outcome in this paper is Construction 1, from which Theorem 1 follows.

Definition 19.

Themapping cylinder of a digraph map$f:\overrightarrow{G}\to \overrightarrow{H}$ is given by

$${\overrightarrow{M}}_f:=[\overrightarrow{G}\square I^{-}\coprod \overrightarrow{H}]/\sim ,$$

where $(g,0)\sim f\left(g\right)$ for all $g\in V_{\overrightarrow{G}}$.

Definition 20.

Anextension of a mapping cylinder ${\overrightarrow{M}}_f$ for a digraph map $f:\overrightarrow{G}\to \overrightarrow{H}$ is the digraph ${\overrightarrow{E}}_f=(V_{{\overrightarrow{E}}_f},E_{{\overrightarrow{E}}_f})$ where,

$$V_{{\overrightarrow{E}}_f}=V_{\overrightarrow{G}}\coprod V_{\overrightarrow{H}},$$

and $(u,v)$ is an edge in $E_{{\overrightarrow{E}}_f}$ if $(u,f\left(v\right))\in E_{\overrightarrow{H}}$ for some $u\in V_{\overrightarrow{H}}$ and $v\in V_{\overrightarrow{G}}$ or in the opposite direction $(v,u)$ is an edge if $(f\left(v\right),u)\in E_{\overrightarrow{H}}$ for some $u\in V_{\overrightarrow{H}}$ and $v\in V_{\overrightarrow{G}}$.

Definition 21.

Anextended mapping cylinder for a digraph map $f:\overrightarrow{G}\to \overrightarrow{H}$ is given by the digraph ${\overrightarrow{EM}}_f={\overrightarrow{M}}_f\cup {\overrightarrow{E}}_f$.

Definition 22.

Thecone$C\overrightarrow{G}$ over a digraph $\overrightarrow{G}$ is the digraph $[\overrightarrow{G}\square I^{-}]/$∼, where $(g,0)\sim \ast$ for all $g\in V_{\overrightarrow{G}}.$

Definition 23.

Anextension of a cone over a sub-digraph $\overrightarrow{X}\subset \overrightarrow{H}$ is the digraph ${\overrightarrow{B}}_{\overrightarrow{X}}=(V_{{\overrightarrow{B}}_{\overrightarrow{X}}},E_{{\overrightarrow{B}}_{\overrightarrow{X}}})$ where $V_{{\overrightarrow{B}}_{\overrightarrow{X}}}=\partial \overrightarrow{X}\cup \left\{p\right\}$, p is the cone point, and $(p,y)\in E_{{\overrightarrow{B}}_{\overrightarrow{X}}}$ if and only if $(x,y)\in E_{\overrightarrow{H}}$ for some $x\in \overrightarrow{X}$ and $y\in \partial \overrightarrow{X}$ or $(y,p)\in E_{{\overrightarrow{B}}_{\overrightarrow{X}}}$ if and only if $(y,x)\in E_{\overrightarrow{H}}$ for some $x\in \overrightarrow{X}$ and $y\in \partial \overrightarrow{X}$.

Definition 24.

Anextended cone over the sub-digraph $\overrightarrow{X}$ in $\overrightarrow{H}$ is $C\overrightarrow{X}\cup {\overrightarrow{B}}_{\overrightarrow{X}}$.

Construction 1.

Thedigraph cofiber$\overrightarrow{C}\left(f\right)$ for a map $f:\overrightarrow{G}\to \overrightarrow{H}$ is an extension of a cone over $\overrightarrow{G}\coprod Im\left(f\right)$ (viewed as an induced subdigraph of ${\overrightarrow{M}}_f$) unioned with the identification digraph $\overrightarrow{G}\square I^{+}\coprod \overrightarrow{H}/\sim$ where $(g,0)\sim f\left(g\right)$ and the extension of this reversed mapping cylinder (See Figure 1).

Remark 2.

The resulting structure in the above definition is a “two-step extended cone” with a middle slice that preserves a copy of $\overrightarrow{G}$. It should be noted that $\overrightarrow{C}\left(f\right)$ is not a category-theoretic cofiber. However, from the perspective of homotopy theory for digraphs, category-theoretic cofibers do not carry much meaning. Specifically, for a digraph map $f:\overrightarrow{G}\to \overrightarrow{H}$, note that its category-theoretic cofiber is a pushout of the following diagram in the category $\mathcal{D}$.

$$\begin{array}{ccc}\overrightarrow{G}& \stackrel{j_1}{\to }& {\overrightarrow{M}}_f\\ \downarrow & j_2\hfill & \\ •& & \end{array}$$

where • is a point, $j_1$ the inclusion, and $j_2$ the constant map. Not only does the pushout not have a slice of $\overrightarrow{G}$ in it, and as mentioned in Section 1, but one cannot homotope $\mathrm{Im}\left(f\right)$ to the vertex of the cone. To further develop homotopy theory for digraphs, we have to construct a cofiber that retains essential properties of a cofiber of continuous map, and from the construction above, one can see that our construction retains a copy of the domain digraph $\overrightarrow{G}$. We claim that $\mathrm{Im}\left(f\right)$ can be homotoped to the cone vertex as stated below.

Theorem 1.

Suppose $f:\overrightarrow{G}\to \overrightarrow{H}$ is a map of digraphs. Consider the sequence $\overrightarrow{G}\stackrel{f}{\to }\overrightarrow{H}\stackrel{i}{\to }\overrightarrow{C}\left(f\right)$ where the map i is the inclusion. Then the composition $i\circ f$ is homotopically trivial.

Proof. 

We have to prove that the subdigraph $\mathrm{Im}\left(f\right)$ is contractible in $\overrightarrow{C}\left(f\right)$. By construction of $\overrightarrow{C}\left(f\right)$, we define a homotopy $F_1:\overrightarrow{C}\left(f\right)\square I^{+}\to \overrightarrow{C}\left(f\right)$ that takes every $f\left(g\right)\in \mathrm{Im}\left(f\right)$ for $g\in V_{\overrightarrow{G}}$ to $(g,1)$ in the $\overrightarrow{G}\square \left\{1\right\}$-slice in $\overrightarrow{G}\square I^{+}\coprod \overrightarrow{H}/$∼ and then $F_2:\overrightarrow{C}\left(f\right)\square I^{+}\to \overrightarrow{C}\left(f\right)$ that takes this slice to the cone vertex. The existence of digraph maps $F_1$ and $F_2$ is guaranteed by Definition 23. □

6. Discussion

In this article, we have constructed a model of a cofiber of a digraph map. A cofiber of a continuous map in the category of spaces loses homotopy-theoretically essential properties after being discretized to a category-theoretic cofiber in the category of digraphs. Our construction retains those essential properties, as seen in Section 5. In addition, our work reveals that a universal construction in category theory is not necessarily a homotopy-theoretically correct construction when we consider a category consisting of discrete objects. Therefore, further research in this category will provide interesting perspectives for category theory.