Issue 
Wuhan Univ. J. Nat. Sci.
Volume 27, Number 4, August 2022



Page(s)  303  312  
DOI  https://doi.org/10.1051/wujns/2022274303  
Published online  26 September 2022 
Mathematics
CLC number: O 189.22
Discrete Morse Theory on Join of Digraphs
^{1}
Department of Mathematics and Statistics, Cangzhou Normal University, Cangzhou 061000, Hebei, China
^{2}
School of Sciences, Hebei University of Science and Technology, Shijiazhuang 050018, Hebei, China
^{3}
Department of Physics and Information Engineering, Cangzhou Normal University, Cangzhou 061000, Hebei, China
^{†} To whom correspondence should be addressed. Email: wangchong_618@163.com
Received:
25
March
2022
For given two digraphs, we can construct a larger digraph through join. The two digraphs that make up the join are called the factors of the join. In this paper, we give a necessary and sufficient condition that the function on the join determined by the discrete Morse functions on factors is a discrete Morse function. Moreover, we further prove the discrete Morse theory on join when the factors satisfy certain conditions.
Key words: path homology / transitive closure / digraph / join
Biography: WANG Chong, female, Associate professor, research direction: geometry and topology on graphs. Email: wangchong_618@163.com
Fundation item: Supported by the Science and Technology Project of Hebei Education Department (ZD2022168, ZD2020410), Project of Cangzhou Normal University (XNJJLYB2021006)
© Wuhan University 2022
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
0 Introduction
Digraphs are important topological models in complex networks and the homology groups of digraphs can reveal the topological and geometric characteristics of complex networks. Among many approaches for constructing (co) homology of digraphs^{[1, 2]}, a natural and important homology theory on digraphs is path homology introduced by Grigor'yan et al, which theory has been systematically developed with fruitful results^{[39]}. In this paper, we consider the discrete Morse theory based on the path homology of digraphs.
Let be a digraph where is the vertex set of and is the directed edge set of . For any directed edge , it can be denoted as . is called transitive, if and are two directed edges of G, then is a directed edge of . The smallest transitive digraph containing is called the transitive closure of , denoted as .
Let be a commutative ring with unit. An elementary npath is a sequence of vertices in , . Let be the module consisting of all the formal linear combinations of the npaths on . The boundary map
is defined as
where is the ith face map
such that
Here means omission of the vertex . Then for each . Hence, is a chain complex, simply denoted as if there is no ambiguity.
An allowed elementary npath is an elementary npath such that and is a directed edge of for each . Let be the free module consisting of all the formal linear combinations of allowed elementary npaths on . Then is a submodule of . However, in general, is not a subchain complex of . Consider the submodule
of . Then . The path homology groups of are defined as the homology groups of chain complex , denoted as .
In topological data analysis, we are concerned with the calculation and simplification of homology groups. Morse theory is just an important tool to simplify the calculation of homology groups. In 1998, Forman^{[10]} extended Morse theory on smooth manifolds to cell complexes and simplicial complexes. And based on this study, Forman studied discrete Morse theory, cohomology card product, Witten Morse theory and other related problems^{[1113]}. From 2007 to 2009, Ayala et al^{[1417]} studied the discrete Morse theory on graphs by using the discrete Morse theory of cell complexes and simplicial complexes given by Forman. Inspired by these, we studied the discrete Morse theory on digraphs^{[1820]}.
In this paper, we study the discrete Morse theory on join of digraphs, hoping to give the discrete Morse theory of join by requiring the two factors constituting the connection to meet certain conditions, rather than directly limiting the join.
Let and be two digraphs where and . Suppose and are disjoint. Then and are disjoint as well. The join of and is a digraph such that
the set of vertices of the digraph is ;
the set of directed edges of the digraph is .
The paper is organized as follows. In Section 1, we review the definition and some properties of discrete Morse functions on digraphs. In Section 2, we give some auxiliary results for main theorems in Lemma 5 and Lemma 8. Finally, in Section 3, we prove the main theorems of this paper.
Let be a digraph and a discrete Morse function on as defined in Definition 1. Define an linear map such that for any allowed elementary npath on ,
where and . Otherwise, ^{[10]}. We call the (algebraic) discrete gradient vector field of on , denoted as , abbreviated as . The discrete gradient flow is defined as
Here Id is the identity map from to .Correspondingly, the discrete Morse function, the (algebraic) discrete gradient vector field and the discrete gradient flow of a transitive digraph are denoted as , and , respectively.
The main theorems of this paper are as follows.
Theorem 1 Let and , discrete Morse functions on and , respectively. Let be the discrete Morse function on determined by and . Suppose is invariant, . Then
where is the subchain complex of consisting of all invariant chains.
Denote as the free module consisting of all the formal linear combinations of critical npaths on . We have that
Theorem 2 Let . Let be a function on such that for each vertex and a discrete Morse function on with a unique zeropoint. Let be the discrete Morse function on determined by and . Suppose is invariant, for any and , . Then
where and is stabilization map of .
1 Preliminaries
In this section, we mainly review the definition and properties of discrete Morse functions on digraphs.
For any allowed elementary paths and , if can be obtained from by removing some vertices, then we write or .
Definition 1^{[20]} A map is called a discrete Morse function on , if for any allowed elementary path on , both of the followings hold:
(i) ;
(ii)
where
For an allowed elementary path , if in both (i) and (ii), the inequalities hold strictly, then is called critical. Precisely,
Definition 2 An allowed elementary npath is called critical, if both of the followings hold:
(i);
(ii)
It follows from Definition 2 that an allowed elementary path is not critical if and only if either of the following conditions holds
(i) there exists such that ;
(ii) there exists such that .
A directed loop on is an allowed elementary path , .
Lemma 1^{[18} ^{, Lemma 2.4] }Let be a digraph and a discrete Morse function on . Let be a directed loop. Then for each , .
Lemma 2^{[18} ^{, Lemma 2.5]} Let be a digraph and a discrete Morse function on as defined in Definition 1. Then for any allowed elementary path on , there exists at most one index such that the value of the corresponding vertex is zero.
Lemma 3^{[19} ^{, Lemma 2.5] }Let be a discrete Morse function on digraph . Then for any allowed elementary path in , (i) and (ii) can not both be true.
2 Auxiliary Results for Main Theorems
Let and be two digraphs. Suppose and are disjoint. Then and are disjoint as well. The join of and is a digraph such that
the set of vertices of the digraph is ;
the set of directed edges of the digraph is
2.1 Discrete Morse Functions on the Join of Digraphs
In this subsection, we will give a necessary and sufficient condition that the function on the join determined by the discrete Morse functions on factors is a discrete Morse function.
Firstly, we prove that discrete Morse functions on the join of digraphs have the following important property.
Lemma 4 Let be a discrete Morse function on . Then there exists at most one zeropoint of on .
Proof Suppose to the contrary, there are two distinct vertices such that . Then by the definition of join of digraphs, there are three cases to be considered.
Case 1 Both of are in . Then for any allowed elementary path on , we have that
and
are two distinct allowed elementary paths on such that . This contradicts that is a discrete Morse function on .
Case 2 Both of are in . Similar to Case 1, for any allowed elementary path on
and
are two distinct allowed elementary paths on such that which contradicts that is a discrete Morse function on .
Case 3 and . Then . This also contradicts that is a discrete Morse function on .
Combining Case 1, Case 2 and Case 3, the lemma is proved.
Secondly, define a function
on , where and are functions on and , respectively. Then by Lemma 4 and (1), we have that
Lemma 5 is a discrete Morse function on if and only if there exist discrete Morse functions on and on respectively such that and one of and is positive while the other one has at most one zeropoint.
Proof ( Let and . Then by (1), and by Definition 1, , are discrete Morse functions on and , respectively. Moreover, by Lemma 4, one of and is positive and the other one has at most one zeropoint.
) Without loss of generality, is a positive function on and is nonnegative on . Let α be an arbitrary allowed elementary npath on . Then by Ref.[3, Proposition 6.4],
where , , . Consider the following cases:
Case 1 . Suppose and are two allowed elementary paths on such that , and . Since for each , it follows that for .Then there are two indices such that . This contradicts Lemma 2. Therefore,
Suppose and are two allowed elementary paths on such that , and . Since for each , it follows that
and
where , and . Since there exists at most one zeropoint of , it follows that and . Without loss of generality, . Thus, there exists a directed loop
on with . This contradicts Lemma 1. Therefore,
Case 2 . Then for any allowed elementary npath on ,
where . Obviously, since for all vertices , it follows that for any allowed elementary path . Hence,
Moreover, since there exists at most one vertex such that , it follows that there exists at most one allowed elementary path
such that and . Hence,
Summarizing Case 1 and Case 2, due to the arbitrariness of , is a discrete Morse function on .
Therefore, the lemma is proved.
Moreover, we have
Theorem 3^{[18} ^{, Theorem 2.12]} Let be a digraph and be a discrete Morse function on . Then can be extended to be a Morse function on such that for each vertex if and only if the following condition (*) is satisfied.
(*) for each vertex , there exists at most one zeropoint of in all allowed elementary paths starting or ending at .
Therefore, by Lemma 5 and Theorem 3, we have that
Corollary 1 Let be a function on and be a discrete Morse function on with at most one zeropoint. Then the function defined in (1) is extendable.
Proof By Theorem 3, can be extended to be a discrete Morse function on such that for , and can be extended to be a discrete Morse function on such that for .
By Lemma 5, is a discrete Morse function on and is extendable.
Define a function such that
Then is the extension of on such that for .
Remark 1 Let be discrete Morse functions on digraphs and , respectively. By Lemma 5 and Corollary 1, unless otherwise specified, we always assume that is positive and has at most a unique zeropoint in this paper. Denote the extended discrete Morse function of on as .
2.2 Transitive Closure of Join of Digraphs, Discrete Gradient Vector Field on the Transitive Closure
Firstly, it is easy to prove that the transitive closure of join of two digraphs are the same as the join of their transitive closures. That is,
Proposition 1 Let and be two digraphs. Then
Proof Firstly,
Secondly, we will prove
and divide the proof into the following two steps.
Step 1 Since , it is sufficient to prove that for each directed edge ,. Since for any , there exist a sequence of directed edges such that with and . Since , there are three cases to be considered.
Case 1 Each , . Then .
Case 2 Each ,. Then .
Case 3 There exists a directed edge . Then by the definition of join of digraphs, vertices are all in and are all in . Thus,
Combing Case 1Case 3, . Hence, .
Step 2 By the definition of join of digraphs, we have that
Moreover,
for each such that and ,
Hence, .
Therefore, (2) is proved and the proposition holds.
By Proposition 1 and Ref.[3, Proposition 6.4], we have
Corollary 2 Suppose is an arbitrary allowed elementary npath on . Then there exist and such that , and .
For each , denote as the free module consisting of all the formal linear combinations of critical npaths on digraph .
Lemma 6 Suppose. Then there exist and such that .
Proof By Corollary 2, where and . By Lemma 5, since is the discrete Morse function on decided by and , it follows that one of and is positive and the other one has at most one zeropoint. Without loss of generality, is positive on and has at most one zeropoint. Then the extension of is positive on and each allowed elementary path on is critical on . Hence, is a critical path on and the crucial part of the proof is to verify that is a critical path on . Consider the following two cases.
Case 1 There exists no zeropoint of . Obviously, and .
Case 2 There exists one zeropoint of . Then each allowed elementary path on is not critical on . Since is critical on , it follows that . We assert that . Suppose to the contrary, is not critical on . By Lemma 3, there are two cases to be considered.
Subcase 2.1 There exists an allowed elementary path on such that and . Let . Then is an allowed elementary path on such that and which contradicts is critical on .
Subcase 2.2 There exists an allowed elementary path on such that and . Let . Then is an allowed elementary path on such that and which contradicts is critical on .
Combining Case 2.1 and Case 2.2, the assertion holds.
Summarizing Case 1 and Case 2, the lemma is proved.
Remark 2 The inverse of Lemma 6 may not hold. For example, suppose is a function on and is a discrete Morse function on with . Let where is an arbitrary vertex of and . Then and are critical paths on and , respectively. Let . Then since , it follows that is not critical on .
Secondly, denote the discrete gradient vector field on and the discrete gradient flow of as and respectively, . Then we have that
Proposition 2 Let be the discrete gradient vector filed on and be an allowed elementary path on where . Then if and only if one of and holds.
Proof ( Suppose . Then there exists a unique allowed elementary path such that and . By Corollary 2, where , and . Since , it follows that . Thus, either
or
Hence, either
or
We assert that only one of (3) and (4) holds. Otherwise, can be written as either or . This contradicts the uniqueness of . Therefore, only one of (5) and (6) holds.
() Without loss of generality, and . Then there exists a unique allowed elementary path on such that and. Let . Then is an allowed elementary path on such that and . Hence, .
The lemma is proved.
Remark 3 The condition "" in Proposition 2 can not be omitted. Consider the example in Remark 2. Let . Then , and . However, since , it follows that .
Remark 4 Let be an allowed elementary path on where and . Then under the assumption that " is positive and has at most a unique zeropoint", we have that
where , and , (Particularly,,,; ,,). Therefore, if , then there must exist a unique zeropoint of on and for any allowed elementary path , and .
Thirdly, consider a structural feature of elements in Ω_{∗}(G).
Lemma 7 Let . Suppose ,where , , and . Then can be written as a finite sum of ,where and .
Proof For each ,
Thus
and
where .
Since , it follows that . Hence, the coefficient for each fixed , must sum up to zero in . Specifically, there are two cases.
Case 1 There exists a certain index such that . Then the coefficient of in is
where , and . Hence, by finite steps, we can obtain a formal linear combination of allowed elementary paths on containing such that
Case 2 There exists a certain index such that . Then
Similar to Case 1 above, we can obtain a formal linear combination of allowed elementary paths on which containing such that.
Therefore, the lemma is proved.
Finally, by Lemma 7, we have that
Lemma 8 Let and be discrete Morse functions on and , respectively. Let be the discrete Morse function on decided by and . Suppose is invariant. Then is invariant.
Proof By Lemma 5 and Corollary 1, is extendable. Without loss of generality, is positive and has at most one zeropoint. Let . By Lemma 7, it is sufficient to prove that for each where , and , we have that . According to the number of zeropoints of , there are two cases.
Case 1 is positive on . Then by Theorem 3, are both extendable and for any allowed elementary path on . Hence, .
Case 2 There exists one vertex such that . Since for any vertex , it follows that is extendable by Theorem 3. Moreover,
for any allowed elementary path . Consider the following two subcases.
Subcase 2.1 . Let and where and. Then by (7) and (8),
Since is invariant, . Hence, by Ref.[3, Proposition 6.4], .That is, is invariant.
Subcase 2.2 . Then , where , are allowed elementary npaths on .
Hence,
where and . Therefore,
By Ref.[3, Proposition 6.4], . Thus, which implies that . That is, is invariant.
Summarizing Case 1 and Case 2, the lemma is proved.
3 Proof of Main Theorems
In this section, we will give the proof of Theorem 1 and the proof of Theorem 2.
Let be the subchain complex of consisting of all invariant chains. By Ref.[18], we have the following theorem.
Theorem 4^{[18} ^{, Corollary 2.16]} Let be a digraph and be a discrete Morse function on satisfying condition (*). Let be the extension of on and be the discrete gradient vector field on . Suppose is invariant. Then
Then we can give the proof of Theorem 1.
Proof of Theorem 1 By Lemma 5 and Corollary 1, is extendable. By Lemma 8, is invariant. By Theorem 4, Theorem 1 is proved.
Furthermore, by Ref. [19], we have that
Theorem 5^{[19} ^{, Corollary 4.11]} Let be a digraph and be the transitive closure of . Suppose is invariant and for any where is the discrete gradient vector field on and is the discrete gradient flow of , respectively. Then
where and is the stabilization map of .
Then we can give the proof of Theorem 2.
Proof of Theorem 2 By Lemma 5, is a discrete Morse function on . By Corollary 1, is extendable. Let ,where , , and . Since for and has a unique zeropoint, it follows that any allowed elementary path on is not critical on . Hence, . Moreover, by Lemma 6, and . Then and .
Since
it follows that
By (8), since , it follows that
and
Hence, by (8), (9), (10) and (11),
Since is invariant, by Lemma 8, it follows that is invariant. Therefore, by Theorem 5, the theorem is proved.
Next, let , be transitive digraphs. Then by Proposition 1, we have that
Thus, is transitive. Therefore, by Lemma 5 and Corollary 1, Theorem 5 can be restated as follows.
Corollary 3 Let where and are transitive digraphs. Let , be discrete Morse functions on and respectively and the discrete Morse function on decided by and . Then
Finally, we give some examples. The following example illustrates Theorem 1 and Theorem 2.
Example 1 Let be a digraph where and . Let be a function on such that , and .
Let be a digraph where and . Let be a function on such that and . Then and are discrete Morse functions on and respectively and both and are extendable.
Let . In fact, is a suspension on (Ref.[3, Definition 6.13]). By Corollary 1, and can define a discrete Morse function as in (1) which is extendable(see Fig.1). Let be the extension of on . Then
Fig.1 Example 1 
and
for any other allowed elementary path on ,
for any allowed elementary path on .
Hence, is invariant. Moreover,
and
Hence for any
On the other hand,
and
for any other allowed elementary path on .
for any other allowed elementary path on .
By Theorem 1, since
it follows that
which is consistent with Ref.[3, Proposition 6.14].
By Theorem 2, since
it follows that
which is consistent with Ref.[3, Proposition 6.14].
And the next is an example illustrating Corollary 3.
Example 2 Let be a digraph with vertex set and directed edge set . Let be a function on such that
Let be a digraph where and . Let be a function on such that and . Then and are discrete Morse functions on and respectively and both and are extendable.
Let . By Corollary 1, and can define a discrete Morse function as (1) which is extendable(see Fig.2). Let be the extension of on . Then
Fig. 2 Example 2 
Hence
for any other allowed elementary path on
and
Therefore,
By Corollary 3,
which is consistent with Ref.[3, Example 6.17].
References
 Barcelo H, Capraro V , White J A. Discrete homology theory for metric spaces[J]. Bull London Math Soc, 2014, 46: 889905. [CrossRef] [MathSciNet] [Google Scholar]
 Happel D. Hochschild cohomology of finite dimensional algebras[C]// Lecture Notes in Mathematics . Berlin: SpringerVerlag, 1989, 1404:108126. [Google Scholar]
 Grigor'yan A, Lin Y, Muranov Y, et al. Homologies of path complexes and digraphs[EB/OL]. [20211203].http://arxiv.org/abs/1207.2834v4. [Google Scholar]
 Grigor'yan A, Lin Y, Muranov Y , et al. Homotopy theory for digraphs[J]. Pure Applied Mathematics Quarterly, 2014, 10(4) : 619674. [CrossRef] [MathSciNet] [Google Scholar]
 Grigor'yan A, Lin Y, Muranov Y , et al. Cohomology of digraphs and (undirected) graphs[J]. Asian J Math, 2015, 19 (5) : 887932. [CrossRef] [MathSciNet] [Google Scholar]
 Grigor'yan A, Lin Y, Muranov Y, et al. Path complexes and their homologies[J]. Journal of Mathematical Science, 2020, 248(5): 564599. [CrossRef] [Google Scholar]
 Grigor'yan A, Muranov Y, Yau S T. Homologies of digraphs and Künneth formulas[J]. Commun Anal Geom, 2017, 25 (5) : 9691018. [CrossRef] [Google Scholar]
 Grigor'yan A, Muranov Y, Vershinin V, et al. Path homology theory of multigraphs and quivers[J]. Forum Math, 2018, 30 (5) : 13191337. [CrossRef] [MathSciNet] [Google Scholar]
 Grigor'yan A, Jimenez R, Muranov Y, et al. Homology of path complexes and hypergraphs[J]. Topol Appl, 2019, 267:106877. [Google Scholar]
 Forman R. Morse theory for cell complexes[J]. Adv Math, 1998, 134 : 90145. [CrossRef] [MathSciNet] [Google Scholar]
 Forman R. A user's guide to discrete Morse theory[J]. Sém Lothar Combin, 2002, 48: 135. [Google Scholar]
 Forman R. Discrete Morse theory and the cohomology ring[J]. Trans Amer Math Soc, 2002, 354 (12) : 50635085. [CrossRef] [MathSciNet] [Google Scholar]
 Forman R. WittenMorse theory for cell complexes[J]. Topology, 1998, 37 (5): 945979. [Google Scholar]
 Ayala R, Fernández L M, Vilches J A. Discrete Morse inequalities on infinite graphs[J]. Electron J Combin, 2009,16 (1): R38. [CrossRef] [Google Scholar]
 Ayala R, Fernández L M, Vilches J A. Morse inequalities on certain infinite 2 complexes[J]. Glasg Math J, 2007,49 (2) :155165. [CrossRef] [MathSciNet] [Google Scholar]
 Ayala R, Fernández L M, FernándezTernero D, et al. Discrete Morse theory on graphs[J]. Topol Appl, 2009, 156: 30913100. [CrossRef] [Google Scholar]
 Ayala R, Fernández L M, Quintero A , et al. A note on the pure Morse complex of a graph[J]. Topol Appl, 2008,155: 20842089. [CrossRef] [Google Scholar]
 Lin Y, Wang C, Yau S T. Discrete Morse theory on digraphs[J]. Pure and Applied Mathematics Quarterly, 2021,17(5): 17111737. [CrossRef] [MathSciNet] [Google Scholar]
 Lin Y, Wang C. WittenMorse functions and Morse inequalities on digraphs[EB/OL]. [20211205]. https://arxiv.org/abs/2108.08004. [Google Scholar]
 Wang C,Ren S. A discrete Morse Theory for digraph[EB/OL]. [20211205]. https://arxiv.org/abs/2007.13425. [Google Scholar]
All Figures
Fig.1 Example 1  
In the text 
Fig. 2 Example 2  
In the text 
Current usage metrics show cumulative count of Article Views (fulltext article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 4896 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.