# The Cellular Homology of Digraphs

Xinxing Tang and Shing-Tung Yau  X. Tang: Beijing Institute of Mathematical
Sciences and Applications, Beijing, China<EMAIL_ADDRESS>S.-T. Yau:
Yau Mathematical Sciences Center, Tsinghua University, and Beijing Institute
of Mathematical Sciences and Applications, Beijing, China;
<EMAIL_ADDRESS>
###### Abstract.

In [17], we consider the minimal paths in the path complex associated to a
digraph $G$ under the strongly regular condition. In this paper, first, based
on our new definitions of admissible pair and admissible relations among the
set of minimal paths, we will give the definitions of cellular chain complex
associated to $G$ and prove the well-definedness. Then we will study several
properties of such cellular homologies. Finally, we give several interesting
examples as well as some important observations.

###### Contents

  1. 1 Introduction
    1. 1.1 Main results
    2. 1.2 Organization
  2. 2 Path Complex and Minimal Path
    1. 2.1 Path complex
    2. 2.2 Minimal path
  3. 3 The Cellular Homology of Digraphs
    1. 3.1 The singular cubical complex of digraphs
    2. 3.2 Admissible pair and admissible relations
      1. 3.2.1 Admissible pair
      2. 3.2.2 Admissible relations
      3. 3.2.3 CW complex of the digraph
    3. 3.3 Cellular homology of a digraph
    4. 3.4 Properties of cellular homology associated to the digraph
      1. 3.4.1 Homotopy invariance
      2. 3.4.2 Acyclic result for $\widetilde{H}^{\operatorname{cell}}_{*}(\operatorname{Supp}(P);\mathbb{R})$ for $P\in\mathcal{P}_{\operatorname{adm}}(G)$
      3. 3.4.3 Künneth formula
  4. 4 More Examples
    1. 4.1 The circulant graph
    2. 4.2 The Johnson digraph
  5. 5 Discussion and Outlook
    1. 5.1 The digraphs from geometry
    2. 5.2 The relation to singular cubical homology
      1. 5.2.1 Example 3.30 revisited
      2. 5.2.2 Example 3.21 and Example 3.22 revisited
      3. 5.2.3 Example 3.15 revisited
  6. A Appendix. The admissible minimal $3$-paths

##  1\. Introduction

Since 2012, Grigoryan, Lin, Muranov and Yau develop a homotopy-homology
approach to digraphs and initiate several study of the relationship between
discrete topology (where the discrete topology is played by objects of various
categories of digraphs or graphs) and continuous topology, which is now known
as GLMY-theory. Compared with other previously studied notions of graph
homologies (e.g. via cliques [2], or via Hochschild (co)homology [14]), it
owns many nice properties ([3, 7, 8, 9, 10, 11]):

  1. (1)

It “generalises” the homology of simplicial complex.

  2. (2)

It satisfies the properties that are analogous to Eilenberg-Steenrod axioms.

  3. (3)

It is well linked to graph-theoretical operations:

     * •

it respects the digraph suspension;

     * •

the Künneth formula holds for both Cartesian product of two digraphs and join
of two digraphs.

  4. (4)

There is an appropriate notion of fundamental group and covering digraphs.

  5. (5)

There is a dual cohomology theory of digraphs which coincides with the one
developed by Dimakis and Müller-Hoissen in [4, 5] as a reduction of the
“universal differential algebra”.

In [17], we study the structure of (a sub-complex of) path complex of a
digraph $G$. More explicitly, we focus on the $\mathbb{Z}$-coefficient
generators of the chain complex under the strongly regular condition (that is,
we require each elementary path to have distinct vertices), study the so-
called minimal path $P$ (see, Definition 2.4) and its supporting digraph
$\operatorname{Supp}(P)$(see, Definition 2.5).

######  Question 1.1.

Why do we consider the strongly regular condition (non-repeatedness
requirement for elementary path)?

On the one hand, given a finite simple digraph $G$, the original regular
condition allows the path of the form

$e_{i_{0}i_{1}\cdots i_{n}},\quad i_{j}\neq i_{j+1},~{}j=0,1,\ldots,n-1.$

Under such a condition, the path complex may be infinite. See, the circulant
digraph $C_{5}^{1,2}$ in Subsection 4.1, for an example. The non-repeatedness
requirement cuts the complex to be of finite length and maybe even make it
more proper. Thus, the strongly regular condition could be understood as some
kind of finite condition for the path complex.

On the other hand, it is based on some topological/geometric consideration. We
hope the minimal $n$-path $P$ and its supporting digraph
$\operatorname{Supp}(P)$ could play the role of the regular $n$-cell in the
topological space. To push forward this idea, we study many examples and
analyze the structure of $P$ and $\operatorname{Supp}(P)$ in [17]. The key
results in [17] are the structure theorem (see, Theorem 2.10) and acyclic
result for $\widetilde{H}_{*}(\operatorname{Supp}(P))$. Immediately, we obtain
several applications based on the standard acyclic model theorem.

However, it is worth to mention that we also have the following observations:

  * •

For any integer $n\geq 3$, there are infinitely many kinds of minimal
$n$-paths.

  * •

The digraph $\operatorname{Supp}(P)$ may not be contractible, see, Example
3.15 (the exotic cube) or Example 2.8. More explicitly, for each $n\geq 3$,
only finite kinds of $\operatorname{Supp}(P)$ are contractible. The
contractibility will disappear with the elementary path components of minimal
path $P$ increasing, correspondingly, the supporting digraph
$\operatorname{Supp}(P)$ will become “fat”.

The contractibility is quite an important property in the further construction
within the topological space $X$. For example, the fiber bundle is trivial
over the contractible space. Thus, to build the relation between digraph and
topological space as much as possible, in this paper, we will study the
minimal path with one more additional condition and study the
$\operatorname{CW}$ complex and cellular homology of the digraph $G$.

###  1.1. Main results

The key results in this paper are as follows.

(1) By introducing the admissible conditions among the set of minimal paths,
we give the definition of the cellular chain complex of digraphs and prove the
well-definedness.

######  Definition 1.2 (Definition 3.8, 3.20).

Let $G$ be a digraph and $P$ be a minimal $n$-path. The pair
$(P,\operatorname{Supp}(P))$ is called admissible, if there exists a digraph
map

$f:I^{\boxdot n}\longrightarrow G$

such that

  * •

$f_{*}(\omega_{n})=cP$, for some $c\in\mathbb{Z}\setminus\\{0\\};$

  * •

the image digraph of $f$ is $\operatorname{Supp}(P)$.

The linear relations among the admissible paths are called the admissible
relations.

######  Definition 1.3 (Definition 3.26).

Let $\mathcal{P}_{\operatorname{adm},n}(G)$ be the set of length-$n$
admissible pairs (up to a sign) in $G$. We define the $n$-th cellular chain of
$G$ to be

$C_{n}(G;\mathbb{R})=\left\\{\sum_{P\in\mathcal{P}_{\operatorname{adm},n}}c_{P}P~{}\bigg{|}~{}c_{P}\in\mathbb{R}\right\\}\bigg{/}\left\\{\text{admissible
relations}\right\\}.$

Moreover, we define a linear operator
$\partial^{\operatorname{cell}}:C_{n}(G;\mathbb{R})\longrightarrow
C_{n-1}(G;\mathbb{R})$. For any $P\in\mathcal{P}_{\operatorname{adm},n}$,

$\partial^{\operatorname{cell}}P=\sum_{Q\in\mathcal{P}_{\operatorname{adm},n-1}(G)}[Q:P]Q,$

where the coefficient $[Q:P]$ is defined as follows:

