Discrete Morse inequalities on infinite graphs

Discrete Morse inequalities on infinite graphs Rafael Ayala, Luis M. Fern´andez and Jos´e A. Vilches ∗ Departamento de Geometr´ıa y Topolog´ıa Facultad de Matem´aticas, Universidad de Sevilla, Sevilla, SPAIN [email protected], [email protected], [email protected] Submitted: Jul 19, 2007; Accepted: Mar 9, 2009; Published: Mar 20, 2009 Mathematics Subject Classification: 05C10, 57M15 Abstract The goal of this paper is to extend to infinite graphs the known Morse inequalities for discrete Morse functions proved by R. Forman in the finite case. In order to get this result we shall use a special kind of infinite subgraphs on which a discrete Morse function is monotonous, namely, decreasing rays. In addition, we shall use this result to characterize infinite graphs by the number of critical elements of discrete Morse functions defined on them. Introduction. Under a classical point of view, Morse theory looks for links between global properties of a smooth manifold and critical points of a function defined on it (see [5]). For instance, the so-called Morse inequalities relate the Betti numbers of the manifold and the numbers of such critical points. R. Forman [1] introduced the notion of discrete Morse function defined on a finite cw-complex and, in this combinatorial context, he developed a discrete Morse theory as a tool for studying the homotopy type and homology groups of these complexes. He also proved the corresponding Morse inequalities, analogous to the classical ones obtained in the smooth case. This theory has shown to have many applications (for instance, see [2]). Following Forman’s suggestions stated in [1], we have begun the study of discrete Morse functions on infinite simplicial complexes by establishing the extension of Morse inequalities which allow us to understand the relationships between the topology of the complex, critical simplices of a discrete Morse function defined on it and the monotonous behaviour of this function at the ends of the complex. The authors made this work for ∗The authors are partially supported by Plan Nacional de Investigaci´on 2.007, Project MTM2007- 65726, SPAIN, 2007 and P.A.I. project 2008/FQM-189, SPAIN, 2008. the electronic journal of combinatorics 16 (2009), #R38 1 the special case of non-compact connected surfaces without boundary in [3]. In this paper, we deal with one-dimensional complexes in a more general way, by obtaining Morse inequalities for any kind of graph. Under this point of view, new situations arise, when finite Morse inequalities do not hold, which are fully understood by taking into account the criticality of the considered function at the infinite. In Section 1, we recall basic Forman’s definitions of discrete Morse function and critical simplex as well as his discrete Morse inequalities for the finite case. Besides, we state some general results concerning graphs which we shall use later. In Section 2, we study discrete Morse functions on infinite graphs. First, we give some examples which point out that new situations appear with respect to the finite case, specially discrete Morse functions without critical simplices and we prove that trees are the only infinite graphs in which it is possible to define such special discrete Morse functions. In order to investigate these new situations, we introduce the notion of weakly decreasing rays which becomes essential in the rest of the paper. Section 3 includes our main result: the discrete Morse inequalities which relate the topology of an infinite graph and the number of critical simplices of a discrete Morse function defined on it by using the number of weakly decreasing rays, generalizing Forman’s result for the finite case. Finally, in Section 4 we give an application of the discrete Morse inequalities which consists on characterizing infinite connected graphs which admit a discrete Morse function with a fixed number of critical elements (critical simplices and decreasing rays). 1 Preliminaries. Let Mbe a simplicial complex. A discrete Morse function defined on Mis a function f:M−→ Rsuch that, for any p-simplex σ∈M: (M1) At most one (p+ 1)-simplex τcontaining σverifies f(τ)≤f(σ). (M2) At most one (p−1)-simplex υcontained in σverifies f(υ)≥f(σ). Ap-simplex σ∈Mis said to be critical with respect to fif: (C1) There is not any (p+ 1)-simplex τcontaining σsatisfying f(τ)≤f(σ). (C2) There is not any (p−1)-simplex υcontained in σsatisfying f(υ)≥f(σ). The above notions were introduced by R. Forman in [1] for the finite case and we shall use them for the infinite case with no changes. Then, we have, by a direct computation, the following proposition which holds for both finite and infinite cases: Proposition 1.1. Let fbe a discrete Morse function defined on a simplicial complex M. Given a subcomplex N⊆M, the restriction of fto Nis a discrete Morse function too. Moreover, if σ∈Nis a critical p-simplex with respect to f, then σis also a critical p-simplex with respect to the restriction of fto N. the electronic journal of combinatorics 16 (2009), #R38 2 Let us remind the reader that given a cw-complex M, the p-th Betti number of M, denoted by bp(M), is the rank of the p-th homology group of M,Hp(M), with integer coefficients. In particular, b0(M) counts the number of connected components of M. In [1], Forman also established the discrete Morse inequalities for discrete Morse functions defined on a finite simplicial complex: Theorem 1.2. (Discrete Morse inequalities for finite complexes) Let fbe a discrete Morse function defined on a finite cw-complex M. Then: (I1) mp(f)−mp−1(f) + · · · ± m0(f)≥bp(M)−bp−1(M) + · · · ± b0(M); (I2) mp(f)≥bp(M); (I3) m0(f)−m1(f)+m2(f)−· · ·±mdim(M)(f) = b0(M)−b1(M)+b2−· · ·±bdim(M)(M), where mp(f)denotes the number of critical p-simplices with respect to f. Consequently, from (I2) we get that, for p= 0, any discrete Morse function on any finite simplicial complex always has critical 0-simplices. Now, we are going to state, for later use, some general results concerning discrete Morse functions on either finite or infinite graphs, whose proofs are obtained directly from the definitions. Moreover, from now on, we shall assume the classic terminology of Graph Theory, that is, we shall write vertex instead of 0-simplex and edge instead of 1-simplex. For more details and terminology concerning Graph Theory, see book of Diestel [4]. Proposition 1.3. Let Mbe a graph, N⊆Mbe a subgraph of Mand fbe a discrete Morse function defined on M. Then, any critical edge of fin Nis a critical edge of fin M. Notice that the above proposition does not establish anything about critical vertices. In fact, it is easy to show that the number of critical vertices with respect to the restriction is, in general, greater than the number of critical vertices on the whole graph. For instance, we have the following example: 1 20 3 4 5 6 7 8 9 the electronic journal of combinatorics 16 (2009), #R38 3 If we consider Nas the subgraph formed by the cycle, the vertex f−1(4) is a critical vertex of N, but it is not a critical vertex of M. Definition 1.4. Let Mbe a graph and fbe a discrete Morse function defined on M. Given a vertex v∈M, we say that f(v) is a local minimum (resp. maximum) of fin M if f(v) is less (resp. greater) than f(e) where eis any edge containing v. Similarly, given an edge e∈M, we say that f(e) is a local maximum of fin Mif (e) is greater than f(v) and f(w) where vand ware the two vertices contained in e. Notice that, by means of condition (M1), a vertex of degree at least 2 cannot be a local maximum. Moreover, condition (M2) implies that the value of fon any edge emust be greater than at least one of the values on its two vertices and thus f(e) cannot be a local minimum. In the next result the notion of critical simplex of a discrete Morse function on a graph is reformulated in terms of local extrema (maxima or minima) of the function. Proposition 1.5. Let Mbe a graph and fbe a discrete Morse function defined on M. Then, a vertex vof Mis critical with respect to fif and only if f(v)is a local minimum of fon M. Moreover, an edge eof Mis a critical edge with respect to fif and only if f(e)is a local maximum of fon M. 2 Discrete Morse functions on infinite graphs. First, we present some examples which show that discrete Morse inequalities for the finite case (Theorem 1.2) do not hold in this new context: Example 2.1.Non existence of critical simplices. Let Mbe the graph of the following figure in which it is defined a discrete Morse function as described: 2 2 1 1 0 0 -1 -1 -2 In this example, m0= 0, m1= 0, b0= 1 and b1= 0. Thus, (I2) and (I3) of Theorem 1.2 do not hold. Example 2.2.Infinite number of critical simplices. Let Mbe the graph of the following figure in which it is defined a discrete Morse function as described: 0 1 0 1 0 1 0 1 0 the electronic journal of combinatorics 16 (2009), #R38 4 In this example m0=∞,m1=∞,b0= 1 and b1= 0. So, (I1) with p= 1 and (I3) of Theorem 1.2 do not hold. Example 2.3.Finite number of critical points. Let Mbe the graph of the following figure in which it is defined a discrete Morse function as described: 13531 0 2 4420 Here, m0= 1, m1= 1, b0= 1 and b1= 0. So, (I3) of Theorem 1.2 does not hold. To study these new situations, a certain class of infinite subgraphs, the rays, will play an outstanding role. A ray of an infinite graph Mis an infinite connected subgraph R⊆Msuch that all of vertices of Rhave degree two but one v0which has degree one. Then, we say that Ris a ray starting at v0. Usually we shall denote a ray Rby listing its vertices and edges in an ordered way: R=v0, e0, v1, e1,... Given two rays in the same infinite graph, we say they are equivalent or cofinal if, from a common vertex, they coincide. We say that a discrete Morse function fis monotonous on a ray R=v0, e0, v1, e1,... if one of the following chain of inequalities it is verified: (1) f(v0)< f(e0)≤f(v1)< f(e1)≤f(v2)< f(e2)≤.... In this case we say that f is weakly increasing on R. (2) f(v0)≥f(e0)> f(v1)≥f(e1)> f(v2)≥f(e2)> . . . . In this case we say that f is weakly decreasing on R. If all inequalities in (1) or (2) are strict we say that fis either decreasing or increasing, respectively. As we shall see later, weakly decreasing rays will play a central role in the generalized discrete Morse inequalities. We characterize them in the following proposition: Proposition 2.4. Let Mbe an infinite graph and let fbe a discrete Morse function defined on M. Given a ray Rin M, the following conditions are equivalent: (i) fis weakly decreasing on R. (ii) There is not any critical simplex with respect to the restriction of fto R, denoted by f|R. (iii) There is not any local minimum or maximum of f|Rexcluding, possibly, the first vertex of R, which could be the unique local maximum of f|R. the electronic journal of combinatorics 16 (2009), #R38 5 Proof. Let Rbe the ray v0, e0, v1, e1,...,vn, en, vn+1, en+1,... (i)⇒(ii). Since fis weakly decreasing on R, then, for any vertex viof R, there exist a unique edge eiof Rincident on it such that f(vi)≥f(ei). So condition (C1) of the definition of critical simplices does not hold. Reasoning similarly we have that, for any edge ejof R, there is one of its two vertices, vj, such that f(ej)≤f(vj) and so, condition (C2) does not hold. (ii)⇒(iii). Let vbe a vertex of R. Since vis not a critical vertex with respect to f|R, by Proposition 1.5, f(v) can not be a local minimum of f|R. Moreover, by means of the comments before Proposition 1.5, if degree of vis at least 2 then f(v) can not be a local maximum of f|R. Thus, only the first vertex of R,v0, could be the unique local maximum of f|R(in the case f(v0)> f(e0)). Now let ebe an edge of R. This edge is not critical with respect to f|Rand hence, by Proposition 1.5, f(e) can not be a local maximum of f|R. Moreover, as we pointed out before Proposition 1.5, f(e) can not be a local minimum of f|R. (iii)⇒(i). By using (iii), we know that f(e0) is not a local maximum of f|Rthen it follows that either f(v1)≥f(e0) or f(v0)≥f(e0). If we assume that f(v1)≥f(e0), from (M2) we have f(v1)≥f(e0)> f(v0), hence f(v0) is a local minimum of f|Rbut it is impossible by hypothesis. Now, let us consider the second possibility, that is, f(v0)≥ f(e0). By means of (M2) we get f(v0)≥f(e0)> f(v1) and since there is not any local minimum of f|Rin Rthen f(v0)≥f(e0)> f(v1)≥f(e1). By repeating this procedure inductively we conclude that fis weakly decreasing on R. At this point, it is convenient to point out that b1(M), the first Betti number of a graph M, is the number of topologically independent cycles of Mor, equivalently, it is the number of chords (edges which are not in a given tree) with respect to a spanning tree. Motivated by Example 2.1, we are going to study how the non existence of critical simplices and the topology of the graph are linked. Theorem 2.5. Let Mbe a connected graph. Then, Madmits a discrete Morse function without critical simplices if and only if Mis an infinite tree. Proof. First, if there is a discrete Morse function defined on Mwithout critical simplices, it is clear that Mhas to be infinite. Now, if Mcontains at least one cycle, let Kbe a finite subgraph of Mwhich contains at least one cycle of M. Then b b1≥1, where b b1=dim(H1(K)). Using Theorem 1.2, we get bm1(f)≥ b b1≥1, where bm1(f) denotes the number of critical edges of the restriction of fto K. By Proposition 1.3, we have that m1(f)≥bm1(f)≥ b b1and this is a contradiction. Conversely, suppose that Mis an infinite tree and let v0be a vertex of M. Then, let R=v0, e0, v1, e1,... be a ray in Mstarting from v0. First, we define the desired function fin a weakly decreasing way on R, that is, such that: f(v0)≥f(e0)> f(v1)≥f(e1)> . . . the electronic journal of combinatorics 16 (2009), #R38 6 In the rest of Mwe define fweakly increasing when we are moving away from v0by paths (finite or not) different of ray R. To complete the definition on all M, we have to consider every path (finite or not again) starting from every vertex of Rwhich is not v0. In this case we can repeat the same construction, that is, we define fin a weakly increasing way when we are moving away from R. Now, it is necessary to check that fis a discrete Morse function with no critical simplices. Given a vertex vin the ray R, there is only one edge e(which is in R) incident with vsuch that f(v)≥f(e) and the other edges e′incident with vsatisffy f(e′)> f(v). If we consider now a vertex wwhich is not in R, there is a unique path in M−R connecting a vertex of Rand w. Then, by using the above construction, fhas to be weakly increasing on this path and so, there is an edge σincident with wsuch that f(σ)≤f(w). Notice that σis the only edge verifying this condition because fhas been defined in a weakly increasing way as we are moving away from R. Next, let ean edge in the ray R. Since fis weakly decreasing on R, its two vertices vand v′verify either f(v)≥f(σ)> f(v′) or f(v)< f(σ)≤f(v′). Finally, if eis an edge which is not in R, since fis weakly increasing as we are moving away from R, it holds either f(v)< f(e)≤f(v′) or f(v′)< f(e)≤f(v), where vand v′ denote the two vertices of e. Consequently, fis a discrete Morse function on Mwithout critical simplices. Observe that Theorem 2.5 gives a method to define discrete Morse functions on infinite trees without critical simplices. Moreover, the constructions of such functions show that they are determined once a ray Ris fixed on the tree M. The following results establish a link between the non-existence of critical simplices and the existence of weakly decreasing rays. Proposition 2.6. Let Mbe a graph and fbe a discrete Morse function defined on M with no critical vertices. Given a vertex vof M, there is a unique weakly decreasing ray starting at v. Proof. Since fdoes not have critical vertices on Mthen Mcan not be a finite graph. Otherwise, by Theorem 1.2 (I2), it follows m0(f)≥1. Let v0any vertex of Mwhich, obviously, is not a critical vertex. Then, there is a unique edge e0incident with v0such that f(v0)≥f(e0). Let v1the other vertex incident with e0. As fis a discrete Morse function, by (M2), f(e0)> f(v1). Again, since v1is not a critical vertex, there is a unique edge e16=e0such that f(v1)≥f(e1). Let v2be the other vertex of e1. It is possible to repeat the same argument for v2and continue with this process indefinitely, getting a ray R=v0, e0, v1, e1, v2, e2,... on which fis weakly decreasing. This construction does not stop after a finite number of steps. Otherwise, the last vertex vnverifies that there are not any edge esuch that f(vn)≥f(e). Then, freaches a minimum on vnand so, vnis a critical vertex, which is a contradiction. Notice that in the above process we never repeat a vertex since the values of fon the vertices of Rare strictly decreasing. Now, if we suppose that there are two non-cofinal weakly decreasing rays, Rand R′, starting at v0, then, there is a vertex vin both rays verifying that there is one edge ein the electronic journal of combinatorics 16 (2009), #R38 7 Rsuch that f(v)≥f(e) and there is one edge e′in R′such that f(v)≥f(e′). This is a contradiction with (M1) and so, the ray Ris unique. Corollary 2.7. Let Mbe a connected graph and fbe a discrete Morse function defined on Mwith no critical simplices. Then there is a unique (up to cofinality) decreasing ray in M. Proof. By Theorem 2.5 we get that Mis an infinite tree. By using the above proposition, we know that for every vertex v, there is a weakly decreasing ray Rvstarting at v. Now, given any vertex w6=v, let us see that Rvand Rware cofinal. It is obvious if w∈Rv. So, let us suppose that Rvand Rwstart at different vertices. Then we have two possibilities: either Rvand Rwhave a common vertex and hence by (M1) they coincide from it (therefore they are cofinal) or they are disjoint. In this case, since there are no critical edges, there is a unique vertex zjoined with vand wby finite decreasing paths starting at zand it is not possible by (M1). 3 Generalized discrete Morse inequalities. In this section, we relate the topology of M, the numbers of critical vertices, critical edges and non-cofinal weakly decreasing rays of a discrete Morse function defined on M. This result generalizes the Forman’s well known theorem for the finite case. It is interesting to point out that, despite the following result is restricted to discrete Morse functions with a finite number of critical simplices, this result holds for discrete Morse functions with an infinite number of critical simplices too. For this case, (i) holds trivially and (ii) is satisfied just by rewriting it as b0+m1(f) = d0+b1+m1(f). Theorem 3.1. Let Mbe an infinite graph and let fbe a discrete Morse function defined on Msuch that m0(f)and m1(f)are finite. Then: (i) m0(f) + d0≥b0and m1(f)≥b1, where d0is denoting the number of non-cofinal weakly decreasing rays on M. (ii) b0−b1=m0(f) + d0−m1(f). Proof. We observe that m1(f)<∞implies that Mcontains a finite number of cycles. Then, let Mbe a finite subgraph of Msuch that it contains every critical simplex of M and every cycle of M. Thus, b1=b1,m0(f)≥m0(f) and m1(f) = m1(f). When we restrict fto the finite subgraph M, we can apply the discrete Morse inequalities for the finite case (Theorem 1.2) and so, we get m1(f)≥b1. Now, if b0<+∞, it is possible to take Mhaving the same number of connected components as M. Moreover, we can get Msuch that each of its connected components intersects a unique connected component of M. In fact, for each connected component of Mwith critical simplices, it is enough to consider a connected and finite subgraph containing all critical simplices and all cycles which are included in the component. On the the electronic journal of combinatorics 16 (2009), #R38 8 other hand, for each connected component of Mwithout critical simplices, since it has to be an infinite tree due to Theorem 2.5, it is enough to consider a finite subtree. Therefore, we get b0=b0. Then, if m0(f) = m0(f), by using the discrete Morse inequalities for the finite case on M, we obtain: m0(f) + d0≥m0(f) = m0(f)≥b0=b0. Next, if m0(f)> m0(f), there exist critical vertices with respect to the restriction of fto Mwhich are not critical with respect to f. Then, every vertex of this kind is in a weakly decreasing ray in M. In fact, let v0be a critical vertex with respect to the restriction of fto Mwhich is not critical with respect to f. This implies that there exists a unique edge e0incident with v0and belonging to M−Msuch that f(v0)≥f(e0). Since e0does not belong to M, it can not be critical with respect to Mand thus, its other vertex v1satisfies f(v1)< f(e0). Moreover, v1is not in Mbecause, in other case, e0is in Mand it is impossible. So, v1is not a critical vertex with respect to fand, consequently, there is a unique edge e1in M−M(that is, not critical with respect to f) and incident with v1, such that f(e1)> f(v2), where v2is the other vertex of e1. If we suppose that v2is in M, then we find two different paths from v0to v2: one through M, since v0and v2are in the same connected component of Mand the other determined by our construction: v0, e0, v1, e1, v2, which is out of M. If we join both paths we get a cycle which is not in M and this is impossible. So, v2is in M−M. The path v0, e0, v1, e1, v2,... can be extended indefinitely, so it is a ray. Otherwise, its last vertex vnwould have to verify one of these two conditions: either vnis a critical vertex with respect to for vnis in M. The first option is impossible by definition of M and the second is impossible too, because reasoning in a similar way as before, it would imply that we could get a cycle which is not in M. At this point, we know that every critical vertex with respect to the restriction of f to Mwhich is not critical with respect to fis in a weakly decreasing ray. Conversely, given a weakly decreasing ray Rin M−Mthere is a unique vertex in Mjoined to Rby a finite decreasing path. This can proved as follows: since every connected component of Mintersects a unique component of Mand there are no critical edges with respect to fin M−M, then there is a finite decreasing path γvstarting from a vertex v∈M, which is critical with respect to the restriction of fto Mbut not with respect to f, and ending at a vertex of R. Notice that vis unique since otherwise there is a cycle in Mnot contained in M. We conclude by joining Rand γvto obtain a new weakly decreasing ray R′starting at a vertex in Mwhich is cofinal with R. Now, If we apply discrete Morse inequalities for the finite case on M, then we can replace every critical vertex with respect to the restriction of fto Mbut not with respect to fby its corresponding weakly decreasing ray. Thus, the total number of critical vertices with respect to the restriction of fto Mcan be expressed as the sum of the number of critical vertices with respect to fand the number of non-cofinal weakly decreasing rays on M. That is, m0(f) = m0(f) + d0and we get the desired equalities and inequalities. Finally, if b0= +∞, since Mis a finite subgraph of M, it only contains a finite number of components of Mand then, there is an infinite number of connected components of M the electronic journal of combinatorics 16 (2009), #R38 9