#  Persistent pairs and connectedness in discrete Morse functions on
simplicial complex i@

Chong Zheng  Faculty of Science and Engineering, Waseda University, Ohkubo,
Shinkuju-ku, Tokyo, 169-8555 Japan<EMAIL_ADDRESS>
###### Abstract.

In this paper, we study some useful properties of persistent pairs in a
discrete Morse function on a simplicial complex $K$. In case of $\dim K=1$
(i.e., a graph), by using the properties, we characterize strongly
connectedness of critical simplices between two distinct discrete Morse
functions, and relate the number of such pairs to the Euler characteristic of
$K$.

###### Key words and phrases:

Discrete Morse theory, Strong connection, Homology, Persistent pairs, Euler
characteristic.

##  1\. Introduction

Introduced by R. Forman [5], discrete Morse theory is a combinatorial version
of standard Morse theory. The main idea of discrete Morse theory is to
collapse pairs of simplices in such a way that the homotopy type of the space
remains consistent, as similar to the elementary collapse theory invented by
J.H.C. Whitehead [12]. A discrete Morse function is a real-valued function
assigned to the set of simplices. Also, a discrete Morse function corresponds
to a gradient vector field, in which non-critical simplices are paired with
each other. We can reduce the number of simplices in a complex by collapsing
the pairs in a gradient vector field. Hence, discrete Morse theory is widely
used for the computation of the homology of spaces. The main theorems of
discrete Morse theory are first formulated for CW complexes, and have since
been expanded to other structures, including simplicial complexes [14], graphs
[1], and posets [4]. This approach has proven to be useful in studying the
topology of spaces and has found numerous applications in various areas,
notably in the calculation of persistent homology [9].

King, Knudson, and Mramor Kosta [7] introduced the concept of birth and death
theory in discrete Morse theory, which has been applied to several interesting
data analysis problems. In their framework, given a CW complex and a series of
discrete Morse functions, they define a connectedness relationship between two
critical simplices in different gradient vector fields. A series of organized
discrete Morse functions on the same cellulation divides space into slices in
which critical simplices appear and disappear. As time varies, they trace
critical points via a discrete version of a bifurcation diagram. The diagram
provides information on the birth and death of each critical simplex. The
persistent time of each critical simplex reflects the geometric information of
the space under the given discrete Morse functions.

In this paper, we apply persistence pairs to discuss various problems related
to connectedness and strong connectedness, including one posed in [7]. A
persistence pair, is a pair of simplices used to depict the birth and death of
a homology class with respect to ascending indices of the filtration of the
simplicial complex. The concept of persistence pair can be found in [11, 2].
Furthermore, a similar concept called homological sequence is discussed in the
case of graphs in Section 3 and 5 of Ayala et al [1]. Compared with [1] and
[3], in which the authors investigate the number of discrete Morse functions
on a graph, our primary objective in this paper is to use persistence pairs to
study the strong connectedness between different discrete Morse functions on a
graph.

Section 2 provides a brief summary of the definitions and results in discrete
Morse theory. In Section 3, we investigate persistence pairs of discrete Morse
functions, and formalize several properties of persistence pairs in terms of
simplicial complexes. In Section 4, we discuss the idea of connectedness
between multiple discrete Morse functions and investigate several problems
regarding to the connectedness, including uniqueness of strong connectedness
and gradient paths. Moreover, in Theorem 4.10, we study the relationship
between the number of strong connectedness pairs and the Euler characteristic
of a graph. Precisely,

######  Theorem.

Let $G$ be a graph and

$f_{1},f_{2}:G\to\mathbb{R}$

be discrete Morse functions. Let $A_{q}^{f_{1},f_{2}}(G)$ be the number of
strongly connected pairs of $q$-dimensional simplices between $f_{1}$ and
$f_{2}$, $q=0,1$. Then,

$A_{0}^{f_{1},f_{2}}(G)-A_{1}^{f_{1},f_{2}}(G)=\beta_{0}(G)-\beta_{1}(G)=\chi(G),$

where $\chi(G)$ is the Euler characteristic of the graph $G$.

##  2\. Prelimanaries

This section is devoted to briefly summarize a theoretical basis of discrete
Morse theory. For details, the readers may refer to [6] and [5]. Additional
resources on discrete Morse theory can be found in textbooks such as [11] and
[8]. This paper includes some basic definitions and facts about homology
theory, which is a fundamental field in algebraic topology and has wide
applications in various fields. Some of the details regarding homology theory
are left undefined and unproven. For details on basic homology theory, one
refers to [10].

A simplicial complex $K$ is a collection of simplices such that every face of
a simplex of $K$ is in $K$, and the intersection of any two simplices of $K$
is a face of each of them. By $K_{p}$ we denote the set of simplices of
dimension $p$. The dimension of $K$ is the maximum dimension among its
simplices.

We denote the chain complex of $K$ with coefficient in a finite field
$\mathbb{F}$ by $C_{\ast}(K;\mathbb{F}):=\bigoplus_{q}C_{q}(K;\mathbb{F})$
with boundary operator $\partial_{\ast}$. We denote by
$B_{q}(K):=\text{im}(\partial_{q+1})$, and
$Z_{q}(K):=\text{ker}(\partial_{q})$. We then define the $q$-th homology group
of $K$ as $H_{q}(K):=Z_{q}(K)/B_{q}(K)$. The rank of $H_{q}$ is called the
$q$-th Betti number. Each element $[h]\in H_{q}$ is called a homology class. A
chain $c\in Z_{q}$ is called a representative chain of $[h]$, if $c$ is in the
homology class $[h]$. Two chains $h_{1},h_{2}\in C_{q}$ are said to be
homologous if they both are representative chains of the same homology class.

Now we introduce the fundamental definitions and theorems of discrete Morse
theory.

######  Definition 2.1.

A discrete Morse function on $K$ is a real-valued function

$f:K\longrightarrow\mathbb{R}$

satisfying for all $\sigma\in K_{p}$,

  1. (1)

$\displaystyle\\#\\{\tau^{(p+1)}\succ\sigma|f(\tau)\leq f(\sigma)\\}\leq 1;$

  2. (2)

$\displaystyle\\#\\{v^{(p-1)}\prec\sigma|f(\sigma)\leq f(v)\\}\leq 1,$

where $\\#$ denotes the cardinality of a set. Notations $v\prec\sigma$ and
$\tau\succ\sigma$ mean that $v$ is a face of $\sigma$ and $\sigma$ is a face
of $\tau$, respectively. Also, we use the notation $\sigma^{(p)}$ to represent
that the dimension of simplex $\sigma$ is $p$.

######  Definition 2.2.

Given a discrete Morse function $f$ on $K$, we say that a simplex $\sigma\in
K_{p}$ is a critical $p$-dimensional simplex (of $f$) if

  1. (1)

$\displaystyle\\#\\{\tau^{(p+1)}\succ\sigma\,|\,f(\tau)\leq f(\sigma)\\}=0;$

  2. (2)

$\displaystyle\\#\\{v^{(p-1)}\prec\sigma\,|\,f(\sigma)\leq f(v)\\}=0.$

If $\sigma$ is a critical simplex, then we call $f(\sigma)$ a critical value
of $f$. Conversely, if a simplex $\sigma$ is not critical, then we say that
$\sigma$ is a non-critical simplex, and $f(\sigma)$ is a non-critical value.

