Open Access
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

© Wuhan University 2022

Licence Creative CommonsThis 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[3-9]. 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 n-path is a sequence of vertices in , . Let be the -module consisting of all the formal linear combinations of the n-paths on . The boundary map

is defined as

where is the i-th 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 n-path is an elementary n-path 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 n-paths on . Then is a submodule of . However, in general, is not a subchain complex of . Consider the sub--module

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[11-13]. From 2007 to 2009, Ayala et al[14-17] 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[18-20].

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 n-path 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 n-paths 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 zero-point. 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 n-path 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 zero-point 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

(1)

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 zero-point.

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 zero-point.

) Without loss of generality, is a positive function on and is nonnegative on . Let α be an arbitrary allowed elementary n-path 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 zero-point 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 n-path 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 zero-point 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 zero-point. 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 zero-point 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

(2)

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 1-Case 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 n-path on . Then there exist and such that , and .

For each , denote as the free -module consisting of all the formal linear combinations of critical n-paths 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 zero-point. Without loss of generality, is positive on and has at most one zero-point. 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 zero-point of . Obviously, and .

Case 2 There exists one zero-point 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

(3)

or

(4)

Hence, either

(5)

or

(6)

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 zero-point", we have that

(7)

where , and , (Particularly,,,; ,,). Therefore, if , then there must exist a unique zero-point 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 zero-point. Let . By Lemma 7, it is sufficient to prove that for each where , and , we have that . According to the number of zero-points 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,

(8)

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 n-paths 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 zero-point, it follows that any allowed elementary path on is not critical on . Hence, . Moreover, by Lemma 6, and . Then and .

Since

it follows that

(9)

By (8), since , it follows that

(10)

and

(11)

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

thumbnail 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

thumbnail 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

  1. Barcelo H, Capraro V , White J A. Discrete homology theory for metric spaces[J]. Bull London Math Soc, 2014, 46: 889-905. [CrossRef] [MathSciNet] [Google Scholar]
  2. Happel D. Hochschild cohomology of finite dimensional algebras[C]// Lecture Notes in Mathematics . Berlin: Springer-Verlag, 1989, 1404:108-126. [Google Scholar]
  3. Grigor'yan A, Lin Y, Muranov Y, et al. Homologies of path complexes and digraphs[EB/OL]. [2021-12-03].http://arxiv.org/abs/1207.2834v4. [Google Scholar]
  4. Grigor'yan A, Lin Y, Muranov Y , et al. Homotopy theory for digraphs[J]. Pure Applied Mathematics Quarterly, 2014, 10(4) : 619-674. [CrossRef] [MathSciNet] [Google Scholar]
  5. Grigor'yan A, Lin Y, Muranov Y , et al. Cohomology of digraphs and (undirected) graphs[J]. Asian J Math, 2015, 19 (5) : 887-932. [CrossRef] [MathSciNet] [Google Scholar]
  6. Grigor'yan A, Lin Y, Muranov Y, et al. Path complexes and their homologies[J]. Journal of Mathematical Science, 2020, 248(5): 564-599. [CrossRef] [Google Scholar]
  7. Grigor'yan A, Muranov Y, Yau S T. Homologies of digraphs and Künneth formulas[J]. Commun Anal Geom, 2017, 25 (5) : 969-1018. [CrossRef] [Google Scholar]
  8. Grigor'yan A, Muranov Y, Vershinin V, et al. Path homology theory of multi-graphs and quivers[J]. Forum Math, 2018, 30 (5) : 1319-1337. [CrossRef] [MathSciNet] [Google Scholar]
  9. Grigor'yan A, Jimenez R, Muranov Y, et al. Homology of path complexes and hypergraphs[J]. Topol Appl, 2019, 267:106877. [Google Scholar]
  10. Forman R. Morse theory for cell complexes[J]. Adv Math, 1998, 134 : 90-145. [CrossRef] [MathSciNet] [Google Scholar]
  11. Forman R. A user's guide to discrete Morse theory[J]. Sém Lothar Combin, 2002, 48: 1-35. [Google Scholar]
  12. Forman R. Discrete Morse theory and the cohomology ring[J]. Trans Amer Math Soc, 2002, 354 (12) : 5063-5085. [CrossRef] [MathSciNet] [Google Scholar]
  13. Forman R. Witten-Morse theory for cell complexes[J]. Topology, 1998, 37 (5): 945-979. [Google Scholar]
  14. 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]
  15. Ayala R, Fernández L M, Vilches J A. Morse inequalities on certain infinite 2- complexes[J]. Glasg Math J, 2007,49 (2) :155-165. [CrossRef] [MathSciNet] [Google Scholar]
  16. Ayala R, Fernández L M, Fernández-Ternero D, et al. Discrete Morse theory on graphs[J]. Topol Appl, 2009, 156: 3091-3100. [CrossRef] [Google Scholar]
  17. 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: 2084-2089. [CrossRef] [Google Scholar]
  18. Lin Y, Wang C, Yau S T. Discrete Morse theory on digraphs[J]. Pure and Applied Mathematics Quarterly, 2021,17(5): 1711-1737. [CrossRef] [MathSciNet] [Google Scholar]
  19. Lin Y, Wang C. Witten-Morse functions and Morse inequalities on digraphs[EB/OL]. [2021-12-05]. https://arxiv.org/abs/2108.08004. [Google Scholar]
  20. Wang C,Ren S. A discrete Morse Theory for digraph[EB/OL]. [2021-12-05]. https://arxiv.org/abs/2007.13425. [Google Scholar]

All Figures

thumbnail Fig.1 Example 1
In the text
thumbnail Fig. 2 Example 2
In the text

Current usage metrics show cumulative count of Article Views (full-text 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 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.