$[Q:P]=\left\\{\begin{array}[]{ll}1,&\hbox{if $Q<\partial P$;}\\\ -1,&\hbox{if
$-Q<\partial P$;}\\\ 0,&\hbox{otherwise.}\end{array}\right.$

Via the careful and non-trivial analysis of the relation between
$\partial^{\operatorname{cell}}$ in the cellular complex and $\partial$ in the
path complex, we understand the operator $\partial^{\operatorname{cell}}$ is a
well-defined boundary operator. Moreover, we arrive at the definition of the
cellular homology of $G$, which are denoted by
$H^{\operatorname{cell}}_{*}(G;\mathbb{R})$.

Our construction is related to the singular cubical homology (which is
recalled in Subsection 3.1). We discuss several similarities between our
cellular homologies of a digraph and singular cubical homologies of a digraph
[7] and propose the following conjecture:

######  Conjecture 1.4 (Conjecture 5.3).

If the digraph $G$ does not contain a monotone cycle, then

$H_{*}^{\operatorname{cell}}(G;\mathbb{R})\cong H_{*}^{c}(G;\mathbb{R}).$

In particular, the admissible relations among the admissible pairs are the
boundary conditions in the singular cubical homology.

(2) We prove several properties of the cellular homologies associated to
digraphs.

  * •

Homotopy invariance (in a narrow case).

  * •

Acyclic result for
$\widetilde{H}^{\operatorname{cell}}_{*}(\operatorname{Supp}(P);\mathbb{R})$
for $P\in\mathcal{P}_{\operatorname{adm}}(G)$.

  * •

Künneth formula for Cartesian product of two digraphs.

In particular, after checking the contractibility of all the admissible
minimal $3$-paths (up to global orientation of edges) in Appendix A, we also
propose the following conjecture.

######  Conjecture 1.5 (Conjecture 3.43).

Let $P\in\mathcal{P}_{\operatorname{adm}}(G)$, then $\operatorname{Supp}(P)$
is contractible.

###  1.2. Organization

In Section 3.40, we recall the necessary definitions and results in [17]. In
Section 3, we start our construction of $\operatorname{CW}$ complex and
cellular chain group of a digraph $G$. In Subsection 3.1, we recall the
singular cubical complex of a digraph in [7] and their relation with path
complex. In Subsection 3.2, we introduce the restricted definitions among the
set of minimal paths, which we call admissible paths and admissible relations.
Various examples will be given there to understand the difference from the
original definitions of minimal path. In Subsection 3.3, we define the
cellular homology of a digraph and do some simple computations. In subsection
3.4, we analyze several properties of such cellular homology. In Section 4, we
compute the cellular homologies of several interesting digraphs, such as
special circulant digraphs and Johnson digraphs. In Section 5, we continue our
discussion and obtain several important observations. In Appendix A, we
enumerate all the admissible minimal $3$-paths up to global orientation of
edges and the corresponding deformation retractions.

Acknowledgments. The authors thank Xin Fu, Yuri Muranov and Fedor Pavutnitskiy
for useful discussions. The work of X.T. is partially supported by research
funding at BIMSA.

##  2\. Path Complex and Minimal Path

In [17], we analyze the structure of $\mathbb{Z}$-coefficient path complex
$\Omega_{*}(G;\mathbb{Z})$ of a digraph $G$ via the so-called minimal path $P$
and the corresponding supporting digraph $\operatorname{Supp}(P)$. In this
section, we will recall necessary results on the path complex and the
corresponding $\mathbb{Z}$-structure.

###  2.1. Path complex

Let $V$ be a finite set. For any $n\in\mathbb{N}$, an elementary $n$-path is
any ordered sequence $i_{0},\ldots,i_{n}$ of $n+1$ vertices of $V$, write it
as $e_{i_{0}\ldots i_{n}}$. Let $\Lambda_{n}(V;\mathbb{Z})$ be the
$\mathbb{Z}$-module generated by all elementary $n$-paths. We also call $n$
the length of the path in $\Lambda_{n}(V;\mathbb{Z})$.

The $\mathbb{Z}$-homomorphism
$\partial:\Lambda_{n}(V;\mathbb{Z})\rightarrow\Lambda_{n-1}(V;\mathbb{Z})$ is
defined via the generators:

$\partial e_{i_{0}\ldots
i_{n}}=\sum_{j=0}^{n}(-1)^{j}e_{i_{0}\ldots\widehat{i_{j}}\ldots i_{n}}.$

Clearly,
$\partial\left(\Lambda_{n}(V;\mathbb{Z})\right)\subset\Lambda_{n-1}(V;\mathbb{Z})$,
and $\partial^{2}=0$.

Now we will consider a sub-complex of $(\Lambda_{*}(V),\partial)$ which is
constrained by a digraph $G$. More explicitly, let $G=(V,E)$ be a finite
simple digraph111Here simple condition means that there are no multiple edges
and self loops. In this paper, a digraph means a finite simple digraph., where
$V$ is the set of vertices and $E$ is the set of directed edges. First, we
have the following definition.

######  Definition 2.1 ([HY]).

Let $G=(V,E)$ be a finite simple digraph.

  1. (1)

An elementary path $e_{i_{0}i_{1}\ldots i_{n}}$ is called allowed, if each
directed edge $i_{k-1}\rightarrow i_{k}$ belongs to $E$, $k=1,2\ldots,n$.

  2. (2)

An elementary path $e_{i_{0}i_{1}\ldots i_{n}}$ is called strongly regular
(abbreviated as s-regular), if $i_{0},i_{1},\ldots,i_{n}$ are all distinct.

Furthermore, we denote the set of s-regular allowed elementary $n$-paths in
$G$ by $E_{n}(G)$.

Let $\mathcal{A}_{n}(G;\mathbb{Z})$ be the free $\mathbb{Z}$-module generated
by the set $E_{n}(G)$. Note that, $\mathcal{A}_{n}(G;\mathbb{Z})=0$, if
$n\geq\big{|}V(G)\big{|}$.

If we take the boundary operator $\partial$ on the s-regular allowed
elementary path $e_{i_{0}\ldots i_{n}}$, in general, $\partial e_{i_{0}\ldots
i_{n}}$ may not be in $\mathcal{A}_{n-1}(G;\mathbb{Z})$. Then furthermore, we
consider the submodule $\Omega_{n}(G;\mathbb{Z})$ of $\partial$-invariant
s-regular allowed $n$-paths. That is

$\Omega_{n}(G;\mathbb{Z})=\\{p\in\mathcal{A}_{n}(G;\mathbb{Z})|\partial
p\in\mathcal{A}_{n-1}(G;\mathbb{Z})\\}.$

######  Definition 2.2.

The complex $(\Omega_{*}(G;\mathbb{Z}),\partial)$ is called the path complex
of a digraph $G$ with $\mathbb{Z}$-coefficients. For each $n\geq 0$,

$H_{n}(G,\mathbb{Z}):=\frac{\ker(\partial:\Omega_{n}(G;\mathbb{Z})\rightarrow\Omega_{n-1}(G;\mathbb{Z}))}{\operatorname{im}(\partial:\Omega_{n+1}(G;\mathbb{Z})\rightarrow\Omega_{n}(G;\mathbb{Z}))},$

it is called the $n$-th path homology of $G$.

######  Remark 2.3 (general definition of regular condition).

The s-regular condition in Definition 2.1 is indeed stronger than the one in
[9]. In [9], the set of regular $n$-paths is defined as a quotient space
$\mathcal{R}_{n}(V)$:

$\mathcal{R}_{n}(V)=\Lambda_{n}(V)/I_{n}(V),$

where $I_{n}(V)$ is the submodule generated by the irregular path
$e_{i_{0}i_{1}\ldots i_{n}}$, that is, $i_{k-1}=i_{k}$ for some
$k=1,\ldots,n$. One can easily check that $(\mathcal{R}_{*}(V),\partial)$
forms a quotient chain complex with the induced boundary operator, we still
denote by $\partial$.

The authors of [9] consider the submodule
$\mathcal{A}_{n}(G)\subset\mathcal{R}_{n}(G)$ and $\partial$-invariant
submodule $\Omega_{n}(G)$, then give the definition of path complex of a
digraph $G$. We have,

  * •

The path complex in Definition 2.2 is a sub-complex of the original one. There
are many examples that both path homologies are isomorphic. In particular, if
there does not exist a monotone cycle in $G$, where the monotone cycle is of
the form

$v_{0}\rightarrow v_{1}\rightarrow v_{2}\rightarrow\cdots\rightarrow
v_{n}\rightarrow v_{0},$

then the s-regular condition is the same as the regular condition. It follows
that the corresponding homologies are the same.

  * •

However, there also exist counterexamples that the two kinds of path
homologies are not the same. Such an example could be found in Appendix A of
[17].

In what follows, for simplicity, we will focus on the definitions under the
s-regular condition.

###  2.2. Minimal path

For any $P=\sum_{p=1}^{m}c_{p}e_{p}\in\Omega_{n}(G;\mathbb{Z})$ with $e_{p}\in
E_{n}(G)$, we define

$w(P)=\sum_{p=1}^{m}|c_{p}|,$

and call it the width of the path $P$.

######  Definition 2.4.

Let $P=\sum_{p=1}^{m}c_{p}e_{p}\in\Omega_{n}(G;\mathbb{Z})$, if there exists

$P^{\prime}=\sum_{p=1}^{m}d_{p}e_{p}\in\Omega_{n}(G;\mathbb{Z})\setminus\\{0\\},$

satisfying

  1. (1)

$|c_{p}-d_{p}|\leq|c_{p}|$ and $|d_{p}|\leq|c_{p}|$ for each $p=1,\ldots,m$;

  2. (2)

$w(P^{\prime})<w(P)$;

then we call $P^{\prime}$ is smaller than $P$, and denote by $P^{\prime}<P$.
If there does not exist such $P^{\prime}$, we call $P$ a minimal $n$-path.

We have the following immediate observations on the minimal path:

  * •

If $P$ is minimal, $-P$ is also minimal.

  * •

If $P^{\prime}<P$, then $P-P^{\prime}\in\Omega_{n}(G;\mathbb{Z})$ is also
smaller than $P$.

  * •

Minimal $0$-path is just represented by a single point (up to a sign); minimal
$1$-path is just represented by $e_{ij}$ (up to a sign), $(i\rightarrow j)\in
E$.

  * •

Any element in $\Omega_{n}(G;\mathbb{Z})$ is a $\mathbb{Z}$-linear combination
of minimal paths.

  * •

Any minimal path is a $\mathbb{Z}$-linear combination of s-regular allowed
elementary paths with the same starting vertex (denote by $S$) and ending
vertex (denote by $E$).

The path complex, especially the minimal path, depends on the digraph. To
understand its structure, we introduce the following definitions.

######  Definition 2.5.

For each minimal path $P$ in the digraph $G$, we define
$\operatorname{Supp}(P)$ to be the minimal subgraph of $G$ such that
$P\in\Omega_{*}(\operatorname{Supp}(P))$.

One can obtain the sub-digraph $\operatorname{Supp}(P)$ as follows:

  1. (1)

First, we express $P$ uniquely in terms of the elementary paths, that is

$P=\sum_{p=1}^{n}c_{p}e_{p},\quad e_{p}\in
E_{n}(G;\mathbb{Z}),~{}c_{p}\in\mathbb{Z}\setminus\\{0\\}.$

Then we get a digraph $\operatorname{Supp}(P)^{\mbox{pre}}$ given by
$\\{e_{p}\\}_{p=1}^{m}$.

  2. (2)

Second, similarly, we express $\partial P$ uniquely in terms of the elementary
paths, that is

$\partial P=\sum_{q=1}^{m}d_{q}e_{q},\quad e_{q}\in
E_{n-1}(G;\mathbb{Z}),~{}d_{q}\in\mathbb{Z}\setminus\\{0\\}.$

Then we add necessary edges from $\\{e_{q}\\}_{q=1}^{m}$ to
$\operatorname{Supp}(P)^{\mbox{pre}}$ and obtain $\operatorname{Supp}(P)$.

For convenience, we also introduce two “distance functions” on $V(P)$. First,
for each s-regular allowed elementary path $e_{I}=e_{i_{0}i_{1}\ldots i_{n}}$,
we have the position function

$f_{I}:V(e_{I})~{}\longrightarrow~{}\mathbb{N},\quad f_{I}(i_{a})=a.$

Then, for a minimal $n$-path $P$ with starting vertex $S$ and ending vertex
$E$, we define

$\displaystyle d_{S}:V(P)\rightarrow\mathbb{N},\quad
d_{S}(v)=\min\\{f_{I}(v)|e_{I}\text{ is a component of }P\\};$ $\displaystyle
d_{E}:V(P)\rightarrow\mathbb{N},\quad d_{E}(v)=\min\\{n-f_{I}(v)|e_{I}\text{
is a component of }P\\}.$

One can understand $d_{S}$ and $d_{E}$ as the distance from $v$ to $S$ and $E$
in $P$ (not in $\operatorname{Supp}(P)$) respectively.

Now let us give several examples on the minimal paths and the corresponding
supporting digraphs as follows.

######  Example 2.6.

In the following 3-simplex digraph $G$, $P=e_{0123}$ is minimal, and its
supporting subdigraph is given by

$G=$
---
$0$
---
$1$
---
$2$
---
$3$
---
$\operatorname{Supp}(P)=$
---
$0$
---
$1$
---
$2$
---
$3$
---

By definition, we have

$\displaystyle d_{S}(0)=0,\quad d_{S}(1)=1,\quad d_{S}(2)=2,\quad d_{S}(3)=3;$
$\displaystyle d_{E}(0)=3,\quad d_{E}(1)=2,\quad d_{E}(2)=1,\quad d_{E}(3)=0.$

######  Example 2.7.

The minimal digraph which supports

$P=e_{0136}-e_{0156}+e_{0456}+e_{0246}-e_{0236}$

is given by

$0$
---
$1$
---
$2$
---
$3$
---
$4$
---
$5$
---
$\operatorname{Supp}(P)=$
---
$6$
---

By definition, we have

$\displaystyle
d_{S}(0)=0,~{}~{}d_{S}(1)=1,~{}~{}d_{S}(2)=1,~{}~{}d_{S}(3)=2,~{}~{}d_{S}(4)=1,~{}~{}d_{S}(5)=2,~{}~{}d_{S}(6)=3;$
$\displaystyle
d_{E}(0)=3,~{}~{}d_{E}(1)=2,~{}~{}d_{E}(2)=2,~{}~{}d_{E}(3)=1,~{}~{}d_{E}(4)=1,~{}~{}d_{E}(5)=1,~{}~{}d_{E}(6)=0.$

######  Example 2.8.

The minimal digraph which supports

$\displaystyle P=~{}$ $\displaystyle
e_{S06E}-e_{S16E}+e_{S17E}-e_{S27E}+e_{S28E}-e_{S38E}$
$\displaystyle+e_{S39E}-e_{S49E}+e_{S4(10)E}-e_{S5(10)E}.$

is given by

$S$
---
$0$
---
$1$
---
$2$
---
$3$
---
$4$
---
$5$
---
$6$
---
$7$
---
$8$
---
$9$
---
$10$
---
$E$
---

######  Example 2.9.

Let us consider the following path

$\displaystyle P=~{}$ $\displaystyle e_{S159E}-e_{S169E}+e_{S269E}$
$\displaystyle+e_{S16(10)E}-e_{S26(10)E}+e_{S27(10)E}-e_{S37(10)E}$
$\displaystyle-e_{S27(11)E}+e_{S37(11)E}-e_{S38(11)E}+e_{S48(11)E}.$

It could be a minimal $4$-path with the following supporting digraph

$1$
---
$2$
---
$3$
---
$4$
---
$5$
---
$6$
---
$7$
---
$8$
---
$9$
---
$10$
---
$11$
---
$E$
---
$S$
---
$\operatorname{Supp}(P)=$
---

We have the following structure theorem for $P$ and $\operatorname{Supp}(P)$.
The readers can understand it in terms of the above examples.

######  Theorem 2.10 ([17] Structure Theorem).

Let $P\in\Omega_{n}(G;\mathbb{Z})$ be a minimal path with the starting vertex
$S$ and ending vertex $E$, $\operatorname{Supp}(P)$ be its supporting digraph
and $d_{S}$, $d_{E}$ be the functions defined above.

(1) Let $S_{1}=d_{S}^{-1}(1)$ and $E_{1}=d_{E}^{-1}(1)$. Then $P$ is a linear
combination of s-regular allowed elementary paths from $S$ to $E$, with
coefficients being either 1 or -1. And in $\operatorname{Supp}(P)$,

$\displaystyle\partial P=\sum_{\alpha\in E_{1}}P_{S,n-1,\alpha}+\sum_{\beta\in
S_{1}}P_{\beta,n-1,E}+\sum_{k\in I_{P}}P_{S,n-1,E}^{k},$

where

  * •

$P_{S,n-1,\alpha},P_{\beta,n-1,E},P_{S,n-1,E}^{k}\in\Omega_{n-1}(\operatorname{Supp}(P);\mathbb{Z})$,
and moreover

    * –

$P_{S,n-1,\alpha}$ is the minimal $(n-1)$-path starting from $S$ and ending
with $\alpha$;

    * –

$P_{\beta,n-1,E}$ is the minimal $(n-1)$-path starting from $\beta$ and ending
with $E$;

    * –

$P_{S,n-1,E}^{k}$ is the minimal $(n-1)$-path starting from $S$ and ending
with $E$.

  * •

Such $P_{S,n-1,\alpha}$, $P_{\beta,n-1,E}$ are unique (up to a sign) in
$\operatorname{Supp}(P)$ for each $\alpha\in E_{1}$, $\beta\in S_{1}$.

  * •

The set $I_{P}$ in the last summand depends on $P$, and $|I_{P}|\leq 1$. That
is, there exists at most one (up to a sign) minimal $(n-1)$-path in
$\operatorname{Supp}(P)$ starting from $S$ and ending with $E$.

(2) For any $v\in d_{E}^{-1}(k)\cap\operatorname{Supp}(P)$, in
$\operatorname{Supp}(P)$,

  * •

There is only one minimal $(n-k)$-path (up to a sign) starting from $S$ and
ending with $v$, denoted by $P_{S,n-k,v}$, as well as only one minimal
$k$-path (up to a sign) starting from $v$ and ending with $E$, denoted by
$P_{v,k,E}$.

  * •

There is at most one minimal $(n-k-1)$-path (up to a sign) starting from $S$
and ending with $v$, denoted by $P_{S,n-k-1,v}$, as well as at most one
minimal $(k-1)$-path starting from $v$ and ending with $E$, denoted by
$P_{v,k-1,E}$.

(3) Each minimal $2$-path with fixed starting and ending vertices in
$\operatorname{Supp}(P)$ ($n\geq 2$) is unique.

In [17], we also prove the following acyclic result.

######  Theorem 2.11 ([17]).

Let $P$ be a minimal path of $G$. Then

$\widetilde{H}_{*}(\operatorname{Supp}(P))=0.$

We switch to the complex with field (characteristic 0) coefficient, for
example, $\mathbb{R}$, then the basis of $\Omega_{*}(G;\mathbb{R})$ consisting
of minimal paths gives the acyclic model of the path complex. Finally, we
discuss several canonical applications of such an acyclic model in the path
complex.

Meanwhile, we have the following two observations:

  * •

For any integer $n\geq 3$, there are infinitely many kinds of minimal
$n$-paths.

  * •

Even if $\widetilde{H}_{*}(\operatorname{Supp}(P))=0$, the digraph
$\operatorname{Supp}(P)$ may not be contractible. More explicitly, for each
$n\geq 3$, only finite kinds of $\operatorname{Supp}(P)$ are contractible. The
contractibility will disappear with the path components of minimal $P$
increasing, correspondingly, $\operatorname{Supp}(P)$ will become “fat”.

In the next section, we will consider a certain sub-complex of path complex,
which bring some additionally finite possibilities.

##  3\. The Cellular Homology of Digraphs

In this section, we will consider the $\operatorname{CW}$ complex associated
to a digraph by specifying certain pairs (which we call admissible pairs) of
minimal path and its supporting digraph. The admissible paths may be linearly
dependent as paths. Our definition of $\operatorname{CW}$ complex depends on
the choice of maximal linearly independent subset of admissible paths. While,
to avoid discussing the choice of basis, we define the cellular chain group of
the digraph to be the quotient of the free group of the so-called admissible
pairs by such linear relations (which we call admissible relations).

###  3.1. The singular cubical complex of digraphs

Our admissible requirement depends on certain kind of singular cubical
realization. Roughly speaking, the $\operatorname{CW}$ complex associated to
$G$ will also be explained as some kind of fusion of path complex and singular
cubical complex. Thus let us first recall the corresponding necessary
definitions and results for singular cubical complex of digraphs. For more
details, please refer to [7].

######  Definition 3.1 (Cartesian product of digraphs).

For two digraphs $G=(V(G),E(G))$ and $H=(V(H),E(H))$, we define the Cartesian
product $G\boxdot H$ as a digraph with the set of vertices $V(G)\times V(H)$
and with the set of edges as follows: for $v,v^{\prime}\in V(G)$ and
$w,w^{\prime}\in V(H)$, we have $(v,w)\rightarrow(v^{\prime},w^{\prime})$ in
$G\boxdot H$ if and only if

$\text{either $\\{v=v^{\prime},~{}w\rightarrow w^{\prime}\\}$, or
$\\{v\rightarrow v^{\prime},~{}w=w^{\prime}\\}$}.$

Let $I$ be the digraph $I=\\{0~{}\bullet~{}\longrightarrow~{}1~{}\bullet\\}$.
In the following discussion, for $n\in\mathbb{N}$, we will focus on the
$n$-cube

$I^{\boxdot n}=\underbrace{I\boxdot I\boxdot\cdots\boxdot I}_{n},~{}n\geq
1;\quad I^{\boxdot 0}=\\{0\\}.$

Where the vertices are represented by the binary sequence. Any of its
$(n-1)$-face is of the form

$I^{\boxdot k}\boxdot\\{\epsilon\\}\boxdot I^{\boxdot(n-1-k)},\quad 0\leq
k\leq n-1,~{}\epsilon=0,1.$

There are also natural inclusions $F_{j\epsilon}:I^{\boxdot(n-1)}\rightarrow
I^{\boxdot n}$, for $1\leq j\leq n$,

(3.1)
$F_{j\epsilon}(c_{1},\ldots,c_{n-1})=(c_{1},\ldots,c_{j-1},\epsilon,c_{j},\ldots,c_{n-1}),\quad
n\geq 2,$

and $F_{1\epsilon}(0)=\epsilon$ for $n=1$.

######  Definition 3.2 (Digraph map).

A morphism from a digraph $G=(V(G),E(G))$ to a digraph $H=(V(H),E(H))$ is a
map $f:V(G)\rightarrow V(H)$ such that for any edge $v\rightarrow w$ in $G$,
we have

$f(v)\rightarrow f(w)\quad\text{or}\quad f(v)=f(w)\text{ in }H.$

The requirement is also denoted by $f(v)\overset{\rightarrow}{=}f(w)$. We also
call such a morphism to be a digraph map, and denote by $f:G\rightarrow H$.

A singular $n$-cube in a digraph $G$ is a digraph map $\phi:I^{\boxdot
n}\rightarrow G$. Of course, the singular $n$-cubes could be degenerate
enough, since $I^{\boxdot n}$ maps to any single point, leading to a singular
$n$-cube. Such a map captures less information of a digraph $G$. To obtain the
more explicit information of a digraph via the singular cube, we want to
module the degenerate singular cubes, which are defined as follows.

For $n\geq 1$ and $1\leq j\leq n$, consider the natural projection
$T^{j}:I^{\boxdot n}\rightarrow I^{\boxdot(n-1)}$: For $n=1$,

$T^{1}(0)=0,\quad T^{1}(1)=0.$

For $n\geq 2$,

$T^{j}(i_{1},\ldots,i_{n})=(i_{1},\ldots,i_{j-1},i_{j+1},\ldots,i_{n}).$

######  Definition 3.3 ([7]).

We call the singular $n$-cube $\phi:I^{\boxdot n}\rightarrow G$ degenerate if
there exist $j\in\\{1,2,\ldots,n\\}$ and a singular $(n-1)$-cube
$\psi:I^{\boxdot(n-1)}\rightarrow G$, such that

$\phi=\psi\circ T^{j}.$

For $n\geq 0$, we denote by $Q_{n}(G)$ the free module generated by the
singular $n$-cubes. And for $n\geq 1$, we denote by $B_{n}(G)$ the free
submodule generated by all degenerate $n$-cubes, $B_{0}(G)=0$.

For $n\geq 1$, one can define a homomorphism $\partial^{c}:Q_{n}(G)\rightarrow
Q_{n-1}(G)$ via the inclusions $\eqref{n-1_n_inclusion}$ by

$\partial^{c}{\phi}=\sum_{j=1}^{n}(-1)^{j}\left(\phi\circ F_{j0}-\phi\circ
F_{j1}\right)$

and $\partial^{c}=0$ for $n=0$.

######  Proposition 3.4 ([7], [15]).

The homomorphism $\partial^{c}$ defines a boundary operator, that is
$\left(\partial^{c}\right)^{2}=0$. Meanwhile,
$\partial^{c}\big{(}B_{n}(G)\big{)}\subset B_{n-1}(G)$.

Following from this proposition,
$(B_{*}(G),\partial^{c})\subset(Q_{*}(G),\partial^{c})$ is a sub-complex.
Hence, the quotient complex

$\left(\Omega_{*}^{c}(G)=Q_{*}(G)/B_{*}(G),\partial^{c}\right)$

is well-defined, and it is called the (normalized) singular cubical chain
complex of the digraph $G$. The associated homology is called the singular
cubical homology of $G$, and denoted by $H_{*}^{c}(G)$.

There is a chain map from the singular cubical complex of $G$ to the original
path complex of $G$, which is useful in our construction of next subsection.

First, there is a standard generator $\omega_{n}$ of $\Omega_{n}(I^{\boxdot
n};\mathbb{Z})$. Denote by $E_{n}$ the set of allowed elementary $n$-paths
between $(0,\ldots,0)$ and $(1,\ldots,1)$ in $I^{\boxdot n}$. Then
$\omega_{n}$222There is another way to define $\omega_{n}$ by using the cross
product $\times$ (Definition 3.44),
$\omega_{n}=\underbrace{e_{01}\times\cdots\times e_{01}}_{n}.$ is defined to
be

$\omega_{n}=\sum_{e_{\alpha}\in E_{n}}(-1)^{\sigma_{n}(\alpha)}e_{\alpha},$

where

  * •

$\alpha=\alpha_{0}~{}\rightarrow~{}\alpha_{1}~{}\rightarrow\cdots\rightarrow~{}\alpha_{n}$
with the vertex $\alpha_{k}=(\alpha_{k,i})_{i=1}^{n}$;

  * •

$\sigma(\alpha)$ is the number of inversions in the sequence
$\\{\sum_{i=1}^{n}2^{i}\alpha_{k,i}\\}$.

Second, one can define a homomorphism
$\tau_{n}:\Omega_{n}^{c}(G)\rightarrow\Omega_{n}(G)$ on the singular $n$-cube
$\phi$ by

$\tau_{n}(\phi):=\phi_{*}(\omega_{n}),$

where $\phi_{*}$ is a linear map defined on the elementary paths by

(3.2) $\phi_{*}(e_{i_{0}i_{1}\ldots
i_{n}})=\left\\{\begin{array}[]{ll}e_{\phi(i_{0})\phi(i_{1})\ldots\phi(i_{n})},&\hbox{if
all $\phi(i_{j})\neq\phi(i_{j+1})$;}\\\
0,&\hbox{otherswise.}\end{array}\right.$

Then one has

######  Proposition 3.5 ([7]).

For $n\geq 0$, and $\phi\in\Omega_{n}^{c}(G)$,

$\partial\circ\tau_{n}(\phi)=\tau_{n-1}\circ\partial^{c}(\phi).$

###  3.2. Admissible pair and admissible relations

####  3.2.1. Admissible pair

Let $\widetilde{\mathcal{P}}_{n}(G)$ be the set of minimal $n$-paths in $G$.
If $P\in\widetilde{\mathcal{P}}_{n}(G)$, so is $-P$. Furthermore, let
$\mathcal{P}_{n}(G)$ be the subset of $\widetilde{\mathcal{P}}_{n}(G)$
containing exactly one of $P$ and $-P$. In the following, we write

$\mathcal{P}_{n}=\mathcal{P}_{n}(G)=\\{P_{n,\alpha}\\}_{\alpha},\quad\mathcal{P}=\bigcup_{n\geq
0}\mathcal{P}_{n}.$

And call them the set of minimal $n$-paths and the set of minimal paths (up to
a sign), respectively.

In our further construction, we will work with a subset of $\mathcal{P}$ which
is related to the singular cube.

First, we modify the definition $f_{*}$ for the digraph map $f:G\rightarrow H$
to work with our situation.

######  Definition 3.6.

Let $G$ and $H$ be two digraphs, and $f:G\rightarrow H$ be a digraph map. Then
we can define a $\mathbb{Z}$-linear map

$f_{*}:\mathcal{A}_{*}(G;\mathbb{Z})\rightarrow\mathcal{A}_{*}(H;\mathbb{Z})$

by

$f_{*}(e_{i_{0}i_{1}\ldots
i_{k}})=\left\\{\begin{array}[]{ll}e_{f(i_{0})f(i_{1})\ldots
f(i_{k})},&\hbox{if all $f(i_{j})$'s are dinstict;}\\\
0,&\hbox{otherswise.}\end{array}\right.$

######  Remark 3.7.

The original definition (3.2) of $f_{*}$ is a chain map between the original
path complexes. For our restricted case, if $H$ has no monotone cycles, then
$f_{*}$ induces a chain map $f_{*}:\Omega_{*}(G)\rightarrow\Omega_{*}(H)$.

With the help of the induced map $f_{*}$, we give our key definition.

######  Definition 3.8.

Let $G$ be a digraph. For $P\in\mathcal{P}_{n}(G)$, we call the pair
$(P,\operatorname{Supp}(P))$ admissible, if there exists a digraph map

$f:I^{\boxdot n}\longrightarrow G$

such that

  1. (1)

$f_{*}(\omega_{n})=cP$ for some $c\in\mathbb{Z}\setminus\\{0\\}$;

  2. (2)

the image digraph of $f$ is $\operatorname{Supp}(P)$.

We also say that $(P,\operatorname{Supp}(P))$ admits a singular cubical
realization.

Let $\mathcal{P}_{\operatorname{adm}}=\mathcal{P}_{\operatorname{adm}}(G)$ be
the set of the admissible pairs in $G$, that is

$\mathcal{P}_{\operatorname{adm}}=\left\\{(P,\operatorname{Supp}(P))\text{ is
admissible. }\big{|}~{}P\in\mathcal{P}\right\\}.$

Since $\operatorname{Supp}(P)$ is determined by $P$, we also regard
$\mathcal{P}_{\operatorname{adm}}$ as a subset of $\mathcal{P}$, and write it
as

$\mathcal{P}_{\operatorname{adm}}=\left\\{P\in\mathcal{P}~{}\big{|}~{}(P,\operatorname{Supp}(P))\text{
is admissible.}\right\\}.$

Now let us give several trivial and non-trivial examples to understand the
definition.

######  Example 3.9 (Triangle $K_{3}$ and Cycle $C_{3}$).

Let us consider the following digraphs $K_{3}$ and $C_{3}$:

$0$
---
$1$
---
$2$
---
$C_{3}=$
---
$0$
---
$1$
---
$2$
---
$K_{3}=$
---

For the triangle digraph $K_{3}$, the set of minimal paths is

$\mathcal{P}=\\{e_{0},~{}e_{1},~{}e_{2};~{}e_{01},~{}e_{02},~{}e_{12};~{}e_{012}\\}.$

Obviously, the admissible set $\mathcal{P}_{\operatorname{adm}}$ is the same
as $\mathcal{P}$.

In particular, the admissible pair
$(e_{012},K_{3}=\operatorname{Supp}(e_{012}))$ could be realized by the
following digraph map $f:I^{\boxdot 2}\rightarrow K_{3}$.

$f((0,0))=0,\quad f((0,1))=1,\quad f((1,0))=f((1,1))=2,$

or alternatively,

$f((0,0))=f((1,0))=0,\quad f((0,1))=1,\quad f((1,1))=2.$

For the 3-cycle digraph $C_{3}$, we have

$\mathcal{P}_{\operatorname{adm}}=\mathcal{P}=\\{e_{0},~{}e_{1},~{}e_{2};~{}e_{01},~{}e_{12},~{}e_{20}\\}.$

######  Example 3.10 (Square $S$ and Cycle $C_{4}$).

Let us consider the following digraphs $S$ and $C_{4}$:

$0$
---
$1$
---
$3$
---
$2$
---
$S=$
---
$0$
---
$1$
---
$3$
---
$2$
---
$C_{4}=$
---

For the square digraph $S$, $S\cong I^{\boxdot 2}$. Obviously, we have

$\mathcal{P}_{\operatorname{adm}}(S)=\mathcal{P}(S)=\\{e_{0},~{}e_{1},~{}e_{2},~{}e_{3};~{}e_{01},~{}e_{02},~{}e_{13},~{}e_{23};~{}e_{013}-e_{023}\\}.$

For the 4-cycle digraph $C_{4}$, we have

$\mathcal{P}_{\operatorname{adm}}(C_{4})=\mathcal{P}(C_{4})=\\{e_{0},~{}e_{1},~{}e_{2},~{}e_{3};~{}e_{01},~{}e_{13},~{}e_{32},~{}e_{20}\\}.$

######  Example 3.11.

For the supporting digraph $\operatorname{Supp}(e_{0123})$ (see Example 2.6),
the admissible set $\mathcal{P}_{\operatorname{adm}}$ is the same as
$\mathcal{P}$. That is,

$\displaystyle\mathcal{P}_{\operatorname{adm}}=\mathcal{P}=\\{$ $\displaystyle
e_{0},~{}e_{1},~{}e_{2},~{}e_{3};~{}e_{01},~{}e_{02},~{}e_{12},~{}e_{13},~{}e_{23};$
$\displaystyle e_{012},~{}e_{013}-e_{023},~{}e_{123};~{}e_{0123}\\}$

The non-obvious admissible pair $(e_{0123},\operatorname{Supp}(e_{0123}))$
could be realized by $f:I^{\boxdot
3}\longrightarrow\operatorname{Supp}(e_{0123})$:

$\displaystyle f((0,0,0))=0,\quad f((1,0,0))=1,\quad f((0,1,0))=2,\quad
f((0,0,1))=2,$ $\displaystyle f((1,1,0))=2,\quad f((1,0,1))=3,\quad
f((0,1,1))=2,\quad f((1,1,1))=3.$

######  Example 3.12 (Example 2.7 revisited).

For the supporting digraph in Example 2.7, that is,

$P=e_{0136}-e_{0156}+e_{0456}+e_{0246}-e_{0236}.$

$0$
---
$1$
---
$2$
---
$3$
---
$4$
---
$5$
---
$\operatorname{Supp}(P)=$
---
$6$
---

The admissible set is the same as the set of minimal paths. That is,

$\displaystyle\mathcal{P}_{\operatorname{adm}}=\mathcal{P}=\\{$ $\displaystyle
e_{0},~{}e_{1},~{}e_{2},~{}e_{3},~{}e_{4},~{}e_{5},~{}e_{6};$ $\displaystyle
e_{01},~{}e_{02},~{}e_{04},~{}e_{13},~{}e_{15},~{}e_{23},~{}e_{24},~{}e_{36},~{}e_{45},~{}e_{46},~{}e_{56};$
$\displaystyle
e_{013}-e_{023},~{}e_{015}-e_{045},~{}e_{024},~{}e_{136}-e_{156},~{}e_{236}-e_{246},~{}e_{456};$
$\displaystyle e_{0136}-e_{0156}+e_{0456}+e_{0246}-e_{0236}\\}$

The non-obvious admissible pair $(P,\operatorname{Supp}(P))$ could be realized
by the digraph map $f:I^{\boxdot 3}\rightarrow\operatorname{Supp}(P)$:

$\displaystyle f((0,0,0))=0,\quad f((1,0,0))=1,\quad f((0,1,0))=2,\quad
f((0,0,1))=4,$ $\displaystyle f((1,1,0))=3,\quad f((1,0,1))=5,\quad
f((0,1,1))=4,\quad f((1,1,1))=6.$

######  Example 3.13.

For the following digraph $G=\operatorname{Supp}(e_{0135}-e_{0235}+e_{0245})$,
we have $\mathcal{P}_{\operatorname{adm}}=\mathcal{P}$.

$0$
---
$1$
---
$2$
---
$3$
---
$4$
---
$5$
---
$G=$
---

That is,

$\displaystyle\mathcal{P}_{\operatorname{adm}}=\mathcal{P}=\\{$ $\displaystyle
e_{0},~{}e_{1},~{}e_{2},~{}e_{3},~{}e_{4},~{}e_{5};$ $\displaystyle
e_{01},~{}e_{02},~{}e_{04},~{}e_{13},~{}e_{15},~{}e_{23},~{}e_{24},~{}e_{35},~{}e_{45};$
$\displaystyle
e_{013}-e_{023},~{}e_{015}-e_{045},~{}e_{024},~{}e_{135},~{}e_{235}-e_{245};$
$\displaystyle e_{0135}-e_{0235}+e_{0245}\\}.$

In particular, we have the corresponding digraph map $f:I^{\boxdot
3}\longrightarrow\operatorname{Supp}(e_{0135}-e_{0235}+e_{0245})$:

$\displaystyle f((0,0,0))=0,\quad f((1,0,0))=1,\quad f((0,1,0))=2,\quad
f((0,0,1))=4,$ $\displaystyle f((1,1,0))=3,\quad f((1,0,1))=5,\quad
f((0,1,1))=4,\quad f((1,1,1))=5.$

######  Example 3.14.

For the following digraph
$G=\operatorname{Supp}(e_{0136}-e_{0146}-e_{0236}+e_{0256})$, we have
$\mathcal{P}_{\operatorname{adm}}=\mathcal{P}$.

$3$
---

$0$
---

$1$
---
$2$
---
$4$
---
$5$
---
$6$
---
$G=$
---

That is,

$\displaystyle\mathcal{P}_{\operatorname{adm}}=\mathcal{P}=\\{$ $\displaystyle
e_{0},~{}e_{1},~{}e_{2},~{}e_{3},~{}e_{4},~{}e_{5},~{}e_{6};$ $\displaystyle
e_{01},~{}e_{02},~{}e_{04},~{}e_{05},~{}e_{13},~{}e_{14},~{}e_{23},~{}e_{25},~{}e_{36},~{}e_{46},~{}e_{56};$
$\displaystyle
e_{013}-e_{023},~{}e_{046}-e_{056},~{}e_{014},~{}e_{025},~{}e_{136}-e_{146},~{}e_{236}-e_{256};$
$\displaystyle e_{0136}-e_{0146}-e_{0236}+e_{0256}\\}.$

In particular, we have the corresponding digraph map $f:I^{\boxdot
3}\longrightarrow\operatorname{Supp}(e_{0136}-e_{0146}-e_{0236}+e_{0256})$:

$\displaystyle f((0,0,0))=0,\quad f((1,0,0))=1,\quad f((0,1,0))=0,\quad
f((0,0,1))=2,$ $\displaystyle f((1,1,0))=4,\quad f((1,0,1))=3,\quad
f((0,1,1))=5,\quad f((1,1,1))=6.$

In the above examples, we see that $\mathcal{P}_{\operatorname{adm}}$ is the
same as $\mathcal{P}$. In particular, we see that there are many different
admissible pairs. In what follows, we will give several examples in which
$\mathcal{P}_{\operatorname{adm}}$ is a proper subset of $\mathcal{P}$.

######  Example 3.15 (exotic cube).

The minimal digraph which supports

$P=e_{0158}-e_{0258}+e_{0268}-e_{0368}+e_{0378}-e_{0478}$

is given by the following digraph, which is known as the exotic cube.

$0$
---
$1$
---
$2$
---
$3$
---
$4$
---
$5$
---
$6$
---
$7$
---
$8$
---
$\operatorname{Supp}(P)=$
---

The set of minimal paths is given by

$\displaystyle\mathcal{P}=\\{$ $\displaystyle
e_{0},~{}e_{1},~{}e_{2},~{}e_{3},~{}e_{4},~{}e_{5},~{}e_{6},~{}e_{7},~{}e_{8};$
$\displaystyle
e_{01},~{}e_{02},~{}e_{03},~{}e_{04},~{}e_{15},~{}e_{18},~{}e_{25},~{}e_{26},~{}e_{36},~{}e_{37},~{}e_{47},~{}e_{48},~{}e_{58},~{}e_{68},~{}e_{78};$
$\displaystyle
e_{015}-e_{025},~{}e_{026}-e_{036},~{}e_{037}-e_{047},~{}e_{018}-e_{048},~{}e_{158},~{}e_{258}-e_{268},~{}e_{368}-e_{378},~{}e_{478};$
$\displaystyle e_{0158}-e_{0258}+e_{0268}-e_{0368}+e_{0378}-e_{0478}\\}.$

Note that the exotic cube has one more vertex than $I^{\boxdot 3}$, thus it
can not be an image digraph of $I^{\boxdot 3}$. Thus,

$\mathcal{P}_{\operatorname{adm}}=\mathcal{P}\setminus\\{P\\}.$

######  Remark 3.16.

One can find more examples as the exotic cube, such as, Example 2.8. In fact,
although there are various kinds of admissible pairs, for each
$n\in\mathbb{N}_{+}$, the total numbers are finite, due to the second
condition in Definition 3.8. In particular, we conjecture that each supporting
digraph of the admissible path is contractible in Subsection 3.4.

Let us further study the supporting digraphs of two minimal $4$-paths,
$\operatorname{Supp}(e_{01234})$ and Example 2.9.

######  Example 3.17.

The digraph $\operatorname{Supp}(e_{01234})$ is as follows:

$0$
---
$1$
---
$2$
---
$3$
---
$4$
---
$\operatorname{Supp}(e_{01234})=$
---

Similarly, we have

$\displaystyle\mathcal{P}_{\operatorname{adm}}=\mathcal{P}=\\{$ $\displaystyle
e_{0},~{}e_{1},~{}e_{2},~{}e_{3},~{}e_{4};~{}e_{01},~{}e_{02},~{}e_{12},~{}e_{13},~{}e_{23},~{}e_{24},~{}e_{34};$
$\displaystyle
e_{012},~{}e_{013}-e_{023},~{}e_{123},~{}e_{124}-e_{134},~{}e_{234};$
$\displaystyle
e_{0123},~{}e_{1234},~{}e_{0124}-e_{0134}+e_{0234};~{}e_{01234}\\}.$

In particular, we have the two digraph maps realizing
$e_{0124}-e_{0134}+e_{0234}$ and $e_{01234}$ respectively:

$\displaystyle f:I^{\boxdot 4}\longrightarrow\operatorname{Supp}(e_{01234}),$
$\displaystyle g:I^{\boxdot
3}\longrightarrow\operatorname{Supp}(e_{0124}-e_{0134}+e_{0234}),$

which are given by

$\displaystyle f((0,0,0,0))=0,\quad f((1,0,0,0))=1,\quad f((0,1,0,0))=1,\quad
f((0,0,1,0))=2,$ $\displaystyle f((0,0,0,1))=2,\quad f((1,1,0,0))=3,\quad
f((1,0,1,0))=2,\quad f((1,0,0,1))=3,$ $\displaystyle f((0,1,1,0))=3,\quad
f((0,1,0,1))=2,\quad f((0,0,1,1))=3,\quad f((1,1,1,0))=4,$ $\displaystyle
f((1,1,0,1))=3,\quad f((1,0,1,1))=4,\quad f((0,1,1,1))=3,\quad
f((1,1,1,1))=4;$ $\displaystyle g=f\big{|}_{I^{\boxdot 3}\boxdot\\{0\\}}.$

Note that in this example,

$\operatorname{Supp}(e_{0124}-e_{0134}+e_{0234})=\operatorname{Supp}(e_{01234}),$

but we regard
$\left(e_{0124}-e_{0134}+e_{0234},~{}\operatorname{Supp}(e_{0124}-e_{0134}+e_{0234})\right)$
as a length-$3$ admissible pair, while
$\left(e_{01234},~{}\operatorname{Supp}(e_{01234})\right)$ as a length-$4$
admissible pair. The former path is a minimal face component of the latter
one.

######  Remark 3.18.

In general, the existence of the digraph map $f:I^{\boxdot
n}\longrightarrow\operatorname{Supp}(P_{n,\alpha})$ in our definition is not
unique, such as the singular cubical realizations of $(e_{012},K_{3})$ in
Example 3.9, there may exist different “degenerations” on faces. Meanwhile,
$I^{\boxdot n}$ has a non-trivial automorphism group, which also leads to the
non-uniqueness.

######  Example 3.19 (Example 2.9 revisited).

Let us look at the digraph $\operatorname{Supp}(P)$ in Example 2.9. According
to the structure theorem 2.10, we have

$\displaystyle\mathcal{P}_{3}=\\{$ $\displaystyle
e_{S159}-e_{S169}+e_{S269},~{}e_{S16(10)}-e_{S26(10)}+e_{S27(10)}-e_{S37(10)},$
$\displaystyle e_{S27(11)}-e_{S37(11)}+e_{S28(11)}-e_{S48(11)};$
$\displaystyle
e_{159E}-e_{169E}+e_{16(10)E},~{}e_{269E}-e_{26(10)E}+e_{27(10)E}-e_{27(11)E},$
$\displaystyle e_{37(10)E}-e_{37(11)E}+e_{38(11)E},~{}e_{48(11)E};$
$\displaystyle
P_{S,3,E}:=e_{S15E}-e_{S1(10)E}+e_{S2(11)E}-e_{S29E}-e_{S38E}+e_{S3(10)E}+e_{S48E}-e_{S4(11)E}+e_{S59E}\\}.$

According to the above examples, all the minimal $3$-paths in
$\mathcal{P}_{3}$ are admissible except the last one $P_{S,3,E}$, since it has
11 vertices. Thus,

$\mathcal{P}_{\operatorname{adm},3}=\mathcal{P}_{3}\setminus\\{P_{S,3,E}\\}.$

Furthermore, $P\in\mathcal{P}_{4}$ is also not admissible. The reason is as
follows: if $(P,\operatorname{Supp}(P))$ is realizable by the singular
$4$-cube $f$, then $f_{*}(\omega_{n})=P$ implies

$\displaystyle f((0,0,0,0))=S,\quad f((1,1,1,1))=E;$ $\displaystyle
f:\\{(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)\\}\rightarrowtail\\{1,2,3,4\\}.$

We claim that the edge $S\rightarrow 5$ can not be in the image digraph of
$f$. If $S\rightarrow 5$ is realizable by $f$, let us analyze the possible
pre-images of $S$:

  * •

$f((0,0,0,0))=S$. Note that there are only four directed edges starting from
$(0,0,0,0)$ in $I^{\boxdot 4}$, which have been mapped to $S\rightarrow 1$,
$S\rightarrow 2$, $S\rightarrow 3$ and $S\rightarrow 4$. Then $S\rightarrow 5$
can not be realized as the pre-image of $f$ via the edges starting from
$(0,0,0,0)$.

  * •

$f((\epsilon_{1},\epsilon_{2},\epsilon_{3},\epsilon_{4}))=S$, for some
$\epsilon_{i}$ with two of them being $1$ and the other two of them being $0$.
Then the image digraph has the edge $1\rightarrow S$, or $2\rightarrow S$, or
$3\rightarrow S$, or $3\rightarrow S$. Contraction.

  * •

$f((\epsilon_{1},\epsilon_{2},\epsilon_{3},\epsilon_{4}))=S$, for some
$\epsilon_{i}$ with three of them being $1$ and the remaining of them being
$0$. Then the image digraph has the edge $S\rightarrow E$. Contraction.

Thus, $\operatorname{Supp}(P)$ could not be the image digraph of any singular
$4$-cube. We have

$\mathcal{P}_{\operatorname{adm}}=\mathcal{P}\setminus\\{P\\}.$

####  3.2.2. Admissible relations

######  Definition 3.20.

For $P_{1}$, $P_{2}\in\mathcal{P}_{\operatorname{adm}}(G)$, if one of $\pm
P_{1}\pm P_{2}$ belongs to $\mathcal{P}_{\operatorname{adm}}(G)$, denote it by
$P_{3}$, that is,

$(P_{3},\operatorname{Supp}(P_{3}))\in\mathcal{P}_{\operatorname{adm}}(G),$

we say that $P_{1}$ and $P_{2}$ are summable in
$\mathcal{P}_{\operatorname{adm}}(G)$. If $P_{3}=P_{1}+P_{2}$, we also write
the relation as

$(P_{3},\operatorname{Supp}(P_{3}))=(P_{1},\operatorname{Supp}(P_{1}))+(P_{2},\operatorname{Supp}(P_{2})).$

We call the linear relations among $\mathcal{P}_{\operatorname{adm}}(G)$ the
admissible relations.

######  Example 3.21.

For any integer $k\geq 3$, we consider the following digraph $S_{k}$, with

$V(S_{k})=\\{S,E,1,2,\ldots,k\\},\qquad
E(S_{k})=\\{S~{}\rightarrow~{}i\\}_{i=1}^{k}\cup\\{i~{}\rightarrow~{}E\\}_{i=1}^{k}.$

$S$
---
$1$
---
$k$
---
$E$
---
$S_{k}=$
---
$2$
---
$k-1$
---
$\vdots$
---

It is easy to see that

$\displaystyle\mathcal{P}_{\operatorname{adm}}=\mathcal{P}=\\{$ $\displaystyle
e_{S},~{}e_{E},~{}e_{i},~{}i=1,\ldots,k;$ $\displaystyle
e_{Si},~{}e_{iE},~{}i=1,\ldots,k;$ $\displaystyle
e_{SiE}-e_{SjE},~{}i,j=1,\ldots,k,\text{and }i\neq j\text{ (up to a sign)}\\}$

For distinct $a,b,c\in\\{1,\ldots,k\\}$, $e_{SaE}-e_{SbE}$ and
$e_{SbE}-e_{ScE}$ are summable and

$(e_{SaE}-e_{SbE})+(e_{SbE}-e_{ScE})=e_{SaE}-e_{ScE}\in\mathcal{P}_{\operatorname{adm}}.$

######  Example 3.22.

For the following digraph,

$0$
---
$1$
---
$3$
---
$6$
---
$2$
---
$4$
---
$5$
---

The admissible set is the same as the set of minimal paths. In particular, the
length-3 part of both sets is given by

$\mathcal{P}_{\operatorname{adm},3}=\mathcal{P}_{3}=\\{e_{0136}-e_{0236}+e_{0256},~{}e_{0136}-e_{0146}+e_{0246}-e_{0236},~{}e_{0146}-e_{0246}+e_{0256}\\}.$

Clearly, any two of them are summable in $\mathcal{P}_{\operatorname{adm},3}$.

######  Example 3.23.

For the following digraph,

$S$
---
$1$
---
$6$
---
$E$
---
$2$
---
$7$
---
$0$
---
$5$
---
$3$
---
$4$
---
$8$
---
$9$
---

Similarly, we look at the length-3 part.

$\displaystyle\mathcal{P}_{3}=\\{$ $\displaystyle
e_{S05E}-e_{S15E}+e_{S16E},~{}e_{S16E}-e_{S17E}+e_{S27E},$ $\displaystyle
e_{S27E}-e_{S37E}+e_{S38E},~{}e_{S38E}-e_{S39E}+e_{S49E},$ $\displaystyle
e_{S05E}-e_{S15E}+e_{S17E}-e_{S27E},~{}e_{S16E}-e_{S17E}+e_{S37E}-e_{S38E},$
$\displaystyle e_{S27E}-e_{S37E}+e_{S39E}-e_{S49E},$ $\displaystyle
e_{S05E}-e_{S15E}+e_{S17E}-e_{S37E}+e_{S38E},$ $\displaystyle
e_{S16E}-e_{S17E}+e_{S37E}-e_{S39E}+e_{S49E},$ $\displaystyle
e_{S05E}-e_{S15E}+e_{S17E}-e_{S37E}+e_{S39E}-e_{S49E}\\},$

Note that $e_{S05E}-e_{S15E}+e_{S17E}-e_{S37E}+e_{S38E}$ is not admissible,
since its supporting digraph has 13 edges, more than those of 3-cube
$I^{\boxdot 3}$. One can apply the same argument to the final two paths in
$\mathcal{P}_{3}$. Then we have

$\displaystyle\mathcal{P}_{\operatorname{adm},3}=\\{$ $\displaystyle
e_{S05E}-e_{S15E}+e_{S16E},~{}e_{S16E}-e_{S17E}+e_{S27E},$ $\displaystyle
e_{S27E}-e_{S37E}+e_{S38E},~{}e_{S38E}-e_{S39E}+e_{S49E},$ $\displaystyle
e_{S05E}-e_{S15E}+e_{S17E}-e_{S27E},~{}e_{S16E}-e_{S17E}+e_{S37E}-e_{S38E},$
$\displaystyle e_{S27E}-e_{S37E}+e_{S39E}-e_{S49E}\\}.$

In particular, note that

  * •

$e_{S05E}-e_{S15E}+e_{S16E}$ and $e_{S16E}-e_{S17E}+e_{S27E}$ are summable in
both $\mathcal{P}_{3}$ and $\mathcal{P}_{\operatorname{adm},3}$;

  * •

$e_{S05E}-e_{S15E}+e_{S16E}$ and $e_{S16E}-e_{S17E}+e_{S37E}-e_{S38E}$ is
summable in $\mathcal{P}_{3}$, but not summable in
$\mathcal{P}_{\operatorname{adm},3}$.

####  3.2.3. CW complex of the digraph

Now we follow Whitehead’s definition of CW complex of a Hausdorff topological
space, and give our definition of CW complex of a digraph $G$.

######  Definition 3.24.

Let $G$ be a digraph, and $\mathcal{P}_{\operatorname{adm}}=\bigcup_{n\geq
0}\mathcal{P}_{\operatorname{adm},n}=\bigcup_{n\geq
0}\\{P_{n,\alpha}\\}_{\alpha}$ be the set of admissible minimal paths in $G$.
Then the pair
$\left(G,\mathcal{P}^{\prime}_{\operatorname{adm}}=\bigcup_{n\geq
0}\\{P_{n,\alpha^{\prime}}\\}_{\alpha^{\prime}}\subset\subset\mathcal{P}_{\operatorname{adm}}\right)$
is called a CW complex of $G$ if the following three conditions are satisfied:

  1. (1)

$G=\bigcup_{P_{n,\alpha^{\prime}}\in\mathcal{P}^{\prime}_{\operatorname{adm}}}\operatorname{Supp}(P_{n,\alpha^{\prime}})$;

  2. (2)

For each $n\geq 0$, there are not admissible relations among
$\\{P_{n,\alpha^{\prime}}\\}_{\alpha^{\prime}}$;

  3. (3)

$\mathcal{P}^{\prime}_{\operatorname{adm}}$ is the maximal subset of
$\mathcal{P}_{\operatorname{adm}}$ satisfying (1) (2).

######  Remark 3.25.

By Definition 3.24 (2) (3), the $\operatorname{CW}$ complex associated to $G$
depends on the choice of the basis due to the possible existence of admissible
relations.

###  3.3. Cellular homology of a digraph

By the standard argument, there exists a cellular chain complex associated to
each $\operatorname{CW}$ complex. But, to avoid discussing the choice of
basis, we define the associated cellular chain complex to be a quotient
complex as follows. For simplicity, in the sequel, we work with coefficient
$\mathbb{R}$ or other fields with characteristic $0$.

######  Definition 3.26 (Cellular chain of a digraph $G$).

Let $G$ be a digraph and $\mathcal{P}_{\operatorname{adm}}$ be the set of
admissible minimal paths of $G$. For all $n\in\mathbb{N}$, the
$\mathbb{R}$-module $C_{n}(G;\mathbb{R})$, called the $n$-th cellular chain
group of $G$ with coefficient $\mathbb{R}$, is generated by the admissible
$n$-minimal paths quotient by the admissible relations

$C_{n}(G;\mathbb{R})=\left\\{\sum_{P\in\mathcal{P}_{\operatorname{adm},n}}c_{P}P~{}\bigg{|}~{}c_{P}\in\mathbb{R}\right\\}\bigg{/}\left\\{\text{admissible
relations}\right\\}.$

Moreover, for any $P\in\mathcal{P}_{\operatorname{adm},n}$, and $n\geq 1$, we
define $\partial^{\operatorname{cell}}P$ as follows:

$\partial^{\operatorname{cell}}P=\sum_{Q\in\mathcal{P}_{\operatorname{adm},n-1}}[Q:P]Q,$

where the number $[Q:P]$ is defined as follows:

$[Q:P]=\left\\{\begin{array}[]{ll}1,&\hbox{if $Q<\partial P$;}\\\ -1,&\hbox{if
$-Q<\partial P$;}\\\ 0,&\hbox{otherwise.}\end{array}\right.$

We also call $Q$ to be the real face of $P$ if $[Q:P]\neq 0$. For
$P\in\mathcal{P}_{\operatorname{adm},0}$,
$\partial^{\operatorname{cell}}P:=0$; or we make the convention that
$\mathcal{P}_{\operatorname{adm},-1}=0$, $C_{-1}(G;\mathbb{R})=0$.

It extends $\mathbb{R}$-linearly to the graded free group generated by
$P\in\mathcal{P}_{\operatorname{adm}}(G)$.

######  Proposition 3.27.

The operator $\partial^{\operatorname{cell}}$ can be descended to the quotient
group $C_{*}(G;\mathbb{R})$, still denoted by
$\partial^{\operatorname{cell}}$. That is, we have a well-defined operator

$\partial^{\operatorname{cell}}:C_{n}(G;\mathbb{R})\longrightarrow
C_{n-1}(G;\mathbb{R}).$

Moreover, it is a boundary operator:
$\left(\partial^{\operatorname{cell}}\right)^{2}=0$.

The proof is based on the following several lemmas.

######  Lemma 3.28.

For $P\in\mathcal{P}_{\operatorname{adm},n}(G)$. In the sub-digraph
$\operatorname{Supp}(P)\subset G$, the boundary operator

$\partial^{\operatorname{cell}}:C_{n}(\operatorname{Supp}(P);\mathbb{R})\longrightarrow
C_{n-1}(\operatorname{Supp}(P);\mathbb{R})$

coincides with the one of path complex of $\operatorname{Supp}(P)$. That is,
we have

$\partial^{\operatorname{cell}}P=\partial P=\sum_{\alpha\in
E_{1}}P_{S,n-1,\alpha}+\sum_{\beta\in S_{1}}P_{\beta,n-1,E}+\sum_{k\in
I_{P}}P_{S,n-1,E}^{k}.$

###### Proof.

For any $P\in\mathcal{P}_{\operatorname{adm},n}$ with starting point $S$ and
ending point $E$, by the structure theorem 2.10 for $\operatorname{Supp}(P)$,
we have the decomposition in $\operatorname{Supp}(P)$,

(3.3) $\partial P=\sum_{\alpha\in E_{1}}P_{S,n-1,\alpha}+\sum_{\beta\in
S_{1}}P_{\beta,n-1,E}+\sum_{k\in I_{P}}P_{S,n-1,E}^{k}.$

And the minimal face components of right hand side are all the real faces of
$P$ in $\operatorname{Supp}(P)$ with the right sign. It remains to check that
each of them has a singular cubical realization, i.e.

$P_{S,n-1,\alpha},~{}P_{\beta,n-1,E},~{}P_{S,n-1,E}^{k}\in\mathcal{P}_{\operatorname{adm},n-1}(\operatorname{Supp}(P)).$

Since $P$ is admissible, there exists a digraph map $f:I^{\boxdot
n}\rightarrow\operatorname{Supp}(P)$, such that

$f_{*}(\omega_{n})=cP,\quad\text{for some }c\in\mathbb{Z}\setminus\\{0\\}.$

In particular, taking into account the length reason, there must be

$f((0,0,\ldots,0))=S,\quad f((1,1,\ldots,1))=E.$

By Proposition 3.5, we have

(3.4) $\displaystyle\partial P=$ $\displaystyle~{}\partial\circ
f_{*}(\omega_{n})=\partial\circ\tau_{n}(f)=\tau_{n-1}\circ\partial^{c}(f)=(\partial^{c}(f))_{*}(\omega_{n-1})$
$\displaystyle=$ $\displaystyle~{}\sum_{j=1}^{n}(-1)^{j}(f\circ
F_{j0})_{*}(\omega_{n-1})-\sum_{j=1}^{n}(-1)^{j}(f\circ
F_{j1})_{*}(\omega_{n-1}).$

Now let us compare the two decompositions (3.3) and (3.4). First, by
definition of the induced homomorphism $(f\circ F_{j\epsilon})_{*}$, each
$(f\circ
F_{j\epsilon})_{*}(\omega_{n-1})\in\Omega_{n-1}(\operatorname{Supp}(P);\mathbb{Z})$.
Then we can classify it according to the starting and ending points.

More explicitly, note that for the minimal path $\omega_{n}$ in $I^{\boxdot
n}$, we have

$\displaystyle S(\omega_{n})=(0,0,\ldots,0),\qquad
E(\omega_{n})=(1,1,\ldots,1),$ $\displaystyle
S_{1}(\omega_{n})=\\{(1,0,0,\ldots,0),~{}(0,1,0,\ldots,0),~{}\cdots,~{}(0,\ldots,0,0,1)\\}$
$\displaystyle
E_{1}(\omega_{n})=\\{(0,1,1,\ldots,1),~{}(1,0,1,\ldots,1),~{}\cdots,~{}(1,\ldots,1,1,0)\\}.$

Furthermore, let

$\displaystyle E_{1,\alpha}=\\{j_{\alpha}|0\text{ appears in the
$j_{\alpha}$-th position of }f^{-1}(\alpha)\cap E_{1}(\omega_{n})\\},$
$\displaystyle S_{1,\beta}=\\{k_{\beta}|1\text{ appears in the $k_{\beta}$-th
position of }f^{-1}(\beta)\cap S_{1}(\omega_{n})\\}.$

Then by (3.3), we have

$\displaystyle P_{S,n-1,\alpha}=\sum_{j_{\alpha}\in
E_{1,\alpha}}(-1)^{j_{\alpha}}(f\circ F_{j_{\alpha}0})_{*}(\omega_{n-1}),$
$\displaystyle P_{\beta,n-1,E}=\sum_{k_{\beta}\in
S_{1,\beta}}(-1)^{k_{\beta}}(f\circ F_{k_{\beta}1})_{*}(\omega_{n-1}),$
$\displaystyle P_{S,n-1,E}^{k}=\partial P-\left(\sum_{\alpha\in
E_{1}}\sum_{j_{\alpha}\in E_{1,\alpha}}(-1)^{j_{\alpha}}(f\circ
F_{j_{\alpha}0})_{*}(\omega_{n-1})-\right.$
$\displaystyle\qquad\qquad\qquad\left.\sum_{\beta\in S_{1}}\sum_{k_{\beta}\in
S_{1,\beta}}(-1)^{k_{\beta}}(f\circ F_{k_{\beta}1})_{*}(\omega_{n-1})\right).$

Since $\operatorname{Supp}(P)$ does not contain monotone cycles, then each
$(f\circ
F_{j\epsilon})_{*}(\omega_{n-1})\in\Omega_{n-1}(\operatorname{Supp}(P))$. By
the decomposition (3.3), and the unique result in the structure theorem, there
exist non-zero integers $\\{c_{\alpha}\\}_{\alpha\in E_{1}}$,
$\\{c_{\beta}\\}_{\beta\in S_{1}}$, $\\{d_{k}\\}_{k\in I_{P}}$ such that

$\displaystyle c_{\alpha}P_{S,n-1,\alpha}=(f\circ
F_{j_{\alpha}0})_{*}(\omega_{n-1}),\text{ for some }j_{\alpha},$
$\displaystyle c_{\beta}P_{\beta,n-1,E}=(f\circ
F_{k_{\beta}1})_{*}(\omega_{n-1}),\text{ for some }k_{\beta},$ $\displaystyle
d_{k}P_{S,n-1,E}^{k}=(f\circ F_{j\epsilon})_{*}(\omega_{n-1}),\text{ for some
}j\text{ and some }\epsilon.$

It remains to check the images of the above chosen $f\circ F_{j_{\alpha}0}$,
$f\circ F_{k_{\beta}1}$ and $f\circ F_{j\epsilon}$ are
$\operatorname{Supp}(P_{S,n-1},\alpha)$, $\operatorname{Supp}(P_{\beta,n-1,E}$
and $\operatorname{Supp}(P_{S,n-1,E}^{k})$ respectively.

Since $(f\circ
F_{j_{\alpha}0})_{*}(\omega_{n-1})=c_{\alpha}P_{S,n-1,\alpha}\in\Omega_{n-1}(\operatorname{Supp}(P))$,
by the minimal condition of $\operatorname{Supp}(P_{S,n-1,\alpha})$, we have

$\operatorname{Supp}(P_{S,n-1,\alpha})\subset\operatorname{im}(f\circ
F_{j_{\alpha}0}).$

Now assume $\operatorname{Supp}(P_{S,n-1,\alpha})\neq\operatorname{im}(f\circ
F_{j_{\alpha}0})$, then applying the structure theorem to
$\operatorname{Supp}(P)$ and $\operatorname{Supp}(P_{S,n-a,\alpha})$, we see
that there exists

$v\in V(\operatorname{im}(f\circ F_{j_{\alpha}0}))\setminus
V(\operatorname{Supp}(P_{S,n-1,\alpha})).$

Let us choose one of the pre-images $(f\circ F_{j_{\alpha}0})^{-1}(v)$ in
$I^{\boxdot(n-1)}$, and denote it by

$(\epsilon_{1}^{v},\epsilon_{2}^{v},\ldots,\epsilon_{n-1}^{v}).$

Then we consider the elementary $(n-1)$-path in $I^{\boxdot(n-1)}$ passing
through $(\epsilon_{1}^{v},\epsilon_{2}^{v},\ldots,\epsilon_{n-1}^{v})$. Its
image under $f\circ F_{j_{\alpha}0}$ is an elementary $k$-path ($k\leq(n-1)$)
from $S$ to $\alpha$ passing through $v$. By applying the structure theorem of
$\operatorname{Supp}(P)$ and $\operatorname{Supp}(P_{S,n-1,\alpha})$ again, we
see that all the elementary $k$-paths ($k\leq(n-1)$) from $S$ to $\alpha$ in
$\operatorname{Supp}(P)$ lie in $\operatorname{Supp}(P_{S,n-1,\alpha})$. Thus,
$v\in V(\operatorname{Supp}(P_{S,n-1,\alpha}))$, contradiction.

The arguments for $\operatorname{Supp}(P_{\beta,n-1,E})$ and
$\operatorname{Supp}(P_{S,n-1,E}^{k})$ are the same. In summary,

$P_{S,n-1,\alpha},~{}P_{\beta,n-1,E},~{}P_{S,n-1,E}^{k}\in\mathcal{P}_{\operatorname{adm},n-1}(\operatorname{Supp}(P)).$

∎

Note that each face component of $P$ in $\operatorname{Supp}(P)$ is a linear
combination of s-regular allowed elementary paths with coefficients $1$ or
$-1$. But it may not be minimal in $G$. Thus, to prove the coincidence of
$\partial^{\operatorname{cell}}$ and $\partial$ in $G$, first we need to prove
the following result: if some face component of $P$ is not minimal in $G$, we
will show that any of its minimal components have singular cubical
realizations. More explicitly, we need to prove the following lemma.

######  Lemma 3.29.

Let $P$ be a linear combination of s-regular allowed elementary paths with
coefficients $1$ or $-1$ and there exists a digraph map

$f:I^{\boxdot n}\longrightarrow G$

such that $f_{*}(\omega_{n})=P$, and the image digraph is
$\operatorname{Supp}(P)$. Then for any $P^{\prime}\in\mathcal{P}_{n}(G)$ with
$P^{\prime}\leq P$, we have
$P^{\prime}\in\mathcal{P}_{\operatorname{adm},n}(G)$.

Before the proof, let us give two examples to explain it.

######  Example 3.30.

Let $G$ be the following digraph and $P=e_{013}-e_{023}\in\Omega_{2}(G)$,

$0$
---
$1$
---
$3$
---
$2$
---
$G=$
---

we have the digraph map $f:I^{\boxdot 2}\longrightarrow G$,

$f((0,0))=0,\quad f((1,0))=1,\quad f((0,1))=2,\quad f((1,1))=3.$

Then $f_{*}(\omega_{2})=P$, the image digraph of $f$ is the square given by
$\operatorname{Supp}(P)$.

Note that $P$ is not minimal in $G$ because of the edge $0\rightarrow 3$. The
paths $P_{1}=e_{013}$ and $P_{2}=-e_{023}$ are minimal in $G$, and we have the
digraph maps $g_{1},g_{2}:I^{\boxdot 2}\longrightarrow G$ respectively

$\displaystyle g_{1}((0,0))=0,\quad g_{1}((0,1))=0,\quad g_{1}((1,0))=1,\quad
g_{1}((1,1))=3;$ $\displaystyle g_{2}((0,0))=0,\quad g_{2}((0,1))=2,\quad
g_{2}((1,0))=0,\quad g_{2}((1,1))=3.$

######  Example 3.31.

In Example 3.11, we give the singular cubical realization of the pair
$(P=e_{0135}-e_{0235}+e_{0245},\operatorname{Supp}(P))$. But in the following
bigger digraph $G$,

$0$
---
$1$
---
$2$
---
$3$
---
$4$
---
$5$
---

we have

$P_{1}=e_{0135}-e_{0235}<P,\quad P_{2}=e_{0245}<P.$

And we also have the digraph maps

$g_{1}:I^{\boxdot 3}\longrightarrow\operatorname{Supp}(P_{1}),\quad
g_{2}:I^{\boxdot 3}\longrightarrow\operatorname{Supp}(P_{2})$

which are given by

$\displaystyle g_{1}((0,0,0))=0,\quad g_{1}((1,0,0))=1,\quad
g_{1}((0,1,0))=2,\quad g_{1}((0,0,1))=2;$ $\displaystyle
g_{1}((1,1,0))=3,\quad g_{1}((1,0,1))=5,\quad g_{1}((0,1,1))=5,\quad
g_{1}((1,1,1))=5;$ $\displaystyle g_{2}((0,0,0))=0,\quad
g_{2}((1,0,0))=2,\quad g_{2}((0,1,0))=2,\quad g_{2}((0,0,1))=4;$
$\displaystyle g_{2}((1,1,0))=2,\quad g_{2}((1,0,1))=5,\quad
g_{2}((0,1,1))=4,\quad g_{2}((1,1,1))=5.$

###### Proof of Lemma 3.29.

To prove this lemma, we need to construct a singular cubical realization
$g:I^{\boxdot n}\longrightarrow\operatorname{Supp}(P^{\prime})$. The
construction is based on the following two steps:

  1. (1)

Construct a map
$p:\operatorname{Supp}(P)\rightarrow\operatorname{Supp}(P^{\prime})$, which is
not necessarily a digraph map, but satisfying

$p_{*}(P)=P^{\prime},~{}\mod\text{ (non-allowed paths)}.$

  2. (2)

Modify the singular cubical realization $f:I^{\boxdot
n}\rightarrow\operatorname{Supp}(P)$ to $f^{\prime}:I^{\boxdot
n}\rightarrow\operatorname{Supp}(P)$ such that $f^{\prime}\circ p$ gives the
singular cubical realization of
$(P^{\prime},\operatorname{Supp}(P^{\prime}))$. More explicitly,

     * •

$f^{\prime}\circ p:I^{\boxdot n}\rightarrow\operatorname{Supp}(P^{\prime})$ is
a digraph map;

     * •

$(f^{\prime}\circ p)_{*}(\omega_{n})=cP^{\prime}$ for some
$c\in\mathbb{Z}\setminus\\{0\\}$ and the image digraph of $f^{\prime}\circ p$
is $\operatorname{Supp}(P^{\prime})$.

The construction is done by induction on the number of elementary path
components of $P$.

If $P$ has only one elementary path components, that is,
$P=e_{i_{0}i_{1}\cdots i_{n}}$. Then, the condition $P^{\prime}\leq P$ implies
that $P^{\prime}=P$. Thus, we can take

$p=\operatorname{Id}_{\operatorname{Supp}(P)},\quad f^{\prime}=f.$

Hypothesis: Assume the pair of maps $(p,f^{\prime})$ can be constructed for
$P$ with $\leq(m-1)$ elementary path components.

Now let us consider $P$ with $m$ ($m\geq 2$) elementary path components.
First, we can write $P$ as follows:

$P=\sum_{\alpha_{k}}P_{S,n-k,\alpha_{k}}\alpha_{k-1}\alpha_{k-2}\cdots\alpha_{1}E,\quad\text{for
some }k=1,\ldots,n-1,$

where

  * •

$\alpha_{k}\in d_{E}^{-1}(k)$, $\alpha_{0}=E$;

  * •

$\sum_{\alpha_{k}}P_{S,n-k,\alpha_{k}}$ has $m$ elementary path components and
$|d_{E}^{-1}(k)|\geq 2$.

For example, the following digraph is the supporting digraph of the path (with
4 elementary path components)

$P=e_{01467}-e_{01367}+e_{02367}-e_{02567}.$

$3$
---

$0$
---

$1$
---
$2$
---
$4$
---
$5$
---
$6$
---
$7$
---

We can also write $P$ as

$P=[(e_{014})+(e_{023}-e_{013})+(e_{025})]67,\quad\text{with
}d_{E}^{-1}(2)=\\{3,4,5\\}.$

Then, we apply the technique in the proof of Theorem 4.1 in [17] to
$P_{S,n-k,\alpha_{k}}\alpha_{k-1}$ (abbreviated as $P_{\alpha_{k-1}}$). That
is, we add some edges

$\alpha_{k+1}\rightarrow\alpha_{k-1},\quad\text{for some }\alpha_{k+1}\in
d_{E}^{-1}(k+1)$

to obtain a larger digraph $\operatorname{Supp}(P)_{1}$ and a good splitting
of $P_{\alpha_{k-1}}$:

$P_{\alpha_{k-1}}=P_{\alpha_{k-1},1}+P_{\alpha_{k-1},2},$

where

  * •

$P_{\alpha_{k-1},1},P_{\alpha_{k-1},2}\in\mathcal{P}_{n-k+1}(\operatorname{Supp}(P)_{1})$,
and $P_{\alpha_{k-1},1},P_{\alpha_{k-1},2}<P_{\alpha_{k-1}}$ in
$\operatorname{Supp}(P)_{1}$;

  * •

$P_{\alpha_{k-1},1}$ is of the form

$P_{\alpha_{k-1},1}=\sum_{\alpha_{k+1}}P_{S,n-k-1,\alpha_{k+1}}\alpha_{k}\alpha_{k-1},\quad\text{i.e.
}d_{E}^{-1}(k)\cap V(P_{\alpha_{k-1},1})=1.$

Let us set

$\displaystyle
P_{1}:=P_{\alpha_{k-1},1}\alpha_{k-2}\cdots\alpha_{1}E=\sum_{\alpha_{k+1}}P_{S,n-k-1,\alpha_{k+1}}\alpha_{k}\alpha_{k-1}\alpha_{k-2}\cdots\alpha_{1}E;$
$\displaystyle P_{1}^{\prime}:=P-P_{1}.$

By the above construction, we have the following two observations:

(1):

$P_{1},P_{1}^{\prime}\in\mathcal{P}_{n}(\operatorname{Supp}(P)_{1})$ and
$P_{1},P_{1}^{\prime}<P$ in $\operatorname{Supp}(P)_{1}$;

(2):

$|V(P_{1})\setminus V(P_{1}^{\prime})|\geq 1$.

If $|V(P_{1})\setminus V(P_{1}^{\prime})|>1$, we continue performing the
operation to $P_{1}$ in $\operatorname{Supp}(P)$, and obtain the new digraph
$\operatorname{Supp}(P)_{2}(\supset\operatorname{Supp}(P)_{1}\supset\operatorname{Supp}(P))$
and $P_{2}$ such that

(3):

$P_{2}\in\mathcal{P}_{n}(\operatorname{Supp}(P)_{2})$ is of the form

$P_{2}=\sum_{\alpha_{k+2}}P_{S,n-k-2,\alpha_{k+2}}\alpha_{k+1}\alpha_{k}\alpha_{k-1}\cdots\alpha_{1}E<P_{1};$

(4):

$1\leq|V(P_{2})\setminus(V(P_{1}-P_{2})\cup
V(P_{1}^{\prime}))|=|V(P_{2})\setminus V(P-P_{2})|<|V(P_{1})\setminus
V(P_{1}^{\prime})|$.

Note that, if $P\in\mathcal{P}_{n}(G)$ has more than 2 elementary path
components, then for each elementary path component $e_{i_{0}i_{1}\ldots
i_{n}}$ in $P$, there exists at least one path component $e_{j_{0}j_{1}\ldots
j_{n}}$ in $P$ such that

$|V(e_{i_{0}i_{1}\ldots i_{n}})\setminus V(e_{j_{0}j_{1}\ldots j_{n}})|=1.$

Thus, if $|V(P_{2})\setminus(V(P-P_{2}))|>1$, after several operations, one
can obtain a much larger digraph $\operatorname{Supp}(P)_{l}$ and $P_{l}$ such
that

(5):

$P_{l}\in\mathcal{P}_{n}(\operatorname{Supp}(P)_{l})$ is of the form

$P_{l}=P_{S,n-k-l,\alpha_{k+l}}\alpha_{k+l-1}\alpha_{k+1}\alpha_{k}\cdots\alpha_{1}E<\cdots<P_{2}<P_{1},\quad
l>2$

(6):

$|V(P_{l})\setminus V(P-P_{l})|=1$, and what is more important is that

$V(P_{l})\setminus V(P-P_{l})=\\{\alpha_{k+l-1}\\}.$

Without loss of generality, we assume that $|V(P_{1})\setminus
V(P_{1}^{\prime})|=1$ and by our notation,

$V(P_{1})\setminus V(P_{1}^{\prime})=\alpha_{k}.$

(Or one can work with $P_{l}$ and remove the redundant new edges to make the
path $P-P_{l}$ minimal.)

Now we need to deal with the following two kinds of local digraphs around
$\alpha_{k}$ in $\widehat{\operatorname{Supp}(P)}$:

I.
---
II.
---
$\alpha_{k+2}^{1}$
---
$\alpha_{k+1}^{1}$
---
$\alpha_{k+1}^{2}$
---
$\alpha_{k}$
---
$\alpha_{k-1}$
---
$\alpha_{k+2}^{2}$
---
$\alpha_{k+1}^{3}$
---
$\alpha_{k}$
---
$\alpha_{k-1}$
---

where, by our construction in Type I subgraph, one of the edges
$\alpha_{k+1}^{i}\rightarrow\alpha_{k-1}$ ($i=1,2$) is added to obtain
$P_{1}$. And in Type II subgraph, the edge
$\alpha_{k+1}^{3}\rightarrow\alpha_{k-1}$ is new.

Now we define the following map

(3.5) $\displaystyle p_{1}:{}$
$\displaystyle\operatorname{Supp}(P)\rightarrow\operatorname{Supp}(P_{1}^{\prime})$
$\displaystyle p_{1}(\alpha_{k})=\alpha_{k-1},$ $\displaystyle
p_{1}(v)=v,~{}\text{ for }v\in V(P)\setminus\\{\alpha_{k}\\}.$

If $\widehat{\operatorname{Supp}(P)}$ only contains Type I local digraph
around $\alpha_{k}$, we have,

  * •

$p_{1}$ is a digraph map;

  * •

$(p_{1})_{*}(P)=P_{1}^{\prime}$ and its image digraph is
$\operatorname{Supp}(P_{1}^{\prime})$.

Then the composition $f\circ p_{1}$ gives us the singular cubical realization
of $P_{1}^{\prime}(<P)$.

If $\widehat{\operatorname{Supp}(P)}$ only contains Type II local digraph
around $\alpha_{k}$, $p_{1}$ is not a digraph map, since

$\alpha_{k+2}^{2}\rightarrow\alpha_{k},\quad\alpha_{k+2}^{3}\nrightarrow\alpha_{k-1}.$

But we still have

$(p_{1})_{*}(P)=P_{1}^{\prime},~{}\mod\text{ (non-allowed paths)}.$

To obtain the singular cubical realization of $P_{1}^{\prime}$, let us modify
$f:I^{\boxdot n}\rightarrow\operatorname{Supp}(P)$ as follows. Note that the
triangle with vertices

$\\{\alpha_{k+2}^{2},~{}\alpha_{k+1}^{3},~{}\alpha_{k}\\}$

must be realized by a digraph map from the square. Without loss of generality,
for convenience, assume it is realized by
$f\big{|}_{(\epsilon_{1},\ldots,\epsilon_{n-2})\boxdot I^{\boxdot 2}}$. That
is, let us write $\epsilon^{\prime}=(\epsilon_{1},\ldots,\epsilon_{n-2})$, the
restriction map is given by exactly one of the following four cases.

$\displaystyle f((\epsilon^{\prime},0,0))=\alpha_{k+2}^{2},\quad
f((\epsilon^{\prime},1,0))=\alpha_{k+2}^{2},$ $\displaystyle
f((\epsilon^{\prime},0,1))=\alpha_{k+1}^{3},\quad
f((\epsilon^{\prime},1,1))=\alpha_{k};$

or

$\displaystyle f((\epsilon^{\prime},0,0))=\alpha_{k+2}^{2},\quad
f((\epsilon^{\prime},1,0))=\alpha_{k},$ $\displaystyle
f((\epsilon^{\prime},0,1))=\alpha_{k+1}^{3},\quad
f((\epsilon^{\prime},1,1))=\alpha_{k};$

or the other two maps induced by the automorphism of the square.

For all the four cases, let us modify $f$ to be

$\displaystyle f^{\prime}:$ $\displaystyle~{}I^{\boxdot
n}\rightarrow\operatorname{Supp}(P)$ $\displaystyle
f^{\prime}((\epsilon^{\prime},1,0))=f^{\prime}((\epsilon^{\prime},0,1))=\alpha_{k+1}^{3};$
$\displaystyle f^{\prime}(v)=f(v),\quad\text{for
}v\neq(\epsilon^{\prime},1,0),(\epsilon^{\prime},0,1).$

If there are other edges $a\rightarrow b$ in $I^{\boxdot n}$ mapping to
$\alpha_{k+2}^{2}\rightarrow\alpha_{k}$ via $f$, similarly, modify it locally
to $f^{\prime}$:

$f^{\prime}(a)=f(a)=\alpha_{k+2}^{2},\quad f^{\prime}(b)=\alpha_{k+1}^{3}.$

Then, one can easily check that $f^{\prime}\circ p_{1}$ gives the singular
cubical realization of $P_{1}^{\prime}$. That is,

  * •

$f^{\prime}\circ p_{1}:I^{\boxdot
n}\rightarrow\operatorname{Supp}(P_{1}^{\prime})$ is a digraph map;

  * •

$(f^{\prime}\circ p_{1})_{*}(\omega_{n})=cP_{1}^{\prime}$, where $c$ is the
same as above.

Now if $\widehat{\operatorname{Supp}(P)}$ contain both Type I and Type II
local digraphs around $\alpha_{k}$, there must be
$\alpha_{k+2}^{1}\neq\alpha_{k+2}^{2}$, then $f^{\prime}$ will have no effect
on Type I case. Thus, the modification $f^{\prime}$ still works.

In summary, we construct a singular cubical realization of $P_{1}^{\prime}$
which has elementary path components less than $m$. By Hypothesis, for any
$\tilde{P}_{1}^{\prime}\in\mathcal{P}_{n}(G)$, $\tilde{P}_{1}^{\prime}\leq
P_{1}^{\prime}$, we have
$\tilde{P}_{1}^{\prime}\in\mathcal{P}_{\operatorname{adm},n}(G)$. Now any
$P^{\prime}\in\mathcal{P}_{n}(G)$ with $P^{\prime}<P$, it could be first
realized as some $P_{1}^{\prime}$ or a smaller path, and then we obtain a
singular cubical realization for $P^{\prime}$. We are done. ∎

For the coincidence of $\partial^{\operatorname{cell}}$ and $\partial$, we
still need the following unique decomposition result.

######  Lemma 3.32.

Let $P\in\mathcal{P}(G)$ and $R$ be a minimal path (of arbitrary length) in
$\operatorname{Supp}(P)$, if $R$ is not minimal in $G$, it admits the
following unique decomposition (up to the summation order) in $G$:

(3.6) $R=R_{1}+R_{2}+\cdots+R_{k},\quad
R_{i}\in\mathcal{P}(G),~{}R_{i}<R,~{}i=1,2,\ldots,k.$

In other words, there do not exist admissible relations among
$\\{R_{i}\in\mathcal{P}_{n}(G)|R_{i}<R\\}$.

###### Proof.

The proof is done by induction on the length of $R$. For the case of
length-$0$ and length-$1$, it’s obvious; and the length-2 result follows from
the structure theorem 2.10 (3). Assume the result holds for the case of
length-$(n-1)$. Now, let $R$ be a length-$n$ minimal path in
$\operatorname{Supp}(P)$. First we have

$R=\sum_{\alpha\in E_{1}}R_{\alpha}E,$

where $R_{\alpha}\in\mathcal{P}_{n-1}(\operatorname{Supp}(P))$ with the ending
vertex $\alpha$. By hypothesis, we can decompose $R_{\alpha}$ in $G$ and write
$R$ as

$R=\sum_{\alpha\in E_{1}}\sum_{i\in I}R_{\alpha,i}E.$

Now if $R$ admits two different decompositions up to the summation order

(3.7) $\displaystyle R=R_{1}+R_{2}+\cdots+R_{k},\qquad
R_{i}\in\mathcal{P}_{n}(G),~{}R_{i}<R,~{}i=1,2,\ldots,k;$ $\displaystyle
R=R_{1}^{\prime}+R_{2}^{\prime}+\cdots+R_{l}^{\prime},\qquad
R_{j}^{\prime}\in\mathcal{P}_{n}(G),~{}R_{j}^{\prime}<R,~{}j=1,2,\ldots,l.$

Without loss of generality, assume that $R_{1}\neq R_{j}^{\prime}$, for any
$j=1,2,\ldots,l$. And we can expand $R_{1}$ as

$R_{1}=\sum_{\alpha\in A\subset E_{1}}\sum_{i\in I^{\prime}\subset
I}R_{\alpha,i}E.$

Since the decomposition for $R_{\alpha}$ in $G$ is unique, by (3.7), for any
$\alpha\in A$ and $i\in I_{1}$, $R_{\alpha,i}E$ is also a component in some
$R_{j}^{\prime}$. We can also expand $R_{j}^{\prime}$ as

$R_{1}=\sum_{\alpha\in A^{\prime}\subset E_{1}}\sum_{i\in
I^{\prime\prime}\subset I}R_{\alpha,i}E$

Assume that there exists $\beta$ in $R_{\alpha,i}$, such that

$\beta\rightarrow\alpha,\quad\beta\nrightarrow E.$

(Otherwise $R_{\alpha,i}E\in\mathcal{P}_{n}$, the minimal conditions for
$R_{1}$ and $R_{j}^{\prime}$ imply that $R_{1}=R_{j}^{\prime}=R_{\alpha,i}$,
contradiction.) Then $R_{1},R_{j}\in\mathcal{P}_{n}(G)$ imply that there exist
path components $R_{\alpha^{\prime},i^{\prime}}$ in $R_{1}$ and
$R_{\alpha^{\prime\prime},i^{\prime\prime}}$ in $R_{j}^{\prime}$ such that

$\beta\rightarrow\alpha^{\prime},\quad\beta\rightarrow\alpha^{\prime\prime}.$

If $\alpha^{\prime}\neq\alpha^{\prime\prime}$, then $R_{1}$, $R_{j}<R$ and $R$
is a minimal path in $\operatorname{Supp}(P)$ imply that
$\operatorname{Supp}(P)$ contains the following subgraph

$\beta$
---
$\alpha$
---
$\alpha^{\prime\prime}$
---
$E$
---
$\alpha^{\prime}$
---

It contradicts with the structure of $\operatorname{Supp}(P)$. Then
$\alpha^{\prime}=\alpha^{\prime\prime}$. Furthermore, the unique
decompositions of all $R_{\alpha}$’s imply that $i^{\prime\prime}=i^{\prime}$.
Thus,

$R_{\alpha^{\prime},i^{\prime}}=R_{\alpha^{\prime\prime},i^{\prime\prime}}.$

Continuing the discussion, one can obtain two $\partial$-invariant completions
$\widetilde{R_{1}}$, $\widetilde{R_{j}^{\prime}}$ of
$R_{\alpha,i}+R_{\alpha^{\prime},i^{\prime}}$ in $R_{1}$ and $R_{j}^{\prime}$.
Applying the same argument, we obtain

$R_{1}=\widetilde{R_{1}}=\widetilde{R_{j}^{\prime}}=R_{j}^{\prime},$

contradiction. Thus, the required decomposition is unique. ∎

######  Corollary 3.33.

For any $n\geq 1$, $P\in\mathcal{P}_{\operatorname{adm},n}(G)$, $\partial P$
admits a representation which coincides with
$\partial^{\operatorname{cell}}P$.

###### Proof.

First, the decomposition of $\partial P$ in $\operatorname{Supp}(P)$ is
unique. We write $\partial P$ as

$\partial P=Q_{1}+Q_{2}+\cdots+Q_{k},\quad
Q_{i}\in\mathcal{P}_{\operatorname{adm},n-1}(\operatorname{Supp}(P)).$

Now we consider all the paths $Q_{i}$ in $G$. If $Q_{i}$ is not minimal in
$G$, by Lemma 3.32, we have the unique decomposition for $Q_{i}$ as follows:

(3.8) $Q_{i}=\sum_{r=1}^{k_{i}}Q_{ir},\quad
Q_{ir}\in\mathcal{P}_{n-1}(G),~{}Q_{ir}<Q_{i}.$

By Lemma 3.29, we have $Q_{ir}\in\mathcal{P}_{\operatorname{adm},n-1}(G)$.

According to the definition of $\partial^{\operatorname{cell}}P$, the
uniqueness of the decomposition implies that the admissible paths
$\\{Q_{ir}\\}_{i,r}$ are all the summands in
$\partial^{\operatorname{cell}}P$. It follows that

$\partial^{\operatorname{cell}}P=\sum_{i,r}Q_{ir}=\partial P.\qed$

###### Proof of Proposition 3.27.

Assume that $P_{1},\ldots,P_{k}\in\mathcal{P}_{\operatorname{adm},n}(G)$
satisfy the admissible (linear) relations, which we write it as

(3.9) $P_{k}=\sum_{i=1}^{k-1}c_{i}P_{i},\quad c_{i}\in\mathbb{R}.$

First, by Corollary 3.33, for each
$P_{i}\in\mathcal{P}_{\operatorname{adm},n}(G)$ in the relation, we have

$\partial^{\operatorname{cell}}P_{i}=\sum_{r}Q_{ir}=\partial P_{i}.$

Then on the one hand, by $\mathbb{R}$-linear extension,

$\partial^{\operatorname{cell}}\left(\sum_{i=1}^{k-1}c_{i}P_{i}\right)=\sum_{i=1}^{k-1}c_{i}\partial^{\operatorname{cell}}P_{i}=\sum_{i=1}^{k-1}c_{i}\sum_{r}Q_{ir}=\partial\left(\sum_{i=1}^{k-1}c_{i}P_{i}\right);$

on the other hand,

$\partial^{\operatorname{cell}}P_{k}=\sum_{r}Q_{kr}=\partial P_{k}.$

It follows from the condition
$Q_{ir}\in\mathcal{P}_{\operatorname{adm},n-1}(G)$ and the relation (3.9) that

$\partial P_{k}=\partial\left(\sum_{i=1}^{k-1}c_{i}P_{i}\right)$

imply the admissible relations among $\\{Q_{ir}\\}_{i=1,\ldots,k;r}$

$\partial^{\operatorname{cell}}P_{k}=\sum_{r}Q_{kr}=\sum_{i=1}^{k-1}c_{i}\sum_{r}Q_{ir}=\partial^{\operatorname{cell}}\left(\sum_{i=1}^{k-1}c_{i}P_{i}\right).$

Thus, we obtain a well-defined operator, still denoted by
$\partial^{\operatorname{cell}}$, on the cellular chain group

$\partial^{\operatorname{cell}}:C_{n}(G;\mathbb{R})\longrightarrow
C_{n-1}(G;\mathbb{R}).$

Its relation with the boundary operator $\partial$ of path complex implies
that $\partial^{\operatorname{cell}}$ is a boundary operator. ∎

######  Definition 3.34.

Let $G$ be a digraph. For any $n\in\mathbb{N}$, the $n$-th cellular homology
of $G$ is defined to be

$H_{n}^{\operatorname{cell}}(G;\mathbb{R})=\frac{\ker\\{\partial_{n}^{\operatorname{cell}}:C_{n}(G;\mathbb{R})\longrightarrow
C_{n-1}(G;\mathbb{R})\\}}{\operatorname{im}\\{\partial_{n+1}^{\operatorname{cell}}:C_{n+1}(G;\mathbb{R})\longrightarrow
C_{n}(G;\mathbb{R})\\}}.$

######  Example 3.35.

We can compute the cellular homologies of the above several digraphs.

  1. (1)

For the $k$-square digraph $S_{k}$ in Example 3.21, it has trivial cellular
homologies for $n\geq 1$ and
$H^{\operatorname{cell}}_{0}(S_{k};\mathbb{R})\cong\mathbb{R}$.

  2. (2)

For the exotic cube, we have

$H_{n}^{\operatorname{cell}}(\mbox{exotic
cube};\mathbb{R})\cong\left\\{\begin{array}[]{ll}\mathbb{R},&\hbox{$n=0,2$;}\\\
0,&\hbox{others.}\end{array}\right.$

  3. (3)

For the supporting digraph of the path $P$,

$\displaystyle P=~{}$ $\displaystyle e_{S159E}-e_{S169E}+e_{S269E}$
$\displaystyle+e_{S16(10)E}-e_{S26(10)E}+e_{S27(10)E}-e_{S37(10)E}$
$\displaystyle-e_{S27(11)E}+e_{S37(11)E}-e_{S38(11)E}+e_{S48(11)E},$

i.e. the digraph in Example 2.9, according to the analysis of its admissible
paths in $\operatorname{Supp}(P)$, i.e. Example 3.19, we have

$H_{n}^{\operatorname{cell}}(\operatorname{Supp}(P);\mathbb{R})\cong\left\\{\begin{array}[]{ll}\mathbb{R},&\hbox{$n=0$;}\\\
0,&\hbox{others.}\end{array}\right.$

###  3.4. Properties of cellular homology associated to the digraph

In this subsection, we will discuss several properties of our cellular
homology associated to the digraph, which include homotopy invariance (in a
narrow case), acyclic model and Künneth formula for Cartesian product of
digraphs.

####  3.4.1. Homotopy invariance

Let us recall basic homotopy theory of digraphs developed in [10].

Fix $n\geq 0$. Denote by $I_{n}$ any digraph, with
$V(I_{n})=\\{0,1,\ldots,n\\}$ and $E(I_{n})$ containing exactly one of the
edges $i\rightarrow i+1$, $i+1\rightarrow i$ for any $i=0,1,\ldots,n-1$. We
call it the line digraph.

######  Definition 3.36 (Homotopy).

Let $G$, $H$ be two digraphs.

  1. (1)

Two digraph maps $f,g:G\rightarrow H$ are called homotopic if there exists a
line digraph $I_{n}$ for some $n\geq 1$ and a digraph map $F:G\boxdot
I_{n}\rightarrow H$, such that

$F\big{|}_{G\boxdot\\{0\\}}=f\quad\text{and}\quad
F\big{|}_{G\boxdot\\{n\\}}=g.$

We shall write $f\overset{F}{\simeq}g$ (or simply $f\simeq g$) and call $F$ a
$n$-step homotopy between $f$ and $g$.

  2. (2)

Two digraphs $G$ and $H$ are called homotopy equivalent if there exist digraph
maps

$f:G\rightarrow H,\quad g:H\rightarrow G$

such that

$f\circ g\simeq\operatorname{Id}_{H},\quad g\circ
f\simeq\operatorname{Id}_{G}.$

######  Theorem 3.37 (Homotopy invariance of path complex[10]).

Let $G$, $H$ be two digraphs.

  1. (1)

Let $f\simeq g:G\rightarrow H$ be two homotopic digraph maps. Then these maps
induce the identical homomorphisms of path homologies of $G$ and $H$:

$f_{*}=g_{*}:H_{*}(G)\rightarrow H_{*}(H).$

  2. (2)

If the digraphs $G$ and $H$ are homotopy equivalent, then they have isomorphic
path homologies.

The proof is first done for one-step homotopy $f\overset{F}{\simeq}g$ and then
by induction on the step of the homotopy. The key point there is to construct
the chain homotopy

$L_{p}:\Omega_{p}(G)\rightarrow\Omega_{p+1}(H),\quad p\geq 0$

such that

$\partial L_{p}+L_{p-1}\partial=g_{*}-f_{*}.$

The answer is given by

$L_{p}(v)=F_{*}(v\times e_{01}),$

where $\times$ is the cross product of paths, which will be recalled in
Definition 3.44.

Now let us return to cellular homologies of digraphs in a narrow sense that
the digraph $G$ does not contain a monotone cycle.

######  Lemma 3.38.

Let $G$, $H$ be two digraphs with no monotone cycles. If $f:G\rightarrow H$ is
a digraph map, then it induces a chain map

$f_{*}:C_{*}(G;\mathbb{R})\rightarrow C_{*}(H;\mathbb{R}).$

###### Proof.

Let $P\in\mathcal{P}_{\operatorname{adm},n}(G)$, and $\phi:I^{\boxdot
n}\rightarrow G$ be its singular cubical realization. Then

$f_{*}(P)=c^{-1}f_{*}\phi_{*}(\omega_{n})=c^{-1}(f\circ\phi)_{*}(\omega_{n}),\quad\text{for
some }c\in\mathbb{Z}\setminus\\{0\\}.$

It means that $f_{*}(P)$ admits a singular cubical realization. Furthermore,
any $Q\in\mathcal{P}_{n}(H)$, with $Q<f_{*}(P)$, we have
$Q\in\mathcal{P}_{\operatorname{adm},n}(H)$. Thus, $f_{*}(P)\in
C_{*}(H;\mathbb{R})$. ∎

######  Remark 3.39.

It is worth to mention that the digraph map is not a cellular map, that is, we
do not have $f_{*}(P)\in\mathcal{P}_{\operatorname{adm},n}(H)$.

######  Lemma 3.40.

If $c\in\mathcal{P}_{\operatorname{adm},p}(G)$, we have

$v\times e_{01}\in\mathcal{P}_{\operatorname{adm},p+1}(G\boxdot I).$

###### Proof.

We will prove the general case in Lemma 3.48, which states as follows: if
$P\in\mathcal{P}_{\operatorname{adm},p}(X)$,
$Q\in\mathcal{P}_{\operatorname{adm},q}(Y)$, then

$P\times Q\in\mathcal{P}_{\operatorname{adm},p+q}(X\boxdot Y).$

∎

Following from Lemmas 3.38, 3.40 and the same proof in the path complex, the
above $L_{p}$ gives the chain homotopy between $C_{*}(G;\mathbb{R})$ and
$C_{*}(H;\mathbb{R})$. Thus we obtain the homotopy invariance of cellular
homology of digraphs.

######  Theorem 3.41.

Let $G$, $H$ be two digraphs with no monotone cycles.

  1. (1)

Let $f\simeq g:G\rightarrow H$ be two homotopic digraph maps. Then

$f_{*}=g_{*}:H_{*}^{\operatorname{cell}}(G;\mathbb{R})\rightarrow
H_{*}^{\operatorname{cell}}(H;\mathbb{R}).$

  2. (2)

If the digraphs $G$ and $H$ are homotopy equivalent, then they have isomorphic
cellular homologies.

####  3.4.2. Acyclic result for
$\widetilde{H}^{\operatorname{cell}}_{*}(\operatorname{Supp}(P);\mathbb{R})$
for $P\in\mathcal{P}_{\operatorname{adm}}(G)$

One can define the reduced cellular homologies
$\tilde{H}_{*}^{\operatorname{cell}}(G;\mathbb{R})$ of $G$ in the usual way by
modifying $H_{0}^{\operatorname{cell}}(G;\mathbb{R})$ to be

$\widetilde{H}_{0}^{\operatorname{cell}}(G;\mathbb{R})=\ker\\{\partial^{\operatorname{cell}}_{0}:C^{\operatorname{cell}}_{0}(G;\mathbb{R})\rightarrow\mathbb{R}\\}/\operatorname{im}\\{\partial_{1}^{\operatorname{cell}}:C_{1}^{\operatorname{cell}}(G;\mathbb{R})\rightarrow
C_{0}^{\operatorname{cell}}(G;\mathbb{R})\\}.$

where

$\partial^{\operatorname{cell}}_{0}:C^{\operatorname{cell}}_{0}(G;\mathbb{R})\rightarrow\mathbb{R},\quad\partial^{\operatorname{cell}}_{0}\left(\sum_{a\in
V(G)}c_{a}a\right)=\sum_{a\in V(G)}c_{a}.$

It follows from Theorem 2.11 and the relation between path complex and
cellular chain complex associated to the digraph, we obtain

######  Proposition 3.42.

For $P\in\mathcal{P}_{\operatorname{adm}}(G)$, we have

$\widetilde{H}_{*}^{\operatorname{cell}}(\operatorname{Supp}(P);\mathbb{R})=0.$

We list all the admissible minimal $3$-paths in Appendix A. In particular, we
check that all the corresponding supporting digraphs are contractible, which
fits our motivation. Thus, we propose the following conjecture and will have a
deep study on it in a separation paper.

######  Conjecture 3.43.

For any $n\geq 0$ and $P\in\mathcal{P}_{\operatorname{adm},n}(G)$, the digraph
$\operatorname{Supp}(P)$ is contractible.

####  3.4.3. Künneth formula

In this subsection, we will study the cellular chain structure of the
Cartesian product of digraphs.

######  Definition 3.44 (Cross product).

Let $X$, $Y$ be two digraphs. For any s-regular allowed elementary $p$-path
$e_{x}$ in $X$ and $q$-path $e_{y}$ in $Y$, the cross product $e_{x}\times
e_{y}$ is defined as a $(p+q)$-path in $X\boxdot Y$ by

$e_{x}\times e_{y}=\sum_{z\in\Sigma_{x,y}}(-1)^{L(z)}e_{z},$

where $\Sigma_{x,y}$ is the set of all stair-like paths $z$ on $X\boxdot Y$
whose projections on $X$ and $Y$ are respectively $x$ and $y$, $L(z)$ is the
number of cells in $\mathbb{N}_{+}^{2}$ below the staircase $S(z)$, see the
following picture333We refer to the picture in [13]. for an explanation.

######  Example 3.45.

Let $a,b\in V(X)$, $1,2\in V(Y)$, we have

  1. (1)

$e_{a}\times e_{12}=e_{(a1)(a2)}$, $e_{ab}\times e_{1}=e_{(a1)(b1)}$;

  2. (2)

$e_{ab}\times e_{12}=e_{(a1)(b1)(b2)}-e_{(a1)(a2)(b2)}$.

The following results are useful for our proof.

######  Lemma 3.46 ([13]).

Let $X$, $Y$ be two digraphs.

  1. (1)

The cross product extends by linearity to the vector space of paths. For
$u\in\Omega_{p}(X)$, and $v\in\Omega_{q}(Y)$, we have $u\times
v\in\Omega_{p+q}(X\boxdot Y)$. The boundary operator $\partial$ is compatible
with the cross product in the following way:

$\partial(u\times v)=(\partial u)\times v+(-1)^{p}u\times(\partial v).$

In particular, if $X=I^{\boxdot p}$ and $Y=I^{\boxdot q}$, then

$\omega_{p}\times\omega_{q}=\omega_{p+q}\in\Omega_{p+q}(I^{\boxdot(p+q)};\mathbb{Z}).$

  2. (2)

Any $\omega\in\Omega_{*}(X\boxdot Y)$ admits a representation

$\omega=\sum_{e_{y}\in E_{*}(Y)}u^{y}\times e_{y},\quad
u^{y}\in\Omega_{*}(X),$

where $E_{*}(Y)=\cup_{q\geq 0}E_{q}(Y)$, with $E_{q}(Y)$ being the set of all
s-regular allowed elementary $q$-paths in $Y$.

######  Remark 3.47.

In [13], the authors work with the coefficient being the field $\mathbb{K}$.
But the above lemma also works for the $\mathbb{Z}$-coefficient. In
particular, any $\omega\in\Omega_{*}(X\boxdot Y;\mathbb{Z})$ admits a
representation

$\omega=\sum_{e_{y}\in E_{*}(Y)}u^{y}\times e_{y},\quad
u^{y}\in\Omega_{*}(X;\mathbb{Z}),$

since for different $e_{y_{1}}$, $e_{y_{2}}\in E_{*}(Y)$, if we represent
$u^{y_{i}}\times e_{y_{i}}$ in terms of elementary paths uniquely, then the
corresponding two sets of elementary paths have empty intersections:

$E(u^{y_{1}}\times e_{y_{1}})\cap E(u^{y_{2}}\times e_{y_{2}})=\emptyset.$

Here, we expect a more restricted result. That is

######  Lemma 3.48.

For any $P\in\mathcal{P}_{\operatorname{adm},p}(X)$ and
$Q\in\mathcal{P}_{\operatorname{adm},q}(Y)$, we have

$P\times Q\in\mathcal{P}_{\operatorname{adm},p+q}(X\boxdot Y).$

###### Proof.

By definition, we need to prove

  1. (1)

$P\times Q$ is minimal in $X\boxdot Y$;

  2. (2)

$P\times Q$ has a singular cubical realization.

(1) Let $R=P\times Q\in\Omega_{k}(X\boxdot Y;\mathbb{Z})$, $k=p+q$. Since
$Q\in\mathcal{P}_{\operatorname{adm},q}(Y)\subset\mathcal{P}_{q}(Y)$, then we
can write $Q=\sum_{e_{y}\in E_{q}(Y)}\epsilon_{y}e_{y}$, where
$\epsilon_{y}=0$, $1$ or $-1$. Thus,

$R=P\times Q=\sum_{e_{y}\in E_{q}(Y)}P\times\epsilon_{y}e_{y}=\sum_{e_{y}\in
E_{q}(Y)}\epsilon_{y}P\times e_{y}.$

Assume that $R$ is not minimal, that is, there exists a path
$\hat{R}\in\Omega_{k}(X\boxdot Y;\mathbb{Z})$ such that $\hat{R}<R$.

By Lemma 3.46(2) and Remark 3.47, $\hat{R}$ admits a representation

$\hat{R}=\sum_{e_{y}\in E_{q}(Y)}\hat{R}^{y}\times
e_{y},\quad\hat{R}^{y}\in\Omega_{p}(X;\mathbb{Z}).$

For different $e_{y}$ and any path $u$, $u\times e_{y}$’s have non-
intersection sets of elementary paths, then $\hat{R}<R$ implies

$\hat{R}^{y}\leq\epsilon_{y}P.$

  * •

If $\epsilon_{y}=0$, then $\hat{R}^{y}=0$.

  * •

If $\epsilon_{y}=\pm 1$, since $P$ is minimal, then $\hat{R}^{y}=0$ or
$\hat{R}^{y}=\epsilon_{y}P$.

Thus we write

$\hat{R}^{y}=\epsilon_{y}^{\prime}P:=\left\\{\begin{array}[]{ll}\epsilon_{y}P,&\hbox{if
$\hat{R}^{y}=\epsilon_{y}P$;}\\\ 0,&\hbox{if
$\hat{R}^{y}<\epsilon_{y}P$.}\end{array}\right.$

Now, we can write $\hat{R}$ as follows:

$\hat{R}=\sum_{e_{y}\in E_{q}(Y)}\hat{R}^{y}\times e_{y}=\sum_{e_{y}\in
E_{q}(Y)}\epsilon_{y}^{\prime}P\times e_{y}=\sum_{e_{y}\in
E_{q}(Y)}P\times\epsilon_{y}^{\prime}e_{y}.$

Since $\hat{R}\in\Omega_{k}(X\boxdot Y;\mathbb{Z})$, by Lemma 3.46 (1), we
have

$\partial\hat{R}=(\partial P)\times\sum_{e_{y}\in
E_{q}(Y)}\epsilon_{y}^{\prime}e_{y}+(-1)^{p}P\times\partial\bigg{(}\sum_{e_{y}\in
E_{q}(Y)}\epsilon_{y}^{\prime}e_{y}\bigg{)}\in\mathcal{A}_{k-1}(X\boxdot
Y,\mathbb{Z}).$

Combining with the conditions $P\in\Omega_{p}(X;\mathbb{Z})$ and
$\sum_{e_{y}\in
E_{q}(Y)}\epsilon_{y}^{\prime}e_{y}\in\mathcal{A}_{q}(Y;\mathbb{Z})$, we
obtain

$\partial\bigg{(}\sum_{e_{y}\in
E_{q}(Y)}\epsilon_{y}^{\prime}e_{y}\bigg{)}\in\mathcal{A}_{q-1}(Y;\mathbb{Z}).$

Thus, $\sum_{e_{y}\in
E_{q}(Y)}\epsilon_{y}^{\prime}e_{y}\in\Omega_{q}(Y;\mathbb{Z})$. It further
implies

$\sum_{e_{y}\in E_{q}(Y)}\epsilon_{y}^{\prime}e_{y}<Q,$

contradiction. Thus $P\times Q$ is minimal.

(2) Since $P$ and $Q$ are admissible, there exist singular cubical
realizations

$f:I^{\boxdot p}\longrightarrow\operatorname{Supp}(P)\subset X,\qquad
g:I^{\boxdot q}\longrightarrow\operatorname{Supp}(Q)\subset Y.$

Now we define a map

$h:I^{\boxdot(p+q)}\longrightarrow X\boxdot Y$

as follows:

$h(a,b)=(f(a),g(b)),\quad a\in V(I^{\boxdot p}),~{}b\in V(I^{\boxdot q}).$

It is easy to check that $h$ is a digraph map by definition of the Cartesian
product. It remains to prove that $h$ gives a singular cubical realization of
$P\times Q$.

######  Claim 3.49.

For any allowed elementary $p$-path $e_{p}=e_{i_{0}i_{1}\cdots i_{p}}$ in
$I^{\boxdot p}$, $q$-path $e_{q}=e_{j_{0}j_{1}\cdots j_{q}}$ in $I^{\boxdot
q}$, we have

$h_{*}(e_{p}\times e_{q})=f_{*}(e_{p})\times g_{*}(e_{q}).$

By definition, we have

$\displaystyle h_{*}(e_{p}\times e_{q})=~{}$ $\displaystyle
h_{*}\left(\sum_{(i_{0},j_{0})\cdots(i_{p},j_{q})\in\Sigma_{p,q}}(-1)^{L((i_{0},j_{0})\cdots(i_{p},j_{q}))}e_{(i_{0},j_{0})\cdots(i_{p},j_{q})}\right)$
$\displaystyle=~{}$
$\displaystyle\sum_{(i_{0},j_{0})\cdots(i_{p},j_{q})\in\Sigma_{p,q}}(-1)^{L((i_{0},j_{0})\cdots(i_{p},j_{q}))}e_{(f(i_{0}),g(j_{0}))\cdots(f(i_{p}),g(j_{q}))}.$

If there exist $i_{k}$ and $i_{k+1}$ such that $f(i_{k})=f(i_{k+1})$, then

  * •

$f_{*}(e_{p})=0$;

  * •

$(f(i_{k}),g(j_{l}))=(f(i_{k+1}),g(j_{l}))$, for any $l=0,1\ldots,q$.

Thus,

$h_{*}(e_{p}\times e_{q})=0=f_{*}(e_{p})\times g_{*}(e_{q}).$

Similar argument holds for the case $g(j_{l})=g(j_{l+1})$ for some $l$.

If $f_{*}(e_{p})$ and $g_{*}(e_{q})$ do not vanish, then there is a bijection
between $\Sigma_{p,q}$ and $\Sigma_{f_{*}(p),f_{*}(q)}$ given by

$(i_{0},j_{0})\cdots(i_{p},j_{q})\in\Sigma_{p,q}~{}\leftrightarrow~{}(f(i_{0}),g(j_{0}))\cdots(f(i_{p}),g(j_{q}))\in\Sigma_{f_{*}(p),g_{*}(q)}$

and moreover

$L((i_{0},j_{0})\cdots(i_{p},j_{q}))=L((f(i_{0}),g(j_{0}))\cdots(f(i_{p}),g(j_{q}))),$

since the staircases on both sides have the same shape. Thus, we can continue
the computation

$\displaystyle h_{*}(e_{p}\times e_{q})=~{}$
$\displaystyle\sum_{(f(i_{0}),g(j_{0}))\cdots(f(i_{p}),g(j_{q}))\in\Sigma_{f_{*}(p),g_{*}(q)}}(-1)^{L((i_{0},j_{0})\cdots(i_{p},j_{q}))}e_{(f(i_{0}),g(j_{0}))\cdots(f(i_{p}),g(j_{q}))}$
$\displaystyle=~{}$
$\displaystyle\sum_{(f(i_{0}),g(j_{0}))\cdots(f(i_{p}),g(j_{q}))\in\Sigma_{f_{*}(p),g_{*}(q)}}(-1)^{L((f(i_{0}),g(j_{0}))\cdots(f(i_{p}),g(j_{q})))}e_{(f(i_{0}),g(j_{0}))\cdots(f(i_{p}),g(j_{q}))}$
$\displaystyle=~{}$ $\displaystyle e_{f(i_{0})\cdots f(i_{p})}\times
e_{g(j_{0})\cdots g(j_{q})}$ $\displaystyle=~{}$ $\displaystyle
f_{*}(e_{p})\times g_{*}(e_{q}).$

Since $h_{*}$, $f_{*}$ and $g_{*}$ are linear maps, we get

$h_{*}(\omega_{p+q})=h_{*}(\omega_{p}\times\omega_{q})=f_{*}(\omega_{p})\times
g_{*}(\omega_{q})=c_{P}P\times c_{Q}Q,\quad
c_{P},c_{Q}\in\mathbb{Z}\setminus\\{0\\}.$

Note that the image digraph of $h$ is given by
$\operatorname{Supp}(P)\boxdot\operatorname{Supp}(Q)$ and

$P\times
Q\in\Omega_{p+q}(\operatorname{Supp}(P)\boxdot\operatorname{Supp}(Q)),$

thus

$\operatorname{Supp}(P\times
Q)\subset\operatorname{Supp}(P)\boxdot\operatorname{Supp}(Q).$

Conversely, any edge
$e_{ij}\in\mathcal{A}_{1}(\operatorname{Supp}(P)\boxdot\operatorname{Supp}(Q))$,
it is of the form

$e_{(i_{0},j_{0})(i_{0},j_{1})}\quad\text{or}\quad
e_{(i_{0},j_{0})(i_{1},j_{0})}.$

Meanwhile,

$\displaystyle
e_{(i_{0},j_{0})(i_{0},j_{1})}\in\mathcal{A}_{1}(\\{i_{0}\\}\boxdot\operatorname{Supp}(Q))=\mathcal{A}_{1}(\operatorname{Supp}(\\{i_{0}\\}\times
Q))\subset\mathcal{A}_{1}(\operatorname{Supp}(P\times Q));$ $\displaystyle
e_{(i_{0},j_{0})(i_{1},j_{0})}\in\mathcal{A}_{1}(\operatorname{Supp}(P)\boxdot\\{j_{0}\\})=\mathcal{A}_{1}(\operatorname{Supp}(P\times\\{j_{0}\\}))\subset\mathcal{A}_{1}(\operatorname{Supp}(P\times
Q)).$

Then

$\operatorname{Supp}(P)\boxdot\operatorname{Supp}(Q)=\bigcup_{e_{ij}\in\mathcal{A}_{1}(\operatorname{Supp}(P)\boxdot\operatorname{Supp}(Q))}\\{i\rightarrow
j\\}\subset\operatorname{Supp}(P\times Q).$

Thus, we have

$\operatorname{Supp}(P\times
Q)=\operatorname{Supp}(P)\boxdot\operatorname{Supp}(Q).$

∎

Combining with the above two lemmas, we obtain

######  Corollary 3.50.

For $u\in\mathcal{P}_{\operatorname{adm},p}(G)$ and
$v\in\mathcal{P}_{\operatorname{adm},q}(G)$, we have

$\partial^{\operatorname{cell}}(u\times
v)=\left(\partial^{\operatorname{cell}}u\right)\times
v+(-1)^{p}u\times\left(\partial^{\operatorname{cell}}v\right).$

######  Theorem 3.51 (Künneth formula).

For any digraphs $X$ and $Y$, any $n\geq 0$, we have

$C_{n}(X\boxdot Y;\mathbb{R})\cong\bigoplus_{p\geq 0,q\geq
0;~{}p+q=n}C_{p}(X;\mathbb{R})\otimes C_{q}(Y;\mathbb{R}).$

Moreover, we have

$H_{*}^{\operatorname{cell}}(X\boxdot Y;\mathbb{R})\cong
H_{*}^{\operatorname{cell}}(X;\mathbb{R})\otimes
H_{*}^{\operatorname{cell}}(Y;\mathbb{R}).$

###### Proof.

According to the proof of Lemma 3.48, any $R\in\mathcal{P}_{n}(X\boxdot Y)$
admits a decomposition

$R=P\times Q,\quad\text{for some
}P\in\mathcal{P}_{p}(X),~{}Q\in\mathcal{P}_{q}(Y),~{}p+q=n,$

and

$\operatorname{Supp}(R)=\operatorname{Supp}(P)\boxdot\operatorname{Supp}(Q).$

Now let us study the singular cubical realizations of $P$ and $Q$ for
$R\in\mathcal{P}_{\operatorname{adm},n}(X\boxdot Y)$. First, let

$h=(h_{1},h_{2}):I^{\boxdot
n}\rightarrow\operatorname{Supp}(R)=\operatorname{Supp}(P)\boxdot\operatorname{Supp}(Q)$

be a singular cubic realization of $R$, where

$h_{1}:I^{\boxdot n}\rightarrow\operatorname{Supp}(P),\quad h_{2}:I^{\boxdot
n}\rightarrow\operatorname{Supp}(Q).$

Note that there are $C_{p+q}^{p}$ kinds of embedding digraph maps

$i_{a}:I^{\boxdot p}\hookrightarrow I^{\boxdot(p+q)},\quad
a=1,2,\ldots,C_{p+q}^{p}$

with the remaining $q$ coordinates being $0$; corresponding the positions of
the remaining $q$ coordinates determine another embedding digraph maps

$j_{a}:I^{\boxdot q}\hookrightarrow I^{\boxdot(p+q)},\quad
a=1,2,\ldots,C_{p+q}^{p}$

with the remaining $p$ coordinates being $0$.

Via $i_{a}$, $j_{a}$ and $h$, we can define two digraph maps $f_{a}$ and
$g_{a}$ as follows

$\displaystyle f_{a}=h_{1}\circ i_{a}:I^{\boxdot p}\hookrightarrow
I^{\boxdot(p+q)}\rightarrow\operatorname{Supp}(P),$ $\displaystyle
g_{a}=h_{2}\circ j_{a}:I^{\boxdot q}\hookrightarrow
I^{\boxdot(p+q)}\rightarrow\operatorname{Supp}(Q).$

Let us denote $S_{P}$ (resp. $S_{Q}$) and $E_{P}$ (resp. $E_{Q}$) to be the
starting vertex and ending vertex of $P$ (resp. $Q$) respectively.

Next, let us analyze the properties of all $f_{a}$, $a=1,\ldots,C_{p+q}^{p}$
along the following steps. The argument for $g_{a}$ is the same.

  1. (1)

If $f_{a}(1,1,\ldots,1)\neq E_{P}$, then

    1. (a)

either $(f_{a})_{*}(\omega_{p})=0$,

    2. (b)

or $(f_{a})_{*}(\omega_{p})$ gives another non-$P$ element in
$\Omega_{p}(\operatorname{Supp}(P);\mathbb{Z})$, it is impossible.

  2. (2)

Let us consider the elementary path components going through $(E_{P},S_{Q})$
in $R$, that is, the paths start from $(S_{P},S_{Q})$ and then go along the
$X$-directions at the first $p$ steps. Then the condition
$h_{*}(\omega_{p+q})=R$ means that there must exist
$a\in\\{1,\ldots,C_{p+q}^{p}\\}$ such that

(3.10) $f_{a}(\underbrace{1,1,\ldots,1}_{p})=E_{P}.$

  3. (3)

We claim that there exists $a$ satisfying (3.10), such that
$(f_{a})_{*}(\omega_{p})\neq 0$. Then the minimal condition for $P$ implies
that $f_{a}$ gives a singular cubical realization for $P$. In fact, if all
$(f_{a})_{*}(\omega_{p})=0$ for $a$ satisfying (3.10), the vanishing here
means the complete cancellations of elementary $p$-paths in
$(f_{a})_{*}(\omega_{p})$. By comparing the relation between $f_{1}$ and $h$,
it also implies that there are not elementary path components in $R$ going
through $(E_{P},S_{Q})$, contradiction.

In summary, we have

$C_{n}(X\boxdot Y;\mathbb{R})=\operatorname{Span}_{\mathbb{R}}\\{u\times
v~{}\big{|}~{}u\in\mathcal{P}_{\operatorname{adm},p}(X),v\in\mathcal{P}_{\operatorname{adm},q}(Y)\\}/\\{\text{admissible
relations}\\}.$

Now, let us study the possibly admissible relations among
$\mathcal{P}_{\operatorname{adm},n}(X\boxdot Y)$. First, for
$R_{i}\in\mathcal{P}_{\operatorname{adm},n}(X\boxdot Y)$, write
$R_{i}=P_{i}\times Q_{i}$,
$P_{i}\in\mathcal{P}_{\operatorname{adm},p}(X),Q_{i}\in\mathcal{P}_{\operatorname{adm},q}(Y)$.
Assume we have the admissible (linear) relation in
$\mathcal{P}_{\operatorname{adm},n}(X\boxdot Y)$, and write it as

(3.11) $R_{k}=\sum_{i=1}^{k-1}a_{i}R_{i},\quad a_{i}\in\mathbb{R}.$

Moreover, we expand $Q_{i}$ as the linear combinations of s-regular allowed
elementary paths

$Q_{k}=\sum\epsilon_{q}e_{q},\quad\epsilon_{q}=1,\text{ or }-1.$

Then we can pick up the term $P_{i}\times\epsilon_{q}e_{q}$ on both sides of
(3.11), and obtain a linear relation among $\\{P_{i}\times e_{q}\\}$.
Similarly, we can expand $P_{k}$ and obtain a linear relation to express
$\epsilon_{p}e_{p}\times Q_{k}$.

Thus, we have an isomorphism

$C_{n}(X\boxdot Y;\mathbb{R})\cong\bigoplus_{p\geq 0,q\geq
0;~{}p+q=n}C_{p}(X;\mathbb{R})\otimes C_{q}(Y;\mathbb{R})$

which is given on the generators by

$R=P\times Q\longmapsto P\otimes Q.$

The remaining follow from Corollary 3.50 and the standard argument. ∎

##  4\. More Examples

###  4.1. The circulant graph

The so-called circulant graphs (also known as loop networks), has been much
studied. Let us recall the definition.

######  Definition 4.1.

Let $1\leq\gamma_{1}\leq\cdots\leq\gamma_{d}\leq\left[\frac{n}{2}\right]$ be
positive integers. A circulant graph $C_{n}^{\gamma_{1},\ldots,\gamma_{d}}$ is
the $2d$-regular graph with $n$ vertices labelled by $0,1\ldots,n-1$ such that
each vertex $\nu$ is connected to $\nu\pm\gamma_{i}$ $\mod n$ for all
$i\in\\{1,2,\cdots,d\\}$.

It is well known that each graph $C_{n}^{\Gamma}$ (where
$\Gamma=\\{1,\gamma_{2},\ldots,\gamma_{d}\\}$) is isomorphic to the
$d$-dimensional discrete torus $\mathbb{Z}^{d}/\Lambda_{\Gamma}\mathbb{Z}^{d}$
with $\Lambda_{\Gamma}$ being the $d\times d$ matrix:

$\displaystyle(\Lambda_{\Gamma})_{11}=n,\quad\Lambda_{1i}=-\gamma_{i},~{}i=2,3,\ldots,d$
$\displaystyle(\Lambda_{\Gamma})_{ij}=\delta_{ij},\quad
i=2,\ldots,d;~{}j=1,\ldots,d.$

######  Example 4.2 ($C_{5}^{1,2}$ and $C_{7}^{1,3}$).

The circulant graphs $C_{5}^{1,2}$ and $C_{7}^{1,3}$ are given as follows:

$1$
---
$2$
---
$3$
---
$4$
---
$0$
---
$0$
---
$1$
---
$2$
---
$3$
---
$4$
---
$5$
---
$6$
---

In our situation, we study the circulant graph as a digraph by considering the
directions of edges: for each $i=1,\ldots,d$,

$\nu-\gamma_{i}~{}\rightarrow~{}\nu~{}\rightarrow~{}\nu+\gamma_{i}\quad\mod
n.$

Then the above circulant graphs, which we still denote by $C_{5}^{1,2}$ and
$C_{7}^{1,3}$, become

$1$
---
$2$
---
$3$
---
$4$
---
$0$
---
$0$
---
$1$
---
$2$
---
$3$
---
$4$
---
$5$
---
$6$
---

Now, let us compute the cellular homologies of the digraphs $C_{5}^{1,2}$ and
$C_{7}^{1,3}$.

######  Example 4.3 (The digraph $C_{5}^{1,2}$).

For all $n\geq 0$, the sets of admissible paths
$\mathcal{P}_{\operatorname{adm},n}(C_{5}^{1,2})$, which are the same as the
sets of minimal paths $\mathcal{P}_{n}(C_{5}^{1,2})$, are given by

$\displaystyle\mathcal{P}_{\operatorname{adm},0}(C_{5}^{1,2})=\mathcal{P}_{0}(C_{5}^{1,2})=V(C_{5}^{1,2});$
$\displaystyle\mathcal{P}_{\operatorname{adm},1}(C_{5}^{1,2})=\mathcal{P}_{1}(C_{5}^{1,2})=E(C_{5}^{1,2});$
$\displaystyle\mathcal{P}_{\operatorname{adm},2}(C_{5}^{1,2})=\mathcal{P}_{2}(C_{5}^{1,2})=\\{e_{012},~{}e_{123},~{}e_{234},~{}e_{340},~{}e_{401},~{}e_{013}-e_{023},~{}e_{124}-e_{134},$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad
e_{230}-e_{240},~{}e_{301}-e_{341},~{}e_{402}-e_{412}\\};$
$\displaystyle\mathcal{P}_{\operatorname{adm},3}(C_{5}^{1,2})=\mathcal{P}_{3}(C_{5}^{1,2})=\\{e_{0123},~{}e_{1234},~{}e_{2340},~{}e_{3401},~{}e_{4012},~{}e_{0124}-e_{0134}+e_{0234},$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad
e_{1230}-e_{1240}+e_{1340},~{}e_{2341}-e_{2301}+e_{2401},$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad
e_{3402}-e_{3412}+e_{3012},~{}e_{4013}-e_{4023}+e_{4123}\\};$
$\displaystyle\mathcal{P}_{\operatorname{adm},4}(C_{5}^{1,2})=\mathcal{P}_{4}(C_{5}^{1,2})=\\{e_{01234},~{}e_{12340},~{}e_{23401},~{}e_{34012},~{}e_{40123}\\};$
$\displaystyle\mathcal{P}_{\operatorname{adm},n}(C_{5}^{1,2})=\mathcal{P}_{n}(C_{5}^{1,2})=0,\quad
n\geq 5.$

One can check that $\left(C_{5}^{1,2},\cup_{n=0}^{4}\mathcal{P}_{n}\right)$
gives the path complex structure as well as CW structure of $C_{5}^{1,2}$, due
to the absence of the admissible relations. After a careful calculation, we
have

$\displaystyle
H_{0}^{\operatorname{cell}}(C_{5}^{1,2};\mathbb{R})=H_{0}(C_{5}^{1,2};\mathbb{R})\cong\mathbb{R};$
$\displaystyle
H_{1}^{\operatorname{cell}}(C_{5}^{1,2};\mathbb{R})=H_{1}(C_{5}^{1,2};\mathbb{R})=\operatorname{Span}_{\mathbb{R}}\bigg{\\{}[e_{01}+e_{12}+e_{23}+e_{34}+e_{40}]\bigg{\\}};$
$\displaystyle
H_{n}^{\operatorname{cell}}(C_{5}^{1,2};\mathbb{R})=H_{n}(C_{5}^{1,2};\mathbb{R})=0,\quad
n\geq 2.$

######  Remark 4.4.

(1) One can choose different representatives for
$H_{1}^{\operatorname{cell}}(C_{5}^{1,2};\mathbb{R})$. Actually,

$\displaystyle[e_{01}+e_{12}+e_{23}+e_{34}+e_{40}]=~{}$
$\displaystyle[e_{01}+e_{13}+e_{30}]=[e_{12}+e_{24}+e_{41}]$
$\displaystyle=~{}$
$\displaystyle[e_{23}+e_{30}+e_{02}]=[e_{34}+e_{41}+e_{13}]$
$\displaystyle=~{}$ $\displaystyle[e_{40}+e_{02}+e_{24}];$
$\displaystyle[e_{02}+e_{24}+e_{41}+e_{13}+e_{30}]=~{}$ $\displaystyle
2[e_{01}+e_{12}+e_{23}+e_{34}+e_{40}].$

It is easy to see that the following 2-chain

$(e_{013}-e_{023})+(e_{124}-e_{134})+(e_{230}-e_{240})+(e_{341}-e_{301})+(e_{402}-e_{412})$

is closed. But it is also the boundary of
$e_{0123}+e_{1234}+e_{2340}+e_{3401}+e_{4012}$. One can further check the
3-closed chains are also trivial. From the point of view of discrete torus, we
hope the above results could be explained as some twisted homology of torus.

(2) If we consider the original regular condition of path complex in Remark
2.3, one can find that for any $k\in\mathbb{N}$,

$\displaystyle e_{{\underbrace{01234\cdots
01234}_{k}0}},~{}e_{{\underbrace{01234\cdots
01234}_{k}01}},~{}e_{{\underbrace{01234\cdots 01234}_{k}012}},$ $\displaystyle
e_{{\underbrace{01234\cdots 01234}_{k}0123}},~{}e_{{\underbrace{01234\cdots
01234}_{k}01234}}\in\Omega_{*}(G).$

It is not easy to completely determine the original path complex for
$C_{5}^{1,2}$. But with our strongly regular condition, the computation of
path complex and cellular complex is much simpler.

######  Example 4.5 (The digraph $C_{7}^{1,3}$).

The sets $\mathcal{P}_{\operatorname{adm},n}(C_{7}^{1,3})$, which are the same
as $\mathcal{P}_{n}(C_{7}^{1,3})$, are given by

$\displaystyle\mathcal{P}_{\operatorname{adm},0}(C_{7}^{1,3})=\mathcal{P}_{0}(C_{7}^{1,3})=V(C_{7}^{1,3});$
$\displaystyle\mathcal{P}_{\operatorname{adm},1}(C_{7}^{1,3})=\mathcal{P}_{1}(C_{7}^{1,3})=E(C_{7}^{1,3});$
$\displaystyle\mathcal{P}_{\operatorname{adm},2}(C_{7}^{1,3})=\mathcal{P}_{2}(C_{7}^{1,3})=\\{e_{014}-e_{034},~{}e_{125}-e_{145},~{}e_{236}-e_{256},~{}e_{340}-e_{360},$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad
e_{451}-e_{401},~{}e_{562}-e_{512},~{}e_{603}-e_{623}\\};$
$\displaystyle\mathcal{P}_{\operatorname{adm},n}(C_{7}^{1,3})=\mathcal{P}_{n}(C_{7}^{1,3})=0,\quad
n\geq 3.$

One can check that $\left(C_{7}^{1,3},\cup_{n=0}^{2}\mathcal{P}_{n}\right)$
gives the path complex structure as well as CW structure of $C_{7}^{1,3}$.
After a careful calculation, we have

$\displaystyle
H_{0}^{\operatorname{cell}}(C_{7}^{1,3};\mathbb{R})=H_{0}(C_{7}^{1,3};\mathbb{R})\cong\mathbb{R};$
$\displaystyle
H_{1}^{\operatorname{cell}}(C_{7}^{1,3};\mathbb{R})=H_{1}(C_{7}^{1,3};\mathbb{R})=\operatorname{Span}_{\mathbb{R}}\bigg{\\{}[e_{03}+e_{36}+e_{60}],~{}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\quad[e_{01}+e_{12}+e_{23}+e_{34}+e_{45}+e_{56}+e_{60}]\bigg{\\}};$
$\displaystyle
H_{2}^{\operatorname{cell}}(C_{7}^{1,3};\mathbb{R})=H_{2}(C_{7}^{1,3};\mathbb{R})=\operatorname{Span}_{\mathbb{R}}\bigg{\\{}[(e_{014}-e_{034})+(e_{125}-e_{145})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\quad+(e_{236}-e_{256})+(e_{340}-e_{360})+(e_{451}-e_{401})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\quad+(e_{562}-e_{512})+(e_{603}-e_{623})]\bigg{\\}};$
$\displaystyle
H_{n}^{\operatorname{cell}}(C_{7}^{1,3};\mathbb{R})=H_{n}(C_{7}^{1,3};\mathbb{R})=0,\quad
n\geq 3.$

###  4.2. The Johnson digraph

######  Definition 4.6.

Fix an integer $k$, $1\leq k\leq n$. The Johnson digraph
$\overrightarrow{J}(n,k)$ is defined as a digraph whose vertices are all
$k$-element subsets of the set $V=\\{1,2,\ldots,n\\}$, and the arrows are
defined as follows: if $a$ and $b$ are two $k$-element subsets of $V$, then
$a\rightarrow b$ in $\overrightarrow{J}(n,k)$ if $a$ and $b$ have the
following form (unordered):

$a=\\{c_{0},c_{1},\ldots,c_{k-1}\\},\quad
b=\\{c_{0}^{\prime},c_{1},\ldots,c_{k-1}\\},\quad c_{0}^{\prime}<c_{0}.$

######  Example 4.7 (Johnson digraph $\overrightarrow{J}(4,2)$).

For $n=4$, $k=2$, we get the following left digraph $\overrightarrow{J}(4,2)$.
For convenience, we relabel its vertices as the right picture shows.

$21$
---
$31$
---
$41$
---
$43$
---
$42$
---
$32$
---
$0$
---
$1$
---
$3$
---
$5$
---
$4$
---
$2$
---

The sets
$\mathcal{P}_{\operatorname{adm},n}=\mathcal{P}_{\operatorname{adm},n}(\overrightarrow{J}(4,2))$,
which are the same as $\mathcal{P}_{n}(\overrightarrow{J}(4,2))$, are given by

$\displaystyle\mathcal{P}_{\operatorname{adm},0}=\mathcal{P}_{0}=V(\overrightarrow{J}(4,2));$
$\displaystyle\mathcal{P}_{\operatorname{adm},1}=\mathcal{P}_{1}=E(\overrightarrow{J}(4,2));$
$\displaystyle\mathcal{P}_{\operatorname{adm},2}=\mathcal{P}_{2}=\\{e_{210},~{}e_{310},~{}e_{420},~{}e_{430},~{}e_{521},~{}e_{531},~{}e_{421}-e_{431},~{}e_{542},~{}e_{543},$
$\displaystyle\qquad\qquad\qquad\quad e_{5i0}-e_{5j0},~{}i,j=1,2,3,4,\text{
and }i\neq j\text{ (up to a sign)}\\};$
$\displaystyle\mathcal{P}_{\operatorname{adm},3}=\mathcal{P}_{3}=\\{e_{5310},~{}e_{5420}\\}.$

There exist admissible relations among
$\\{e_{5i0}-e_{5j0},~{}i,j=1,2,3,4,\text{ and }i\neq j\text{ (up to a
sign)}\\}$. Furthermore, we can compute the cellular homology of
$\overrightarrow{J}(4,2)$, and obtain

$\widetilde{H}_{*}^{\operatorname{cell}}(\overrightarrow{J}(4,2))=0.$

The result could also follow from the contractibility of Johnson digraph
$\overrightarrow{J}(4,2)$, which are given by the composition of the following
two digraph maps

$\displaystyle f_{1}(5)=f_{1}(4)=f_{1}(2)=2,\quad f_{1}(3)=f_{1}(1)=1,\quad
f_{1}(0)=0;$ $\displaystyle f_{2}(2)=f_{2}(1)=f_{2}(0)=0.$

##  5\. Discussion and Outlook

###  5.1. The digraphs from geometry

There are several ways to discrete a manifold $M$ and get a graph which
captures some topological structure of $M$. For example, one can choose a
simplicial complex $K$ which triangulates $M$, and its one-skeleton gives us a
graph. Such a discretization has a wide range of applications, such as
Cheeger-Müller theorem, combinatorial quantum field theory.

CMY[12] prove that after twice barycentric subdivisions, the corresponding
path homology of the larger digraph is isomorphic to the simplicial homology
of $K$.

Instead, we can consider the digraph from geometry in another way. For
simplicity, let $(M,g)$ be an oriented complete Riemannian manifold with
metric $g$ and injectivity radius bounded below by a positive constant $b$.
First, choose a discrete collection of points $\\{x_{i}\\}=V\subset M$
satisfying

  1. (1)

$\operatorname{dist}_{g}(x_{i},x_{j})\geq\frac{b}{4}$, for any $x_{i}\neq
x_{j}$;

  2. (2)

for every $x\in M$ there is some $x_{i}\in V$ such that
$\operatorname{dist}_{g}(x_{i},x)<\frac{b}{2}$.

Next, define an (undirected) edge structure on $V$ by the relationship

$x_{i}\sim x_{j},\text{ if }\operatorname{dist}_{g}(x_{i},x_{j})<b\text{ and
}i\neq j.$

Then $G=(V,E)$ is a connected graph. Moreover, we consider the direction of
each edge which is induced by the orientation of $M$: Given an undirected edge
$x_{i}\sim x_{j}$, we say $x_{i}~{}\rightarrow~{}x_{j}$, if the tangent vector
at $x_{i}$ to a distance minimizing geodesic connecting $x_{i}$ to $x_{j}$ is
given by the orientation on $M$.

######  Example 5.1 (The integer lattice $\mathbb{Z}^{n}$).

Let $\mathbb{R}^{n}$ be the Euclidean space. Take $V=\mathbb{Z}^{n}$ and
$b=\sqrt{2}$, then we get the standard nearest-neighbor digraph on the given
lattice.

We will study the path homology and cellular homology of the digraph from
geometry and compare them to the homology of the manifold in a separation
paper.

###  5.2. The relation to singular cubical homology

In Remark 2.3, we have the observation: if the digraph does not contain a
monotone cycle, then our restricted path homology is also the same as the
original path homology. In the sequel, we continue focusing on such special
digraphs.

Note that the definition of our cellular homology is related to the singular
cubical homology. It is natural to consider the relation between the two
homologies. First, if Conjecture 3.43 holds, then by homotopy invariance of
both homologies, we have

$\widetilde{H}_{*}^{\operatorname{cell}}(\operatorname{Supp}(P))=\widetilde{H}_{*}^{c}(\operatorname{Supp}(P))=0,\quad
P\in\mathcal{P}_{\operatorname{adm}}(G).$

Next, we will consider the following three typical digraphs, which include the
trivial linear relations, admissible linear relations and non-admissible
minimal paths respectively. And we will see their correspondence in the
singular cubical complex.

  * •

$G=\\{0\rightarrow 1\rightarrow 3,0\rightarrow 2\rightarrow 3,0\rightarrow
3\\}$, i.e. Example 3.30;

  * •

the digraph $S_{k}$ in Example 3.21 and Example 3.22;

  * •

the exotic cube, i.e. Example 3.15.

####  5.2.1. Example 3.30 revisited

In the digraph $G$ of Example 3.30, we have the following trivial linear
relations

  1. (1)

$(e_{013},\operatorname{Supp}(e_{013}))+(-e_{013},\operatorname{Supp}(e_{023}))=0$;

  2. (2)

$(e_{013}-e_{023},\operatorname{Supp}(e_{013}-e_{023}))+(e_{023}-e_{013},\operatorname{Supp}(e_{013}-e_{023}))=0$;

  3. (3)

$(e_{013},\operatorname{Supp}(e_{013}))+(-e_{023},\operatorname{Supp}(e_{023}))=(e_{013}-e_{023},\operatorname{Supp}(e_{013}-e_{023}))$.444Although
$e_{013}-e_{023}$ is not minimal in $G$, but it admits a singular cubic
realization, we want to discuss the relations among these singular cubes.

For the trivial relations (1) (2), let us look at the following singular
$3$-cubes $f_{+}$, $f_{-}$, $g_{+}$, $g_{-}$:

$\displaystyle f_{+}((0,0))=f_{+}((0,1))=0,\quad f_{+}((1,0))=1,\quad
f_{+}((1,1))=3;$ $\displaystyle f_{-}((0,0))=f_{-}((1,0))=0,\quad
f_{-}((0,1))=1,\quad f_{-}((1,1))=3;$ $\displaystyle g_{+}((0,0))=0,\quad
g_{+}((1,0))=1,\quad g_{+}((0,1))=2,\quad g_{+}((1,1))=3;$ $\displaystyle
g_{-}((0,0))=0,\quad g_{-}((1,0))=2,\quad g_{-}((0,1))=1,\quad
g_{-}((1,1))=3.$

It is easy to obtain

$(f_{+})_{*}(\omega_{2})+(f_{-})_{*}(\omega_{2})=e_{013}+(-e_{013})=0,\quad(g_{+})_{*}(\omega_{2})+(g_{-})_{*}(\omega_{2})=0.$

Furthermore, we can construct a non-degenerate $3$-cube $\tilde{f}$:

$\displaystyle\tilde{f}((0,0,0))=\tilde{f}((1,0,0))=\tilde{f}((0,0,1))=\tilde{f}((1,0,1))=0,$
$\displaystyle\tilde{f}((0,1,0))=\tilde{f}((1,1,0))=\tilde{f}((0,1,1))=1,\quad\tilde{f}((1,1,1))=3.$

By definition, $\tilde{f}\circ F_{11}=f_{+}$, $\tilde{f}\circ F_{31}=f_{-}$,
and other $\tilde{f}\circ F_{j\epsilon}$’s are degenerate. Thus, we have

$\partial^{c}(\tilde{f})=f_{+}+f_{-}.$

Similarly, one can check the following non-degenerate $3$-cube $\tilde{g}$:

$\displaystyle\tilde{g}((0,0,0))=\tilde{g}((1,0,0))=\tilde{g}((0,0,1))=0,\quad\tilde{g}((1,0,1))=1$
$\displaystyle\tilde{g}((0,1,0))=\tilde{g}((1,1,0))=\tilde{g}((0,1,1))=2,\quad\tilde{g}((1,1,1))=3.$

satisfying $\partial^{c}(\tilde{g})=g_{+}+g_{-}$.

######  Remark 5.2.

Note that the above $f_{+}$ and $f_{-}$ ($g_{+}$ and $g_{-}$ respectively) are
related by an automorphism of $I^{\boxdot 2}$. Thus it is an interesting
problem to study the action of the automorphism group of the cubes on the
singular cubes. On the other hand, one can also consider other different
singular cubical realizations of the triangle and discuss their relations.

For the trivial relation (3), let us look at the following three singular
$3$-cubes $f_{1}$, $f_{2}$, $f_{3}$:

$\displaystyle f_{1}((0,0))=0,~{}f_{1}((0,1))=1,~{}f((1,0))=f((1,1))=3;$
$\displaystyle
f_{2}((0,0))=f_{2}((1,0))=0,~{}f_{2}((0,1))=2,~{}f_{2}((1,1))=3;\quad
f_{3}=g_{+}.$

Similarly, we have

$(f_{3})_{*}(\omega_{2})=e_{013}-e_{023}=-(f_{1})_{*}(\omega_{2})+(f_{2})_{*}(\omega_{2}).$

And we can construct a non-degenerate $3$-cubes $h$ in $G$:

$\displaystyle h((0,0,0))=h((1,0,0))=h((0,0,1))=0,\quad h((1,0,1))=1$
$\displaystyle h((0,1,0))=h((0,1,1))=2,\quad h((1,1,0))=h((1,1,1))=3.$

It satisfies $\partial^{c}(h)=f_{3}+f_{1}-f_{2}.$

####  5.2.2. Example 3.21 and Example 3.22 revisited

For the digraph $S_{k}$, it is contractible, since we have the deformation
retraction

$f:S_{k}\rightarrow\\{S~{}\rightarrow~{}1\\},$

which are given by

$f(S)=f(2)=f(3)=\cdots=f(k)=S,\quad f(1)=f(E)=1.$

By homotopy invariance, we know that both kinds of homologies of $S_{k}$ are
trivial. It is worth to mention that, on the one hand, there are many
admissible relations among $\mathcal{P}_{\operatorname{adm},2}(S_{k})$ being
quotient in the cellular chain. Here we focus our discussions on the following
two relations.

  1. (1)

For distinct $i,j,l$,
$(e_{SiE}-e_{SjE})-(e_{SiE}-e_{SlE})+(e_{SjE}-e_{SlE})=0$;

  2. (2)

$(e_{S1E}-e_{S2E})+(e_{S3E}-e_{S4E})+(e_{S2E}-e_{S3E})+(e_{S4E}-e_{S1E})=0$.

Note that each square in $S_{k}$ corresponds to a singular $2$-cube. For
example, we consider the cubes

$f_{ij}:I^{\boxdot 2}\rightarrow S_{k},\quad i,j=1,\ldots,k,~{}i\neq j$

which are given by

$f_{ij}((0,0))=S,\quad f_{ij}((1,0))=i,\quad f_{ij}((0,1))=j,\quad
f_{ij}((1,1))=E.$

By definition, for distinct $i,j,l\in\\{1,2,\ldots,k\\}$, we have

  * •

$[(f_{ij})_{*}-(f_{il})_{*}+(f_{jl})_{*}](\omega_{2})=0$, i.e. the above
admissible relation (1);

  * •

$\partial^{c}(f_{ij}-f_{il}+f_{jl})=0.$

While $f_{ij}-f_{il}+f_{jl}$ is also a boundary of a non-degenerate singular
$3$-cube $g:I^{\boxdot 3}\rightarrow S_{k}$ which is defined by

$\displaystyle g((0,0,0))=g((1,0,0))=g((0,1,0))=g((0,0,1))=S,$ $\displaystyle
g((1,1,0))=i,\quad g((1,0,1))=j,\quad g((0,1,1))=l,\quad g((1,1,1))=E.$

One can check that $\partial^{c}(g)=f_{ij}-f_{il}+f_{jl}$ $\mod$ (degenerate
cubes).

Similarly, the four summands in the above admissible relation (2) could be
realized by singular $2$-cubes $f_{12}$, $f_{34}$, $f_{23}$ and $f_{41}$
respectively. By definition, we have

$\partial^{c}(f_{12}+f_{34}+f_{23}+f_{41})=0.$

Meanwhile, we can construct two singular $3$-cubes $g_{1},g_{2}:I^{\boxdot
3}\rightarrow S_{k}$:

$\displaystyle g_{1}((0,0,0))=g_{1}((1,0,0))=g_{1}((0,1,0))=g_{1}((0,0,1))=S,$
$\displaystyle g_{1}((1,1,0))=1,\quad g_{1}((1,0,1))=2,\quad
g_{1}((0,1,1))=3,\quad g_{1}((1,1,1))=E;$ $\displaystyle
g_{2}((0,0,0))=g_{2}((1,0,0))=g_{2}((0,1,0))=g_{2}((0,0,1))=S,$ $\displaystyle
g_{2}((1,1,0))=3,\quad g_{2}((1,0,1))=4,\quad g_{2}((0,1,1))=1,\quad
g_{2}((1,1,1))=E.$

One can check $\partial^{c}(g_{1}+g_{2})=f_{12}+f_{34}+f_{23}+f_{41}$ $\mod$
(degenerate cubes).

We learn from this example that the admissible relations may be realized as
the boundary conditions in the singular cubical homology. We can also check
this observation via Example 3.22, where the digraph is

$0$
---
$1$
---
$3$
---
$6$
---
$2$
---
$4$
---
$5$
---

All the admissible paths in

$\mathcal{P}_{\operatorname{adm},3}=\\{e_{0136}-e_{0236}+e_{0256},~{}e_{0136}-e_{0146}+e_{0246}-e_{0236},~{}e_{0146}-e_{0246}+e_{0256}\\},$

could be realized by the following three singular 3-cubes

$\displaystyle f:I^{\boxdot
3}\rightarrow\operatorname{Supp}(e_{0136}-e_{0236}+e_{0256}),$ $\displaystyle
g:I^{\boxdot
3}\rightarrow\operatorname{Supp}(e_{0136}-e_{0146}+e_{0246}-e_{0236}),$
$\displaystyle h:I^{\boxdot
3}\rightarrow\operatorname{Supp}(e_{0146}-e_{0246}+e_{0256}),$

which are explicitly given by

$\displaystyle f((0,0,0))=0,\quad f((1,0,0))=1,\quad f((0,1,0))=2,\quad
f((0,0,1))=5,$ $\displaystyle f((1,1,0))=3,\quad f((1,0,1))=6,\quad
f((0,1,1))=5,\quad f((1,1,1))=6;$ $\displaystyle g((0,0,0))=0,\quad
g((1,0,0))=1,\quad g((0,1,0))=2,\quad g((0,0,1))=1,$ $\displaystyle
g((1,1,0))=3,\quad g((1,0,1))=3,\quad g((0,1,1))=4,\quad g((1,1,1))=6;$
$\displaystyle h((0,0,0))=0,\quad h((1,0,0))=2,\quad h((0,0,1))=5,\quad
h((0,1,0))=1,$ $\displaystyle h((1,1,0))=5,\quad h((1,0,1))=4,\quad
h((0,1,1))=6,\quad h((1,1,1))=6.$

One can check that

$\displaystyle f_{*}(\omega_{3})-g_{*}(\omega_{3})-h_{*}(\omega_{3})$
$\displaystyle=~{}$
$\displaystyle(e_{0136}-e_{0236}+e_{0256})-(e_{0136}-e_{0146}+e_{0246}-e_{0236})-(e_{0146}-e_{0246}+e_{0256})=0$

and also compute by definition

$\partial^{c}(f-g+h)=0.$

Meanwhile, we can construct $\phi:I^{\boxdot 4}\rightarrow G$ as follows:

$\displaystyle\phi((0,0,0,0))=0,\quad\phi((1,0,0,0))=1,\quad\phi((0,1,0,0))=2,\quad\phi((0,0,1,0))=5,$
$\displaystyle\phi((1,1,0,0))=3,\quad\phi((1,0,1,0))=6,\quad\phi((0,1,1,0))=5,\quad\phi((1,1,1,0))=6;$
$\displaystyle\phi((0,0,0,0))=0,\quad\phi((1,0,0,0))=1,\quad\phi((0,1,0,0))=2,\quad\phi((0,0,0,1))=1,$
$\displaystyle\phi((1,1,0,0))=3,\quad\phi((1,0,0,1))=3,\quad\phi((0,1,0,1))=4,\quad\phi((1,1,0,1))=6;$
$\displaystyle\phi((0,0,0,0))=0,\quad\phi((0,1,0,0))=2,\quad\phi((0,0,1,0))=5,\quad\phi((0,0,0,1))=1,$
$\displaystyle\phi((0,1,1,0))=5,\quad\phi((0,1,0,1))=4,\quad\phi((0,0,1,1))=6,\quad\phi((0,1,1,1))=6;$
$\displaystyle\phi((1,1,1,1))=6.$

We write several repeated terms to make the following observations clearer

$\displaystyle f=\phi\circ F_{40},\quad\text{via }~{}F_{40}:I^{\boxdot 3}\cong
I^{\boxdot 3}\boxdot\\{0\\};$ $\displaystyle g=\phi\circ F_{30},\quad\text{via
}~{}F_{30}:I^{\boxdot 3}\cong I^{\boxdot 2}\boxdot\\{0\\}\boxdot I;$
$\displaystyle h=\phi\circ F_{10},\quad\text{via }~{}F_{10}:I^{\boxdot
3}\cong\\{0\\}\boxdot I^{\boxdot 3}.$

To compute $\partial^{c}\phi$, we also need to know

$\phi\circ F_{20}~{}\text{ and }~{}\phi\circ F_{j1},~{}j=1,2,3,4.$

One can easily check one by one that these singular $3$-cubes are degenerate.
Thus, by definition,

$\displaystyle\partial^{c}{\phi}=~{}$
$\displaystyle\sum_{j=1}^{4}(-1)^{j}\left(\phi\circ F_{j0}-\phi\circ
F_{j1}\right)$ $\displaystyle=~{}$ $\displaystyle f-g-h\quad\mod\text{
(degenerate cubes)}.$

####  5.2.3. Example 3.15 revisited

In [7], a non-trivial 2-cycle $\phi$ (where they use the notation
$\phi^{\Box}$) for the singular cubical homology of the exotic cube is
constructed to be a linear combination of 8 singular $2$-cubes:

$\phi=\sum_{i=1}^{8}\phi_{i}.$

In particular, the 8 singular $2$-cubes exactly give the singular cubical
realizations of the 8 minimal 2-faces in
$\mathcal{P}_{\operatorname{adm},2}(\mbox{exotic cube})$ respectively. And

$\phi_{*}(\omega_{2})=\sum_{i=1}^{8}(\phi_{i})_{*}(\omega_{2})$

gives us the non-trivial 2-cycle in the cellular homology which generates
$H_{2}^{\operatorname{cell}}(\text{exotic cube};\mathbb{R})$.

Note that the singular cubical chains are big enough that it is quite
difficult to write down the chain complex and compute the corresponding
homologies. But our cellular homologies are much easier. With the above
observations, we have the following conjecture.

######  Conjecture 5.3.

If the digraph $G$ does not contain a monotone cycle, then

$H_{*}^{\operatorname{cell}}(G;\mathbb{R})\cong H_{*}^{c}(G;\mathbb{R}).$

In particular, the admissible relations among the admissible pairs are the
boundary conditions in the singular cubical homology.

##  Appendix A Appendix. The admissible minimal $3$-paths

In this appendix section, we will give all the admissible minimal $3$-paths
and the retraction digraph maps to the corresponding face components.

First, as we explain before, there are finitely many kinds of admissible pairs
$(P,\operatorname{Supp}(P))$ for each $n\geq 0$. With the admissible
condition, we have the following observations on
$P\in\mathcal{P}_{\operatorname{adm},n}(G)$:

  * •

$|V(P)|=|V(\operatorname{Supp}(P))|\leq|V(I^{\boxdot n})|=2^{n}$.

  * •

Let $\operatorname{NE}(P)$ be the number of elementary path components in $P$.
Then $f_{*}(\omega_{n})=P$ implies

$\operatorname{NE}(P)\leq\operatorname{NE}(\omega_{n})=n!.$

  * •

Let $\operatorname{NF}(P)$ be the number of $(n-1)$-face components of $P$ in
$\operatorname{Supp}(P)$. Then Lemma 3.28 implies

$\operatorname{NF}(P)\leq\operatorname{NF}(\omega_{n})=2n.$

  * •

If we reverse all the edges in $\operatorname{Supp}(P)$, that is,

$\text{for any }a\rightarrow b\text{ in
}\operatorname{Supp}(P),\qquad\rightsquigarrow\qquad b\rightarrow a,$

then obviously the resulting path $\tilde{P}$ also admits a singular cubical
realization.

Thus, we can use these number constraints to analyze the set of admissible
minimal $3$-paths up to the above global orientation of edges. Finally, we
arrive at the following eight admissible minimal $3$-paths.

For simplicity, we will use the following notations

  * •

$K_{3}(a,b,c)$: the triangle $\\{a\rightarrow b\rightarrow c,~{}a\rightarrow
c\\}$;

  * •

$S(a,b,c,d)$: the square $\\{a\rightarrow b\rightarrow d,~{}a\rightarrow
c\rightarrow d\\}$.

######  Example A.1 ($\operatorname{NE}(P)=1$).

The admissible pair $(P,\operatorname{Supp}(P))$ with $\operatorname{NE}(P)=1$
is given by $P=e_{0123}$ and

$\operatorname{Supp}(e_{0123})=$
---
$0$
---
$1$
---
$2$
---
$3$
---

The singular cubical map (non-unique) $f:I^{\boxdot
3}\rightarrow\operatorname{Supp}(P)$ could be given by

$\displaystyle f((0,0,0))=0,\quad f((1,0,0))=1,\quad f((0,1,0))=2,\quad
f((0,0,1))=2,$ $\displaystyle f((1,1,0))=2,\quad f((1,0,1))=3,\quad
f((0,1,1))=2,\quad f((1,1,1))=3.$

We also have the following deformation retractions:

  1. (1)

$r_{1}:\operatorname{Supp}(P)\rightarrow\operatorname{im}\left(f\big{|}_{I^{\boxdot
2}\boxdot\\{0\\}}\right)=K_{3}(0,1,2)$,

$r_{1}(3)=r_{1}(2)=2,~{}r_{1}(1)=1,~{}r_{1}(0)=0;$

  2. (2)

$r_{2}:\operatorname{Supp}(P)\rightarrow\operatorname{im}\left(f\big{|}_{\\{0\\}\boxdot
I^{\boxdot 2}}\right)=\\{0\rightarrow 2\\}$,

$r_{2}(3)=r_{2}(2)=2,~{}r_{2}(1)=r_{2}(0)=0;$

  3. (3)

$r_{3}:\operatorname{Supp}(P)\rightarrow\operatorname{im}\left(f\big{|}_{I^{\boxdot
2}\boxdot\\{1\\}}\right)=\\{2\rightarrow 3\\}$,

$r_{3}(3)=3,~{}r_{3}(2)=r_{3}(1)=r_{3}(0)=2;$

  4. (4)

$r_{4}:\operatorname{Supp}(P)\rightarrow\operatorname{im}\left(f\big{|}_{I\boxdot\\{1\\}\boxdot
I}\right)=\\{2\rightarrow 3\\}$,

$r_{4}(3)=3,~{}r_{4}(2)=r_{4}(1)=r_{4}(0)=2;$

  5. (5)

$r_{5}:\operatorname{Supp}(P)\rightarrow\operatorname{im}\left(f\big{|}_{\\{1\\}\boxdot
I^{\boxdot 2}}\right)=K_{3}(1,2,3)$,

$r_{5}(3)=3,~{}r_{5}(2)=2,~{}r_{5}(1)=r_{5}(0)=1.$

Note that $\operatorname{im}\left(f\big{|}_{I\boxdot\\{0\\}\boxdot
I}\right)=S(0,1,2,3)$, there is no digraph map from $\operatorname{Supp}(P)$
onto $S(0,1,2,3)$. But it is easy to construct the digraph maps from
$\operatorname{Supp}(P)$ onto

$\\{0\rightarrow 1\\},~{}\\{0\rightarrow 2\\},~{}\\{1\rightarrow
3\\},~{}\\{2\rightarrow 3\\},~{}\\{0\rightarrow 1\rightarrow
3\\},~{}\\{0\rightarrow 2\rightarrow 3\\}.$

######  Example A.2 ($\operatorname{NE}(P)=2$).

One of the admissible pairs $(P,\operatorname{Supp}(P))$ with
$\operatorname{NE}(P)=2$ is given by $P=e_{0124}-e_{0134}$ and

$\operatorname{Supp}(P)=$
---
$0$
---
$1$
---
$2$
---
$3$
---
$4$
---

Another one is given by reversing all the edges.

The singular cubical map (non-unique) $f:I^{\boxdot
3}\rightarrow\operatorname{Supp}(P)$ could be given by

$\displaystyle f((0,0,0))=0,\quad f((1,0,0))=1,\quad f((0,1,0))=2,\quad
f((0,0,1))=3,$ $\displaystyle f((1,1,0))=2,\quad f((1,0,1))=3,\quad
f((0,1,1))=4,\quad f((1,1,1))=4.$

We also have the following deformation retractions:

  1. (1)

$r_{1}:\operatorname{Supp}(P)\rightarrow\operatorname{im}\left(f\big{|}_{I^{\boxdot
2}\boxdot\\{0\\}}\right)=K_{3}(0,1,2)$,

$r_{1}(4)=r_{1}(2)=2,~{}r_{1}(3)=r_{1}(1)=1,~{}r_{1}(0)=0;$

  2. (2)

$r_{2}:\operatorname{Supp}(P)\rightarrow\operatorname{im}\left(f\big{|}_{I\boxdot\\{0\\}\boxdot
I}\right)=K_{3}(0,1,3)$,

$r_{2}(4)=r_{2}(3)=3,~{}r_{2}(2)=r_{2}(1)=1,~{}r_{2}(0)=0;$

  3. (3)

$r_{3}:\operatorname{Supp}(P)\rightarrow\operatorname{im}\left(f\big{|}_{\\{0\\}\boxdot
I^{\boxdot 2}}\right)=S(0,2,3,4)$,

$r_{3}(4)=4,~{}r_{3}(3)=3,~{}r_{3}(2)=2,~{}r_{3}(1)=r_{3}(0)=0;$

  4. (4)

$r_{4}:\operatorname{Supp}(P)\rightarrow\operatorname{im}\left(f\big{|}_{I^{\boxdot
2}\boxdot\\{1\\}}\right)=\\{3\rightarrow 4\\}$,

$r_{4}(4)=r_{4}(2)=4,~{}r_{4}(3)=r_{4}(1)=r_{4}(0)=3;$

  5. (5)

$r_{5}:\operatorname{Supp}(P)\rightarrow\operatorname{im}\left(f\big{|}_{I\boxdot\\{1\\}\boxdot
I}\right)=\\{2\rightarrow 4\\}$,

$r_{5}(4)=r_{5}(3)=4,~{}r_{5}(2)=r_{5}(1)=r_{5}(0)=2;$

  6. (6)

$r_{6}:\operatorname{Supp}(P)\rightarrow\operatorname{im}\left(f\big{|}_{\\{1\\}\boxdot
I^{\boxdot 2}}\right)=S(1,2,3,4)$,

$r_{6}(4)=4,~{}r_{6}(3)=3,~{}r_{6}(2)=2,~{}r_{6}(1)=r_{6}(0)=1.$

######  Example A.3 ($\operatorname{NE}(P)=3$, $\operatorname{NF}(P)=4$).

The admissible pair $(P,\operatorname{Supp}(P))$ with
$\operatorname{NE}(P)=3$, $\operatorname{NF}(P)=4$ is given by

$P=e_{0124}-e_{0134}+e_{0234},$

$0$
---
$1$
---
$2$
---
$3$
---
$4$
---
$\operatorname{Supp}(P)=$
---

The singular cubical map (non-unique) $f:I^{\boxdot
3}\rightarrow\operatorname{Supp}(P)$ could be given by

$\displaystyle f((0,0,0))=0,\quad f((1,0,0))=1,\quad f((0,1,0))=1,\quad
f((0,0,1))=2,$ $\displaystyle f((1,1,0))=3,\quad f((1,0,1))=2,\quad
f((0,1,1))=3,\quad f((1,1,1))=4.$

We also have the following deformation retractions:

  1. (1)

$r_{1}:\operatorname{Supp}(P)\rightarrow\operatorname{im}\left(f\big{|}_{I^{\boxdot
2}\boxdot\\{0\\}}\right)=\\{0\rightarrow 1\rightarrow 3\\}$,

$r_{1}(4)=r_{1}(3)=3,~{}r_{1}(2)=r_{1}(1)=1,~{}r_{1}(0)=0;$

  2. (2)

$r_{2}:\operatorname{Supp}(P)\rightarrow\operatorname{im}\left(f\big{|}_{I\boxdot\\{0\\}\boxdot
I}\right)=K_{3}(0,1,2)$,

$r_{2}(4)=r_{2}(3)=r_{2}(2)=2,~{}r_{2}(1)=1,~{}r_{2}(0)=0;$

  3. (3)

$r_{4}:\operatorname{Supp}(P)\rightarrow\operatorname{im}\left(f\big{|}_{I^{\boxdot
2}\boxdot\\{1\\}}\right)=K_{3}(2,3,4)$,

$r_{4}(4)=4,~{}r_{4}(3)=3,~{}r_{4}(2)=r_{4}(1)=r_{4}(0)=2;$

  4. (4)

$r_{5}:\operatorname{Supp}(P)\rightarrow\operatorname{im}\left(f\big{|}_{I\boxdot\\{1\\}\boxdot
I}\right)=\\{1\rightarrow 3\rightarrow 4\\}$,

$r_{5}(4)=4,~{}r_{5}(3)=r_{5}(2)=3,~{}r_{5}(1)=r_{5}(0)=1;$

Note that $\operatorname{im}\left(f\big{|}_{\\{0\\}\boxdot I^{\boxdot
2}}\right)=S(0,1,2,3)$ and $\operatorname{im}\left(f\big{|}_{\\{1\\}\boxdot
I^{\boxdot 2}}\right)=S(1,2,3,4)$, there are no digraph maps from
$\operatorname{Supp}(P)$ onto these two faces, but there exist digraph maps
onto their components, such as $r_{1}$ and $r_{5}$.

######  Example A.4 ($\operatorname{NE}(P)=3$, $\operatorname{NF}(P)=5$, i.e.
Example 3.13).

The admissible pair $(P,\operatorname{Supp}(P))$ with
$\operatorname{NE}(P)=3$, $\operatorname{NF}(P)=5$ is given by

$P=e_{0135}-e_{0235}+e_{0245},$

$0$
---
$1$
---
$2$
---
$3$
---
$4$
---
$5$
---
$\operatorname{Supp}(P)=$
---

The singular cubical map (non-unique) $f:I^{\boxdot
3}\rightarrow\operatorname{Supp}(P)$ could be given by

$\displaystyle f((0,0,0))=0,\quad f((1,0,0))=1,\quad f((0,1,0))=2,\quad