A discrete Morse function is called excellent, if its all critical values are
different. In this paper, we always assume that the discrete Morse functions
under consideration are excellent without loss of generality, because we can
always perturb the real values to ensure distinct real values.

######  Definition 2.3.

Let $f$ be a discrete Morse function. A gradient vector field $V$
corresponding to $f$ is the collection of pairs $(\alpha^{(p)},\beta^{(p+1)})$
satisfying $\alpha^{(p)}\prec\beta^{(p+1)}$ and $f(\alpha)\geq f(\beta)$. We
call such a pair $(\alpha^{(p)},\beta^{(p+1)})$ a gradient pair. Given a
gradient vector field $V$, a gradient $V$-path is a sequence of simplices

$\alpha_{0}^{(p)},\beta_{0}^{(p+1)},\alpha_{1}^{(p)},\beta_{1}^{(p+1)},\cdots,\beta_{r}^{(p+1)},\alpha_{r+1}^{(p)}$

such that for each $i=0,\cdots,r$, $(\alpha^{(p)},\beta^{(p+1)})\in V$ and
$\beta_{i}^{(p+1)}\succ\alpha_{i+1}^{(p)}\neq\alpha_{i}^{(p)}.$

By Definitions 2.2 and 2.3, a simplex is in the gradient vector field if and
only if it is non-critical. Consequently, if a simplex is $f$-critical (non-
critical), it can also be referred to as $V$-critical (non-critical).

We denote a gradient $V$-path $\gamma$ consisting of $p$ and
$(p+1)$-dimensional simplices from $\alpha_{0}^{(p)}$ to $\alpha_{r+1}^{(p)}$
by

$\gamma:\alpha_{0}^{(p)}\mathrel{\stackunder[2pt]{\stackon[4pt]{\rightsquigarrow}{\scriptscriptstyle
V(p,p+1)}}{\scriptscriptstyle}}\alpha_{r+1}^{(p)}.$

Note that we can also take any $(p+1)$-dimensional simplex $\beta_{0}^{(p+1)}$
as the starting simplex, and $\beta_{r}^{(p+1)}$ as the ending simplex. Thus,
we can denote the corresponding path consisting of $p$\- and
$(p+1)$-dimensional simplices by

$\gamma:\beta_{0}^{(p+1)}\mathrel{\stackunder[2pt]{\stackon[4pt]{\rightsquigarrow}{\scriptscriptstyle
V(p,p+1)}}{\scriptscriptstyle}}\beta_{r}^{(p+1)}.$

We say that two gradient paths $\gamma_{1},\gamma_{2}$ are the same path if
all elements of two paths are the same, denoted $\gamma_{1}=\gamma_{2}$. A
trivial path is a gradient $V$-path that consists of only one simplex.

######  Definition 2.4.

For $c\in\mathbb{R}$, we define the sub-level complex

$K(c)=\bigcup_{\sigma\in K,f(\sigma)\leq c}\bigcup_{\tau\leq\sigma}\tau.$

$K(c)$ is the sub-complex of $K$ consisting of all simplices $\tau$ with
$f(\tau)\leq c$ and their faces.

The followings are fundamental theorems in discrete Morse theory. Proofs can
be found in [5, 6].

######  Theorem 2.5 ([6, Thm. 3.3]).

If $a<b$ are real numbers such that $[a,b]$ contains no critical values of f,
then $K(b)$ is homotopy equivalent to $K(a)$.

######  Theorem 2.6 ([5, Thm. 2.11]).

Let $C_{q}$ be the number of critical simplices of dimension $q$. Then,

  1. (1)

for any $i\in\mathbb{N}$,

$C_{i}-C_{i-1}+\cdots\pm C_{0}\geq\beta_{i}-\beta_{i-1}+\cdots\pm\beta_{0},$

where $\beta_{q}$ is the $q$-th Betti number.

  2. (2)

for any $i\in\mathbb{N}$,

$C_{i}\geq\beta_{i}.$

  3. (3)

$\chi(K)=\beta_{0}-\beta_{1}+\beta_{2}-\cdots\pm\beta_{dimK}=C_{0}-C_{1}+C_{2}-\cdots\pm
C_{dimK},$ where $\chi(K)$ is the Euler characteristic number of $K$.

The inequalities above are commonly referred to as the weak discrete Morse
inequality and the strong discrete Morse inequality, respectively.

##  3\. Persistence pairs of discrete Morse functions

Given a discrete Morse function $f:K\to\mathbb{R}$, we recall the concept of a
persistence pair, which consists of two critical simplices of $f$ and
describes the birth and death of a homology class. Then, we study some useful
properties of persistence pairs. Some of them are not complicated when we
consider them at the level of discrete Morse complexes, see Forman [5] and
Section 3.1 of Bauer [2]. Nonetheless, in order to thoroughly examine the
connectivity and strong connectivity between critical simplices of different
discrete Morse functions, which is our primary goal in Section 4, a clear
description at the level of simplicial complex $K$ is necessary.

We first define the filtration associated to $f$ of a simplcial complex and
its homology in discrete Morse theory by applying Definition 2.4. Recall we
always assume discrete Morse functions to be excellent.

######  Definition 3.1.

Given a discrete Morse function $f:K\to\mathbb{R}$, let
$c_{1}<c_{2}<\cdots<c_{n}$ be a sequence of increasing real numbers and
$K(c_{i})$ be the sub-level complex at value $c_{i}$. We call

$K(c_{1})\subset K(c_{2})\subset\cdots\subset K(c_{n})$

a filtration of $K$ associated to $f$, where $K(c_{n})=K$. For convenience, if
$f(\sigma)=c$, then we use both $K(c)$ and $K(\sigma)$ to represent the sub-
level complex at value $c$ or $f(\sigma)$.

Note that if a discrete Morse function $f:K\to\mathbb{R}$ is restricted to a
sub-complex $K_{i}$, then $f|_{K_{i}}$ is still a discrete Morse function. A
discrete Morse function provides local information of $K$. Specifically,
whether a simplex of $K$ is critical or not remains consistent when we
consider each sub-complex $K(c_{i})$ of $K$. This property is formalized in
the following lemma.

######  Lemma 3.2.

Let $K(c_{1})\subset K(c_{2})\subset\cdots\subset K(c_{n})$ be a filtration of
$K$ associated to $f$. If $\sigma$ is a critical (or non-critical) simplex of
$K(c_{i})$ for some $i$, then $\sigma$ is also a critical (or non-critical)
simplex of $K(c_{j})$ for all $j>i.$

###### Proof.

To prove the critical case, we let $\sigma$ be a $q$-dimensional critical
simplex in $K(c_{i})$ and $j>i$. Since $\sigma$ is a critical simplex of
$K(c_{i})$, by definition,

  1. (1)

for any $\alpha^{(q-1)}\in K(c_{i})$ with $\alpha^{(q-1)}\prec\sigma$,
$f(\alpha)<f(\sigma)$;

  2. (2)

for any $\tau^{(q+1)}\in K(c_{i})$ with $\tau^{(q+1)}\succ\sigma$,
$f(\tau)>f(\sigma).$

The second statement still holds for all $\tau^{(q+1)}\in K(c_{j})$, since
$j>i$. Furthermore, by the definition of sub-level complex, since $\sigma$ is
in $K(c_{i})$, all the faces of $\sigma$ are also in $K(c_{i})$. Hence,
statement (1) still holds for $K(c_{j})$.

A similar proof can also be applied to the non-critical case.

∎

Note that the statement in Lemma 3.2 may fail to hold for general objects
other than simplicial complexes. In paper [4], the authors define the discrete
Morse theory for posets, and a similar statement to Lemma 3.2 for posets does
not hold.

By applying the simplicial homology functor to the filtration, we obtain a
sequence of homology groups and inclusion-induced homomorphisms. For each
homology class, we can use a pair of simplices to describe its birth and
death. A homology class $[h]$ is said to be born at a certain $f$-value
$c_{i}$, if $[h]$ is not in the image of $H_{\star}(K(c_{i-1}))$. On the other
hand, a homology class $[h]$ is said to persist at $c_{i}$, if the image of
$[h]$ in $H_{\star}(K(c_{i+1}))$ is non-zero, otherwise, it is said to die at
$c_{i}$. If there exists some simplex $\sigma$ with $f(\sigma)=c_{i}$, then we
also say that the homology class $[h]$ is born at $\sigma$, or dies at
$\sigma$. To precisely describe the persistence of a cycle, the elder rule is
applied. The elder rule is to let the death simplex always be paired with the
youngest birth simplex.

######  Definition 3.3.

A pair of simplices $(\sigma,\tau)$ is called a persistence pair if there is a
homology class $[h]$ that is born at $\sigma$ and dies at $\tau$. $\sigma$ is
referred to as the birth simplex, and $\tau$ is referred to as the death
simplex of $[h]$. In the case where $[h]$ is born at $\sigma$ and does not
die, we say that $\sigma$ is paired with infinity, denoted $(\sigma,\infty)$.

This is a well-defined definition because we assume the discrete Morse
function being excellent and the elder rule is applied. Note that in [2], the
birth simplex and death simplex are also called the positive cell and negative
cell, respectively.

We call the dimension of a homology class $[h]$ to be the dimension of the
simplices of a representative chain. Then, the following statements about
persistent pairs hold true under the conditions of discrete Morse function and
the elder rule.

######  Proposition 3.4.

Let $f$ be a discrete Morse function on $K$. Suppose that $[h]$ is a
$q$-dimensional homology class with persistent pair $(\sigma,\tau)$. Then

  1. (1)

$\dim\sigma=q$;

  2. (2)

$\dim\tau=q+1$;

  3. (3)

$[h]$ is represented by a cycle $z=\sum_{i}n_{i}\sigma_{i}$ such that
$\sigma=\sigma_{j}$, for some $j$.

###### Proof.

To prove the first statement, since the $\dim\sigma$ can not be smaller than
$q$, we assume the opposite, that is, $\dim\sigma>q.$

Since $[h]$ is born at $\sigma$, there exists at least one
$\alpha\prec\sigma$, such that $\dim\alpha=q$, and $\alpha$ is a part of some
representative chain of $[h]$. We write the chain $z$ as
$z=\sum_{i}n_{i}\alpha_{i},$ where there exists at least one index $j$ such
that $\alpha=\alpha_{j}$ and $n_{j}=1.$

If there are multiple such $\alpha$ satisfying the conditions, without loss of
generality, we label them as $\alpha_{1},\cdots,\alpha_{K}$. Considering any
two $\alpha_{k}\prec\sigma$ and $\alpha_{l}\prec\sigma$ of them, since
$\sigma$ is a simplex, by definition, there exists a $(q+1)$-dimensional
simplex $\delta$ with $a_{k}$ and $a_{l}$ as faces. Since $[h]$ is born at
$\sigma$, we have $f(\sigma)<f(\delta^{(q+1)})<f(a_{k}^{(q)}),$ and
$f(\sigma)<f(\delta^{(q+1)})<f(a_{j}^{(q)}),$ which contradicts the definition
of a discrete Morse function.

On the other hand, if there is only one such $\alpha$, since $\sigma$ is a
simplex, there exists a $(q+1)$-dimensional face $\delta^{(q+1)}\prec\sigma$,
such that $\alpha\prec\delta$ and $f(\alpha)>f(\delta)$. Let
$z=\sum_{i}n_{i}\alpha_{i}$ be a representative chain of $[h]$ with
$\alpha=\alpha_{j}$ and $n_{j}=1$ for some index $j$. Since $f$ is a discrete
Morse function, by definition, $f(\alpha)>f(\delta)>f(\tilde{\alpha})$, for
any $\tilde{\alpha}\neq\alpha$ in the boundary of $\delta$. Let $\tilde{z}$ be
the chain consisting of all elements in $z$ except $\alpha$, and all elements
of the boundary of $\delta$ except $\alpha$. Then $z$ is homologous to
$\tilde{z}$, contradicting the fact that $[h]$ is born at $\sigma$ as
$\tilde{z}$ appears earlier than $\sigma$.

A similar proof also applies to statement (2). The third statement is
straightforward after proving (1) and (2). ∎

######  Proposition 3.5.

Let $f$ be a discrete Morse function. If $(\sigma^{(q)},\tau^{(q+1)})$ is a
persistence pair of $f$, then both $\sigma$ and $\tau$ are $f$-critical.

###### Proof.

Suppose that $(\sigma^{(q)},\tau^{(q+1)})$ is a persistence pair. To prove
$\sigma$ is $f$-critical, consider any $(q-1)$-dimensional face
$\alpha^{(q-1)}\prec\sigma$. By Proposition 3.4 (3), there exists a cycle
$z=\sum_{i}n_{i}\sigma_{i},$ with $\sigma_{j}=\sigma,n_{i}=1$, for some index
$j$. Since $\sigma$ is a simplex, any $(q-1)$-dimensional face
$\alpha^{(q-1)}\prec\sigma$ is the intersection of $\sigma$ and $\sigma_{k}$
for some $k$ in the cycle $z$. Note that $f(\sigma)>f(\sigma_{k}),$ as $z$ is
born at $\sigma$. Thus, by the definition of discrete Morse function,
$f(\sigma)>f(\alpha).$ The proof for the statement that for any
$(q+1)$-dimensional simplex $\delta^{(q+1)}$ such that
$\delta^{(q+1)}\succ\sigma$, it has a larger $f$-value than $\sigma$, is
similar to the proof given in Proposition 3.4.

Next, we prove that $\tau$ is $f$-critical. By Proposition 3.4 (2), we have
$\dim\tau=q+1.$ Suppose $\rho^{(q)}\prec\tau$. Since $(\sigma,\tau)$ is a
persistence pair, every element $\rho_{i}$ of the boundary of $(\tau)$
satisfies $f(\tau)>f(\rho_{i}).$ The rest is similar to the proof given in
Proposition 3.4. ∎

According to Proposition 3.5, we can classify critical simplices based on the
structure of their persistence pairs. We define the dimension of a persistence
pair as the dimension of its birth simplex.

######  Theorem 3.6.

Let $\sigma^{(q)}$ be a critical simplex. Then, $\sigma^{(q)}$ is in exactly
one of the three following kinds of persistence pairs:

  1. (1)

a $q$-dimensional persistence pair $(\sigma^{(q)},\tau^{(q+1)})$;

  2. (2)

a $(q-1)$-dimensional persistence pair $(\alpha^{(q-1)},\sigma^{(q)})$;

  3. (3)

a $q$-dimensional persistence pair consisting of infinity
$(\sigma^{(q)},\infty)$.

Note that in [1], when $K$ is a graph, the type (3) critical simplices are
referred to as essential vertices and essential edges when $q=0$ and $q=1$,
respectively. The other types of critical simplices are called superfluous.

A gradient pair provides information locally because it only captures of the
ordering information of the neighbourhood of an element. A persistent pair, on
the other hand, contains global order information for a specific dimension,
hence it provides global information. Notably, only critical simplices paired
with infinity contribute to the homology of the underlying space, as those
cycles persist until the end of the filtration. Recall Theorem 2.6, the Morse
inequalities, which establishes a connection between the number of
$q$-dimensional critical simplices and $q$-th Betti number. Therefore, as a
corollary, we can use the structures of persistence pairs to re-write the
Morse inequalities as equations, providing a more refined understanding of the
relationship between critical simplices and homology. A similar result for the
graph case is given in [1].

Let $P_{q}$ be the set of persistence pairs whose birth simplices have
dimension $q$. Let $\hat{P}_{q}$ be the set of persistence pairs whose birth
simplices have dimension $q$ and death simplices are not infinity. Then,
$\hat{P}_{q}\subset P_{q},$ and the $q$-th Betti number is given by
$\beta_{q}=\\#P_{q}-\\#\hat{P}_{q}.$

######  Corollary 3.7.

The Morse inequality in Theorem 2.6 can be re-written as an equation

$C_{q}=\beta_{q}+\\#\hat{P}_{q-1}+\\#\hat{P}_{q}.$

Moreover, the strong and weak Morse inequalities become more explicit as well.

######  Corollary 3.8.

Let $K$ be a simplicial complex, and the dimension of $K$ is $n$. Then

$C_{n}-C_{n-1}+\cdots\pm C_{0}=\beta_{n}-\beta_{n-1}+\cdots\pm\beta_{0}.$

Also, for $i=0,1,\cdots,n,$

$C_{i}-C_{i-1}+\cdots\pm
C_{0}=\beta_{i}-\beta_{i-1}+\cdots\pm\beta_{0}+\\#\hat{P}_{i}.$

###### Proof.

We first prove the second equation. For any $i=0,1,\cdots,n,$ we calculate the
left side of the equation using Corollary 3.7.

$\displaystyle C_{i}-C_{i-1}+\cdots\pm C_{0}$
$\displaystyle=(\beta_{i}+\\#\hat{P}_{i-1}+\\#\hat{P}_{i})$
$\displaystyle-(\beta_{i-1}+\\#\hat{P}_{i-2}+\\#\hat{P}_{i-1})$
$\displaystyle+\quad\quad\quad\vdots$
$\displaystyle\pm(\beta_{0}+\\#\hat{P}_{-1}+\\#\hat{P}_{0}).$

Since $\\#\hat{P}_{-1}=0,$ the second equation holds.

For the first equation, suppose that $i=k$. Then, since $\\#\hat{P}_{n}=0$,
the first equation holds, as well. ∎

##  4\. Strong connection of discrete Morse functions on graphs

In this section, we explore the relationship between multiple discrete Morse
functions on a simplicial complex. We begin this section by defining
connectedness between critical simplices in different gradient vector fields.
The definition is initially introduced in [7]. The connectedness relationship
is a binary relationship (but not an equivalence relationship) between two
critical simplices with the same dimension in two distinct gradient vector
fields. Consequently, the connection relationship between two simplices also
reveals the relationship between the corresponding functions. The precise
definition is given as follows.

######  Definition 4.1.

[7]. Let $K$ be a simplicial complex, and $\\{f_{i}\\}$ be a family of
discrete Morse functions on $K$. For each $i$, let $V_{i}$ be the
corresponding gradient vector field of $f_{i}$. Suppose that $\alpha$ and
$\beta$ are $q$-dimensional simplices of $K$, and $\alpha$ is critical in
$V_{i}$, and $\beta$ is critical in $V_{j}$, $j\neq i$.

We say that $\alpha$ is connected to $\beta$ if there are a $q$-dimensional
simplex $\sigma$ and gradient paths
$\alpha\mathrel{\stackunder[2pt]{\stackon[4pt]{$\rightsquigarrow$}{$\scriptscriptstyle
V_{i}(q-1,q)$}}{$\scriptscriptstyle$}}\sigma$ and
$\sigma\mathrel{\stackunder[2pt]{\stackon[4pt]{$\rightsquigarrow$}{$\scriptscriptstyle
V_{j}(q,q+1)$}}{$\scriptscriptstyle$}}\beta.$ We denote by $\alpha\to\beta$,
if $\alpha$ is connected to $\beta$. We also define that $\alpha$ is strongly
connected to $\beta$ if $\alpha$ is connected to $\beta$ and $\beta$ is
connected to $\alpha$, denoted $\alpha\leftrightarrow\beta$.

For more detailed information and applications of connectedness, one refers to
[7]. Note that by definition, $\alpha\leftrightarrow\alpha$. Additionally, if
$\alpha$ is critical at both $V_{i}$ and $V_{j}$, then $\alpha$ is strongly
connected to itself by the trivial path.

Let $f_{1},f_{2}$ be discrete Morse functions on $K$, $\tilde{\sigma}_{1}$,
$\tilde{\sigma}_{2}$ be $f_{1}$,$f_{2}$-critical simplex, respectively. Given
the concept of connectedness between critical simplices in two different
gradient vector fields, it is natural to consider the following problems:

  1. (1)

Let $A_{q}^{f_{1},f_{2}}(K)$ be the number of strongly connected pairs of
$q$-dimensional simplices between $f_{1}$ and $f_{2}$. Does
$A_{q}^{f_{1},f_{2}}(K)$ depend on $\beta_{q}(K)$?

  2. (2)

Suppose that $\tilde{\sigma}_{1}$ is strongly connected to
$\tilde{\sigma}_{2}$. Under what conditions is the gradient path connecting
them unique?

  3. (3)

(Posed in [7]) Suppose that $\tilde{\sigma}_{1}$ is strongly connected to
$\tilde{\sigma}_{2}$. Under what conditions is $\tilde{\sigma}_{1}$ not
strongly connected to any other simplices of $f_{2}$ except
$\tilde{\sigma}_{2}$?

In this section, we will investigate the connectedness relationship in the
case of simple graph and provide solutions to the aforementioned problems. A
simple graph $G$ is a graph that does not contain loops or parallel edges,
making it equivalent to a one-dimensional simplicial complex. Discrete Morse
theory on graphs is not complicated, and several interesting and fundamental
properties are introduced in Kozlov [8] and Ayala et al [1].

With regard to the connectedness between $\tilde{\sigma}_{1}^{(q)}$ and
$\tilde{\sigma}_{2}^{(q)}$ on a graph, when $q=0$, $\tilde{\sigma}_{1}$ is
connected to $\tilde{\sigma}_{2}$ if there is a gradient path
$\tilde{\sigma}_{1}\mathrel{\stackunder[2pt]{\stackon[4pt]{$\rightsquigarrow$}{$\scriptscriptstyle
V_{2}(0,1)$}}{$\scriptscriptstyle$}}\tilde{\sigma}_{2}$; when $q=1$,
$\tilde{\sigma}_{1}$ is connected to $\tilde{\sigma}_{2}$ if there is a
gradient path
$\tilde{\sigma}_{1}\mathrel{\stackunder[2pt]{\stackon[4pt]{$\rightsquigarrow$}{$\scriptscriptstyle
V_{1}(0,1)$}}{$\scriptscriptstyle$}}\tilde{\sigma}_{2}$;

######  Remark 4.2.

To address the higher dimensional cases, we plan to present another paper [13]
to give solutions to the aforementioned problems.

We begin with a simple case by assuming that the discrete Morse functions
$f_{1},f_{2}$ are optimal. We define a discrete Morse function to be optimal
(or perfect) if, for each $n$, the number of $n$-dimensional critical
simplices $C_{n}$ equals the $n$-th Betti number $\beta_{n}$ [1]. For $i=1,2$,
we use $\tilde{v}_{i},\tilde{e}_{i}$ to represent $0$-, $1$-dimensional
$f_{i}$-critical simplices, respectively.

######  Proposition 4.3.

Let $G$ be a graph and

$f_{1},f_{2}:G\to\mathbb{R}$

be optimal discrete Morse functions, $q=0,1$. For each $q$-dimensional
homology class $[\alpha]$, suppose that $[\alpha]$ is born at
$\tilde{\sigma}^{(q)}_{1}$ in $f_{1}$ and $\tilde{\sigma}^{(q)}_{2}$ in
$f_{2}$. Then, $\tilde{\sigma}_{1}$ is strongly connected to
$\tilde{\sigma}_{2}.$

###### Proof.

We assume that $\tilde{\sigma}_{1}\neq\tilde{\sigma}_{2}$, as the result is
trivial when $\tilde{\sigma}_{1}=\tilde{\sigma}_{2}$. Since $[\alpha]$ is born
at $\tilde{\sigma}_{1}$ in $f_{1}$ and at $\tilde{\sigma}_{2}$ in $f_{2}$,
$\tilde{\sigma}_{1}$ and $\tilde{\sigma}_{2}$ are in persistent pairs
$(\tilde{\sigma}_{1},\infty)$ and $(\tilde{\sigma}_{2},\infty)$ of $f_{1}$ and
$f_{2}$, respectively.

When $q=0,$ to show $\tilde{v}_{1}\to\tilde{v}_{2},$ it suffices to show the
existence of an $f_{2}$-gradient path connecting $\tilde{v}_{1}$ and
$\tilde{v}_{2}$. Since $f_{2}$ is optimal, there are no other $(v,\infty)$ or
$(v,e)$ type critical simplices in the connected component generated by
$[\alpha]$. Therefore, it suffices to show that there is a path from
$\tilde{v}_{1}$ to $\tilde{v}_{2}$ in which all $1$-dimensional simplices $e$
are non-critical.

Suppose that there is an $f_{2}$-critical simplex $e$ in the path. Then,
$(e,\infty)$ is an $f_{2}$-persistence pair, and we can always find an
alternative path that consists of the elements of the cycle and flows towards
to $\tilde{v}_{2}$. As $G$ is finite, we can repeat this procedure to obtain
the desired gradient path.

When $q=1,$ $\tilde{e}_{1}$ and $\tilde{e}_{2}$ belong to the same cycle.
Since $[\alpha]$ is born at $\tilde{e}_{1}$ in $f_{1}$,
$f_{1}(\tilde{e}_{1})>f_{1}(\tilde{e}_{2})$. When $f_{1}$ is optimal, there is
always one gradient $f_{1}$-gradient path connecting $\tilde{e}_{1}$ and
$\tilde{e}_{2}$. Thus, $\tilde{e}_{1}\to\tilde{e}_{2}$.

Therefore, since both $f_{1}$ and $f_{2}$ are optimal, we have
$\tilde{v}_{1}\leftrightarrow\tilde{v}_{2}$ and
$\tilde{e}_{1}\leftrightarrow\tilde{e}_{2}$. ∎

######  Corollary 4.4.

Let $G$ be a graph and

$f_{1},f_{2}:G\to\mathbb{R}$

be optimal discrete Morse functions. Then,

  1. (1)

$A_{0}^{f_{1},f_{2}}(G)=\beta_{0}(G)$;

  2. (2)

$A_{1}^{f_{1},f_{2}}(G)\geq\beta_{1}(G)$.

###### Proof.

The first equation holds because there are no paths connecting vertices in
different components.

∎

Note that in general cases, $A_{q}^{f_{1},f_{2}}$ may be smaller than
$\beta_{q}$.

######  Proposition 4.5.

Let $G$ be a graph and

$f_{1},f_{2}:G\to\mathbb{R}$

be discrete Morse functions. Let $\tilde{v}_{1}$ and $\tilde{v}_{2}$ be
$0$-dimensional $f_{1}$\- and $f_{2}$-critical simplices, respectively. If
$\tilde{v}_{1}$ is strongly connected to $\tilde{v}_{2}$, then $\tilde{v}_{1}$
is not strongly connected to other critical $f_{2}$-critical simplices and
$\tilde{v}_{2}$ is not strongly connected to other $f_{1}$-critical simplices.
Moreover, the gradient path connecting $\tilde{v}_{1}$ to $\tilde{v}_{2}$ and
the gradient path connecting $\tilde{v}_{2}$ to $\tilde{v}_{1}$ are unique.

###### Proof.

Suppose $\tilde{v}_{1}\leftrightarrow\tilde{v}_{2}$. The second statement
simply follows from the fact that the outdegree of each vertex is at most $1$.
Hence, if there exists an $f_{2}$-critical $\tilde{v}_{2}^{\prime}$ such that
$\tilde{v}_{1}\to\tilde{v}_{2}^{\prime}$, then the gradient path
$\gamma_{1,2^{\prime}}:\tilde{v}_{1}\mathrel{\stackunder[2pt]{\stackon[4pt]{$\rightsquigarrow$}{$\scriptscriptstyle
V_{2}(0,1)$}}{$\scriptscriptstyle$}}\tilde{v}_{2}^{\prime}$ is either a sub-
path of
$\gamma_{1,2}:\tilde{v}_{1}\mathrel{\stackunder[2pt]{\stackon[4pt]{$\rightsquigarrow$}{$\scriptscriptstyle
V_{2}(0,1)$}}{$\scriptscriptstyle$}}\tilde{v}_{2}$, or it contains
$\gamma_{1,2^{\prime}}$. Both cases contradict with the definition of gradient
path, because there is no critical simplex on the gradient path. ∎

From the proof above we can see that there may be two different
$f_{1}$-critical vertices $v_{1}$, $v_{1}^{\prime}$ connecting to one
$f_{2}$-critical vertex $v_{2}$, but $v_{2}$ can not be connected to both of
them. In Proposition 4.3, we assumed the functions to be optimal. Next, we
remove the conditions on $f_{1}$ and $f_{2}$ and instead impose restrictions
on the graph $G$ by assuming that $G$ is a forest.

######  Lemma 4.6.

Let $G$ be a forest, and

$f_{1},f_{2}:G\to\mathbb{R}$

be discrete Morse functions, $q=0,1$. If $\tilde{\sigma}^{(q)}_{1}$ is
strongly connected to $\tilde{\sigma}^{(q)}_{2}$, then they are not strongly
connected to other critical simplices of $f_{2}$ and $f_{1}$, respectively.
Moreover, the gradient path connecting $\tilde{\sigma}^{(q)}_{1}$ and
$\tilde{\sigma}^{(q)}_{2}$ to the gradient path connecting
$\tilde{\sigma}^{(q)}_{2}$ to $\tilde{\sigma}^{(q)}_{1}$ are unique.

###### Proof.

The case $q=0$ follows from Proposition 4.5. When $q=1$, assume that
$\tilde{e}_{1}\leftrightarrow\tilde{e}_{2}$ and
$\tilde{e}_{1}\to\tilde{e}_{2}^{\prime}$. We aim to prove
$\tilde{e}_{2}^{\prime}\not\to\tilde{e}_{1}$. Suppose, for contradiction, that
$\tilde{e}_{2}^{\prime}\to\tilde{e}_{1}$.

Since $\tilde{e}_{1}\to\tilde{e}_{2}$ and
$\tilde{e}_{1}\to\tilde{e}_{2}^{\prime}$, we have two gradient paths
$\gamma_{1,2}:\tilde{e}_{1}\mathrel{\stackunder[2pt]{\stackon[4pt]{$\rightsquigarrow$}{$\scriptscriptstyle
V_{1}(0,1)$}}{$\scriptscriptstyle$}}\tilde{e}_{2}$ and
$\gamma_{1,2^{\prime}}:\tilde{e}_{1}\mathrel{\stackunder[2pt]{\stackon[4pt]{$\rightsquigarrow$}{$\scriptscriptstyle
V_{1}(0,1)$}}{$\scriptscriptstyle$}}\tilde{e}_{2}^{\prime}$. These paths
either start from the same non-critical face of $\tilde{e}_{1}$ or from to two
different non-critical faces of $\tilde{e}_{1}$. Since $G$ is a forest,
gradient paths
$\gamma_{2,1}:\tilde{e}_{2}\mathrel{\stackunder[2pt]{\stackon[4pt]{$\rightsquigarrow$}{$\scriptscriptstyle
V_{2}(0,1)$}}{$\scriptscriptstyle$}}\tilde{e}_{1}$ and
$\gamma_{2^{\prime},1}:\tilde{e}_{2}^{\prime}\mathrel{\stackunder[2pt]{\stackon[4pt]{$\rightsquigarrow$}{$\scriptscriptstyle
V_{2}(0,1)$}}{$\scriptscriptstyle$}}\tilde{e}_{1}$ have to be the reverse
paths of $\gamma_{1,2}$ and $\gamma_{1,2^{\prime}}$, respectively.

In the former case, either $\gamma_{1,2}$ or $\gamma_{1,2^{\prime}}$ is a sub-
path of the other. This contradicts the definition of a gradient path. In the
latter case, it contradicts the fact that $\tilde{e}_{1}$ cannot be part of
both gradient pairs associated with its two faces.

The uniqueness of gradient paths is trivial.

∎

Note that in the above lemma, although we suppose that $G$ is a forest, we can
relax the condition to “the subgraph consisting of all paths connecting
$\tilde{\sigma}_{1}$ and $\tilde{\sigma}_{2}$ does not contain cycles”.

######  Proposition 4.7.

Let $G$ be a cyclic graph, and

$f_{1},f_{2}:G\to\mathbb{R}$

be discrete Morse functions. Then, the following statements hold.

  1. (1)

If $\sigma_{1}$ is connected to $\sigma_{2}$, then the gradient path
connecting them is unique.

  2. (2)

$A_{0}^{f_{1},f_{2}}(G)=A_{1}^{f_{1},f_{2}}(G).$

###### Proof.

Statement (1) is trivial because there are always two paths connecting
$\tilde{e}_{1}$ and $\tilde{e}_{2}$, and one of them contains $\tilde{v}_{1}$,
where $(\tilde{v}_{1},\infty)$ is a persistence pair of $f_{1}$, hence it is
not a gradient path. Additionally, Proposition 4.5 gives a proof to the case
$q=0.$

To prove statement (2), suppose that $(\tilde{v}_{1},\infty)$ are
$(\tilde{e}_{1},\infty)$ are persistence pairs for the cycle in $f_{1}$.
Without loss of generality, we order the $f_{1}$-critical simplices by
considering the paths connecting $\tilde{e}_{1}$ and $\tilde{v}_{1}$ as
follows $(n,m\geq 1)$:

$\gamma_{1}:\tilde{e}_{1},v_{1}^{1},e_{1}^{1},\ldots,v_{n}^{1},e_{n}^{1},\tilde{v}_{1},$

and

$\gamma_{2}:\tilde{e}_{1},v_{1}^{2},e_{1}^{2},\ldots,v_{m}^{2},e_{m}^{2},\tilde{v}_{1}.$

It is easy to check that the statement holds for the cases $n=0$ or $m=0$.
Note that $1$-dimensional critical simplices always appear after
$0$-dimensional critical simplices in the above sequence.

For any interval containing the endpoints starting from $v_{i}$ to $e_{i}$ in
$\gamma_{1}$ or $\gamma_{2}$, the $f_{1}$ flow is either trivial when
$v_{i}\prec e_{i}$, or is from $e_{i}$ to $v_{i}$ otherwise. Similarly, the
same result holds when considering the interval starting from $e_{i}$ to
$v_{i+1}$, $\tilde{e}_{1}$ to $v_{1}^{1}$ and $e_{n}^{1}$ to $\tilde{v}_{1}.$
We investigate the types of $f_{2}$-critical simplices and the variation of
$A_{q}^{f_{1},f_{2}}(G)$ in the interval. Let $\overline{v}$ and
$\overline{e}$ be $0$\- and $1$-dimensional $f_{2}$-critical simplices,
respectively.

  1. (1)

When there is only one $f_{2}$-critical $1$-dimensional simplex $\overline{e}$
in the interval, we have $e_{i}\leftrightarrow\overline{e}$, and there is no
other strong connection in the interval. Hence, $A_{1}^{f_{1},f_{2}}$
increases by one, and $A_{0}^{f_{1},f_{2}}$ does not change.

  2. (2)

When there is only one $f_{2}$-critical $0$-dimensional simplex $\overline{v}$
in the interval, we have $v_{i}\leftrightarrow\overline{v}$, and there is no
other strong connection in the interval. Hence, $A_{0}^{f_{1},f_{2}}$
increases by one, and $A_{1}^{f_{1},f_{2}}$ does not change.

  3. (3)

Suppose that there are multiple $f_{2}$-critical simplices with $\overline{e}$
being the first one and $\overline{v}$ being the last one in the interval.
Then, $e_{i}\leftrightarrow\overline{e}$, and
$v_{i}\leftrightarrow\overline{v}$. Hence, both $A_{1}^{f_{1},f_{2}}$ and
$A_{0}^{f_{1},f_{2}}$ increase by one.

  4. (4)

Suppose that there are multiple $f_{2}$-critical simplices with $\overline{v}$
being the first one and $\overline{e}$ being the last one in the interval.
Then, there is no strong connection in the interval. Hence, neither
$A_{1}^{f_{1},f_{2}}$ nor $A_{0}^{f_{1},f_{2}}$ change.

  5. (5)

Suppose that there are multiple $f_{2}$-critical simplices with $\overline{e}$
being the first one and $\overline{e^{\prime}}$ being the last one in the
interval. Then, $e_{i}\leftrightarrow\overline{e}$. Hence,
$A_{1}^{f_{1},f_{2}}$ increases by one, and $A_{0}^{f_{1},f_{2}}$ does not
change.

  6. (6)

Suppose that there are multiple $f_{2}$-critical simplices with $\overline{v}$
being the first one and $\overline{v^{\prime}}$ being the last one in the
interval. Then, $v_{i}\leftrightarrow\overline{v}$. Hence,
$A_{0}^{f_{1},f_{2}}$ increases by one, and $A_{1}^{f_{1},f_{2}}$ does not
change.

Since $G$ is a cyclic graph, $C_{0}^{f_{2}}(G)=C_{1}^{f_{2}}(G).$ In cases
(1), (5), the number of $1$-dimensional $f_{2}$-critical simplices contained
in the interval is one more than $0$-dimensional $f_{2}$-critical simplices
contained in the interval. In cases (2), (6), the number of $0$-dimensional
$f_{2}$-critical simplices contained in the interval is one more than
$1$-dimensional $f_{2}$-critical simplices contained in the interval. In cases
(3), (4), the number of $0$-dimensional $f_{2}$-critical simplices contained
in the interval is the same as $1$-dimensional $f_{2}$-critical simplices
contained in the interval.

Hence, if we sum up all the intervals, then the sum of cases (1) and (5) must
equal the sum of cases (2) and (6). Therefore, the difference between
$A_{0}^{f_{1},f_{2}}(G)$ and $A_{1}^{f_{1},f_{2}}(G)$ equal the difference
between $C_{0}^{f_{2}}(G)$ and $C_{1}^{f_{2}}(G)$, and
$A_{0}^{f_{1},f_{2}}(G)=A_{1}^{f_{1},f_{2}}(G).$ ∎

Proposition 4.7 can be generalized by considering the set of gradient paths
connecting $1$-dimensional critical simplices and $0$-dimensional critical
simplices. In [1], the rooted tree of a discrete Morse function on $G$ is
introduced to study the structure of the gradient vector field. Moreover, in
[3], the rooted tree is applied to investigate the complex of discrete Morse
functions. We cite the definition as follows. For a detailed explanation and
comprehensive discussion on the rooted tree and its applications, the reader
may refer Section 4 of [1].

######  Definition 4.8.

Let $G$ be a graph, and $f:G\to\mathbb{R}$ be discrete Morse functions. Given
any $0$-critical element $v$, the set of all gradient paths rooted in it forms
a tree called the tree rooted in v, denoted as $T^{f}_{v}$. When the context
is clear, we omit $f$.

Since any two of such rooted trees are disjoint, we call the set consisting of
all rooted trees $\\{T_{v}\\}$ the rooted forest. The rooted forest can be
obtained by removing all critical edges of $f$.

The tree rooted in $v$ contains two sets of gradient paths: the gradient paths
that originate from the faces of $1$-dimensional critical simplices to $v$ and
the gradient paths that do not start from any face of $1$-dimensional critical
simplices. The former set is denoted $\\{\overline{\gamma_{e,v}}\\}_{e},$
where $e$ is a $1$-dimensional critical simplex. On the other hand, the latter
set is denoted $\overline{\gamma_{v}}$. $\overline{\gamma_{v}}$ consists of
branches ending at $v$, with each branch represented $B_{i}$, $i=1,2\ldots n$.
Note that the branch set may be empty for some graphs, for example, the cyclic
graphs we consider above. Hence, the branch set is also the main difficulty to
generalize the proof for cyclic graphs to general graphs.

We call the union $\overline{\gamma_{e,v}}\cup\overline{\gamma_{v}}$, which is
a subgraph of $T_{v}$, the tree of $e$ rooted in $v$, denoted $T_{e,v}$.

######  Example 4.9.

Figure 1 depicts an example of a discrete Morse function, denoted as $f_{1}$,
on graph $G$. The gradient vector field on $G$ is represented by arrows.
Critical simplices within the graph, marked in red, consist of three
$0$-dimensional simplices $v_{1}^{1},v_{1}^{2},v_{1}^{3}$, and three
$1$-dimensional simplices $e_{1}^{1},e_{1}^{2},e_{1}^{3}$.

The rooted tree of vertex $v_{1}^{2}$ is illustrated in Figure 2. The rooted
tree comprises gradient paths $\overline{\gamma_{e_{1}^{1},v_{1}^{2}}},$
$\overline{\gamma_{e_{1}^{2},v_{1}^{2}}}$,
$\overline{\gamma_{e_{1}^{3},v_{1}^{2}}}$ along with an additional branch.
Note that $\overline{\gamma_{e_{1}^{3},v_{1}^{2}}}$ is contained in
$\overline{\gamma_{e_{1}^{1},v_{1}^{2}}}$ and
$\overline{\gamma_{e_{1}^{2},v_{1}^{2}}}$.

$e_{1}^{2}$$e_{1}^{3}$$v_{1}^{1}$$e_{1}^{1}$$v_{1}^{2}$$v_{1}^{3}$ Figure 1.
Graph $G$ with discrete Morse function $f_{1}$.

######  Theorem 4.10.

Let $G$ be a graph, and

$f_{1},f_{2}:G\to\mathbb{R}$

be discrete Morse functions. Then,

$A_{0}^{f_{1},f_{2}}(G)-A_{1}^{f_{1},f_{2}}(G)=\beta_{0}(G)-\beta_{1}(G)=\chi(G),$

where $\chi(G)$ is the Euler characteristic of the graph $G$.

###### Proof.

Let $v^{1}$ and $e^{1}$ be $0$-, $1$-dimensional $f_{1}$-critical simplices,
respectively. Following the approach used in the proof of Proposition 4.7, we
consider the $f_{2}$-critical sequence of simplices in the tree of $e^{1}$
rooted in $v^{1}$
$T^{f_{1}}_{e^{1},v^{1}}=\overline{\gamma_{e^{1},v^{1}}}\cup\overline{\gamma_{v^{1}}}$.
If $e^{1}$ is also $f_{2}$-critical, then $e^{1}\leftrightarrow e^{1}$ via
trivial paths. Note that if there is any $f_{2}$-critical edge $e^{2}$ in
$\overline{\gamma_{e^{1},v^{1}}}$, then $e^{1}\to e^{2}$. Also, if there is
any $f_{2}$-critical edge $e^{2}$ in $\overline{\gamma_{v^{1}}}$, then there
is no $f_{1}$-critical edge that is connected to $e^{2}$. Finally, if there is
any $f_{2}$-critical vertex $v^{2}$ in $T_{e^{1},v^{1}}$, then $v^{2}\to
v^{1}$.

First, we discuss the branch set $\overline{\gamma_{v^{1}}}$. Let $B_{i}$ be a
branch starting at $v_{i}^{1}$ ending at $v^{1}$. We consider the sequence of
$f_{2}$-critical simplices between $v_{i}^{1}$ and $v^{1}$, always beginning
with a $0$-dimensional simplex. We introduce two additional cases in addition
to the cases (1) to (6) from the proof of Proposition 4.7.

  1. (7)

When the sequence of $f_{2}$-critical simplices starts at a $0$-dimensional
simplex and ends at a $1$-dimensional simplex, neither $A_{0}$ nor $A_{1}$
changes.

  2. (8)

When the sequence of $f_{2}$-critical simplices starts at a $0$-dimensional
simplex ends at a $0$-dimensional simplex, $A_{0}$ increases by one while
$A_{1}$ does not change.

Next, we modify the cases (1) to (6) from the proof of Proposition 4.7 for
$\overline{\gamma_{e^{1},v^{1}}}$. In the context of a general graph $G$, an
$f_{2}$-critical simplex $e_{2}$ may not be connected to $e^{1}$, even if
$e_{2}$ is the first $f_{2}$-critical edge of the $f_{2}$-critical sequence in
$\overline{\gamma_{e^{1},v^{1}}}$. Also, the $f_{2}$-critical sequence may
consists of consecutive $f_{2}$-critical edges or even all $f_{2}$-critical
edge, such as $e_{2}^{1},e_{2}^{2},\ldots,e_{2}^{k}$.

Suppose that $e_{2}$ is the first $f_{2}$-critical edge of the
$f_{2}$-critical sequence in $\overline{\gamma_{e^{1},v^{1}}}$, and $e_{2}$ is
not connected to $e_{1}$. The $f_{2}$-gradient flow then transitions from one
or two faces of $e_{2}$ to one or two branches of $\overline{\gamma_{v^{1}}}$,
respectively. This case is addressed by the branch case described above.

It is straightforward to check that for each case in the tree
$T^{f_{1}}_{e^{1},v^{1}}$, the variation in
$A_{0}^{f_{1},f_{2}}(G)-A_{1}^{f_{1},f_{2}}(G)$ equals the difference between
the number of $f_{2}$-critical vertices and the number of $f_{2}$-critical
edges. We can sum up the result by varying $e^{1}$ to obtain the result for
the rooted tree $T_{v_{1}}^{f_{1}}$. Since any two of such rooted trees are
disjoint, aggregating the individual results of each rooted tree leads to the
conclusion that

$A_{0}^{f_{1},f_{2}}(G)-A_{1}^{f_{1},f_{2}}(G)=\beta_{0}(G)-\beta_{1}(G)=\chi(G),$

the Euler characteristic of $G$. ∎

######  Example 4.11.

We present an example to elucidate Theorem 4.10. Consider another discrete
Morse function, denoted as $f_{2}$, applied to the graph $G$ shown in Figure
3. In this instance, there are four $f_{2}$-critical $0$-dimensional simplices
$v_{2}^{1},v_{2}^{2},v_{2}^{3},v_{2}^{4}$, and four $f_{2}$-critical
$1$-dimensional simplices $e_{2}^{1},e_{2}^{2},e_{2}^{3},e_{2}^{4}$ of
$f_{2}$.

Upon examination, one can identify the following strong connections:
$v_{1}^{1}\leftrightarrow v_{2}^{1}$, $v_{1}^{2}\leftrightarrow v_{2}^{2}$,
$v_{1}^{3}\leftrightarrow v_{2}^{4}$, $e_{1}^{1}\leftrightarrow e_{2}^{1}$,
$e_{1}^{3}\leftrightarrow e_{2}^{2}$, $e_{1}^{3}\leftrightarrow e_{2}^{4}$.
This example notably demonstrates a scenario where one critical simplex is
strongly connected to two distinct critical simplices. Therefore,
$A_{0}^{f_{1},f_{2}}(G)-A_{1}^{f_{1},f_{2}}(G)=3-3=\beta_{0}(G)-\beta_{1}(G)=1-1=0=\chi(G)$.

$e_{2}^{2}$$e_{2}^{3}$$e_{2}^{1}$$v_{1}^{2}$ Figure 2. The rooted tree
$T_{v_{1}^{2}}^{f_{1}}$.
$v_{2}^{2}$$e_{2}^{2}$$v_{2}^{1}$$e_{2}^{1}$$v_{2}^{3}$$e_{2}^{3}$$v_{2}^{4}$$e_{2}^{4}$
Figure 3.  Graph $G$ with discrete Morse function $f_{2}$.

######  Acknowledgements.

I express my gratitude to the editors and referees for their hard work and
insightful feedback, which are pivotal in enhancing the quality of the
manuscript. Special thanks are due to Prof. Toru Ohmoto (Waseda Univ.) and
Prof. Akira Koyama (Waseda Univ.) for their exceptional guidance and
invaluable support throughout this series of work.

## References

  * [1] R. Ayala, L.M. Fernández, D. Fernández-Ternero, J.A. Vilches, Discrete Morse theory on graphs. Topology and its Applications 156 (2009), 3091–3100.
  * [2] U. Bauer, Persistence in discrete Morse theory. Available at https://ediss.uni-goettingen.de›handle›bauer_u.
  * [3] M. K. Chari, M. Joswig, Complexes of discrete Morse functions, Discrete Mathematics 302 (2005) 39-51.
  * [4] D. Fernández-Ternero, E. Macías-Virgós, D. Mosquera-Lois, N. A. Scoville, J. A. Vilches Fundamental theorems of Morse theory on posets. AIMS Mathematics 2022, Volume 7, Issue 8.
  * [5] R. Forman: A User’s Guide to Discrete Morse Theory. Seminaire Lotharingien de Combinatoire 48 (2002), Article B48c.
  * [6] R. Forman, Morse Theory for Cell Complexes. Advances in Mathematics 134, (1998), 90-145.
  * [7] H. King, K. Knudson, N. M. Kostac, Birth and death in discrete Morse theory. Journal of Symbolic Computation 78 (2017), 41-60.
  * [8] D. N. Kozlov, Organized Collapse: An Introduction to Discrete Morse Theory, Graduate Studies in Mathematics, 207. American Mathematical Society, Providence, RI, 2020.
  * [9] K. Mischaikow, V. Nanda, Morse Theory for Filtrations and Efficient Computation of Persistent Homology. Discrete Comput Geom 50, 330-353 (2013).
  * [10] J. R. Munkres, Elements of Algebraic Topology, Addison-Wesley Publishing Company, California, 1984.
  * [11] N. A. Scoville, Discrete Morse Theory. Student Mathematical Library vol. 90, American Mathematical Society, Providence, RI, 2020.
  * [12] J. H. C, Whitehead Simple Homotopy Types. American Journal of Mathematics, vol. 72, no. 1, 1950, pp. 1-57.
  * [13] C. Zheng, Persistent pairs and strong connectedness in discrete Morse functions on simplicial complex ii@, in preparation.
  * [14] A. Zorn, Discrete Morse Theory on Simplicial Complexes, Available at http://www.math.uchicago.edu/~may/VIGRE/VIGRE2009/REUPapers/Zorn.pdf.