Combinatorial Differential Topology and Geometry

New Perspectives in Geometric Combinatorics MSRI Publications Volume 38, 1999 Combinatorial Di�erential Topology and Geometry ROBIN FORMAN Abstract. A variety of questions in combinatorics lead one to the task of analyzing the topology of a simplicial complex, or a more general cell complex. However, there are few general techniques to aid in this investiga- tion. On the other hand, the subjects of di�erential topology and geometry are devoted to precisely this sort of problem, except that the topological spaces in question are smooth manifolds. In this paper we show how two standard techniques from the study of smooth manifolds, Morse theory and Bochner’s method, can be adapted to aid in the investigation of combina- torial spaces. Introduction A variety of questions in combinatorics lead one to the task of analyzing a simplicial complex, or a more general cell complex. For example, a standard approach to investigating the structure of a partially ordered set is to instead study the topology of the associated order complex. However, there are few general techniques to aid in this investigation. On the other hand, the subjects of di�erential topology and di�erential geometry are devoted to precisely this sort of problem, except that the topological spaces in question are smooth manifolds, rather than combinatorial complexes. These are classical subjects, and numerous very general and powerful techniques have been developed and studied over the recent decades. A smooth manifold is, loosely speaking, a topological space on which one has a well-de�ned notion of a derivative. One can then use calculus to study the space. I have recently found ways of adapting some techniques from di�erential topology and di�erential geometry to the study of combinatorial spaces. Per- haps surprisingly, many of the standard ingredients of di�erential topology and di�erential geometry have combinatorial analogues. The combinatorial theories This work was partially supported by the National Science Foundation and the National Se- curity Agency. 177 178 ROBIN FORMAN are often simpler than the corresponding smooth theory, and in some cases imply the smooth theory. In this paper, I will discuss two new general tools to aid in the study of combinatorial spaces. One derived from Morse theory, a standard tool in di�erential topology, and the other derived from Bochner’s method, a standard tool in di�erential geometry and global analysis. Most of the results in this paper have appeared in [Forman 1998d; 1998a]. Of course, many others have had the idea of \borrowing" ideas from con- tinuous mathematics to study combinatorial objects. See for example [Bjo¨rner 1995] and the numerous references therein. As we go along, I will mention those references most closely related to our topic. 1. Morse Theory Since its introduction in [Morse 1925], Morse theory has become a funda- mental technique for investigating the topology of smooth manifolds. The basic principle is that the topology of a manifold is very closely related to the critical points of a smooth function on the manifold. The simplest example of this rela- tionship is the fact that if the manifold is compact, then any continuous function must have a maximum and a minimum. Morse theory provides a signi�cant re- �nement of this observation. See [Milnor 1962] for a beautiful exposition of this subject, and [Bott 1988] for a wonderful overview of Morse theory, including some recent developments. Many others have developed versions of Morse theory for simplicial complexes (see [Brehm and Ku¨hnel 1987; Ku¨hnel 1990], for example), and other types of nonsmooth topological spaces (for example, [Morse 1934; Eells and Kuiper 1962; Kuiper 1971; Goresky and MacPherson 1983; 1988]). When extending Morse theory to such spaces, one must decide what will replace smooth functions, the key ingredient in the classical theory. In the references cited, a number of choices have been made. Attention is focussed on piecewise linear functions [Brehm and Ku¨hnel 1987; Ku¨hnel 1990], continuous functions which behave like smooth functions near their critical points [Morse 1934; Eells and Kuiper 1962], and functions which can be extended to a larger domain to be smooth [Goresky and MacPherson 1983; 1988]). If one attempts to consider all continuous functions, one can still de�ne the notion of a critical point, but it seems to be impossible to control the topological contribution of each critical point [Kuiper 1971; Gromov 1981]. In this paper, we take a di�erent approach. We will present a very simple Morse theory for simplicial complexes which is entirely discrete. That is, there is no mention at all of continuous functions. Instead, our functions assign a single real number to each cell of the complex. Because we require so little structure from our functions, we need very little structure in our spaces, so the theory can be applied to very general cell complexes. After de�ning combinatorial Morse functions and critical points, we will show that the standard theorems of Morse COMBINATORIAL DIFFERENTIAL TOPOLOGY AND GEOMETRY 179 theory, relating the topology of the space to the critical points of the function, are true. We also present discrete analogues of such (seemingly) intrinsically smooth notions as the gradient vector �eld and the corresponding gradient flow associated to a Morse function. Using these, we de�ne a Morse complex, a di�erential complex built out of the critical points of our discrete Morse function, which has the same homology as the underlying space. In the smooth setting, the Morse complex has been subject to much recent study, and has played a crucial role in some recent applications (see [Klingenberg 1982; Floer 1988], for example). Most of this section will be an informal exposition of the contents of [Forman 1995; 1998d]. This combinatorial theory is not really a new theory, but rather an extraction of the combinatorial essence of the smooth theory. As evidence for this, we will indicate later that it is possible to deduce much of the smooth theory from this combinatorial theory, and, conversely, some of the results we present can be proved by \smoothing" the combinatorial Morse function and applying the corresponding smooth theory (although that is not the approach we will take in this paper). As we mentioned above, this discrete Morse theory can be de�ned for any CW complex, but to avoid very minor complications we will restrict attention, in this paper, to simplicial complexes. See [Forman 1998d] for a more general treatment. Let M be any �nite simplicial complex. We emphasize that M need not be a triangulated manifold, nor have any other special property. Denote by K the set of (nonempty) simplices of M , and Kp the simplices of dimension p. Write �(p) if � has dimension p, and � > � (or � < �) if � is a face of �. A discrete Morse function on M will actually be a function on K. That is, we assign a single real number to each simplex in M . Roughly speaking, a function f : K ! R is a Morse function if f usually assigns higher values to higher dimensional simplices, with at most one exception, locally, at each simplex. More precisely: Definition 1.1. A function f : K ! R is a discrete Morse function if, for every �(p) 2 K, (1) #f�(p+1) > � j f(�) � f(�)g � 1 and (2) #fγ(p−1) < � j f(γ) � f(�)g � 1. A simple example will serve to illustrate the de�nition. Consider the two com- plexes shown in Figure 1. Here we indicate functions by writing next to each cell the value of the function on that cell. The function on the left is not a discrete Morse function as the edge f−1(0) violates rule (2), since it has 2 lower- dimensional \neighbors" on which f takes on higher values, and the vertex f−1(3) 180 ROBIN FORMAN violates rule (1), since it has 2 higher dimensional \neighbors" on which f takes on lower values. The function on the right is a Morse function. 11 3 0 22 11 3 0 22 Figure 1. Left: not a discrete Morse function. Right: a discrete Morse function. The other main ingredient in Morse theory is the notion of a critical point. Definition 1.2. A simplex �(p) is critical (with index p) if (1) #f�(p+1) > � j f(�) � f(�)g = 0 and (2) #fγ(p−1) < � j f(γ) � f(�)g = 0. For example, in Figure 1, right, the vertex f−1(0) is critical of index 0, the edge f−1(3) is critical of index 1, and there are no other critical simplices. Note that if �(p) is critical, it is necessarily critical of index p. We will pause here to relate these de�nitions to the corresponding notions in the smooth category. To illustrate the main idea, we will consider a special case. Suppose x is a critical point of index 1 of a smooth Morse function F on a smooth manifold of dimension n. Then the Morse Lemma [Milnor 1962, Lemma 2.2] states that there are coordinates (t1; : : : ; tn), with x corresponding to (0; : : : ; 0), such that in these coordinates F (t1; : : : ; tn) = F (x)− t21 + nX i=2 t2i : That is, beginning at the point x, F decreases to both sides in the t1 direction, and increases in the other coordinate directions. Now suppose e is a critical 1-simplex of a discrete Morse function f . Then f(e) is greater than f at either boundary vertex, and less than f at any 2-simplex with e in its boundary (see, for example, Figure 2). We can see that this is, in fact, a combinatorial model of the smooth situation. Moreover we see that the critical edge e can be thought of as representing a critical point of index 1 in the smooth case together with a curve pointing in the directions in which the function is decreasing. In the general case, if �(p) is critical, � can be thought of as representing the p-dimensional \unstable" directions at a smooth critical point of index p. If our simplicial complex is a smooth triangulation of a smooth manifold, then one can make this discussion more precise. One can think of a discrete Morse function f as assigning a number COMBINATORIAL DIFFERENTIAL TOPOLOGY AND GEOMETRY 181 e 1 0 0 2 2 2 Figure 2. The function f decreases as one moves from the 1-simplex to either boundary component, and increases in each transverse direction. to the barycenter of each simplex. One can then smoothly interpolate between these values to de�ne a smooth function on all of M . If this is done carefully, \smoothing" a discrete Morse function f near a critical p-simplex results in a smooth Morse function F with a critical point of index p. Our next step is to show that the topology of a general simplicial complex M is intimately related to the critical points of a discrete Morse function on M . Before stating the main theorems, we need one more de�nition. Suppose f is a discrete Morse function on a simplicial complex M . For any c 2 R de�ne the level subcomplex M(c) by M(c) = [ f(�)�c [ ��� �: That is, M(c) is the subcomplex of M consisting of all simplices � with f(�) � c, as well as all of their faces. Theorem 1.3. Suppose the interval (a; b] contains no critical values of f . Then M(a) is a deformation retract of M(b). Moreover , M(b) simplicially collapses onto M(a). To de�ne simplicial collapse, suppose M is a simplicial complex, �(p) is a p- simplex of M that is not a face of any simplex, and γ(p−1) < � is a (p−1)-face γ � M Figure 3. Simplicial collapse of M onto M − (� [ γ). 182 ROBIN FORMAN of � that is not the face of any other simplex. Then we say that M simplicially collapses onto M − (� [ γ); see Figure 3. More generally, a simplicial collapse is any sequence of such operations. See Figure 4 for the simplicial collapse of a 2-simplex onto a vertex. Figure 4. Simplicial collapse of a 2-simplex onto a vertex. The equivalence relation generated by simplicial collapse is called simple- homotopy equivalence. This indicates that our Morse theory is particularly well suited to handling questions in this category. Theorem 1.4. Suppose �(p) is a critical simplex with f(�) 2 (a; b], and there are no other critical simplices with values in (a; b]. Then M(b) is (simple-)homotopy equivalent to M(a) [ _e(p) e(p) where e(p) is a p-cell , and it is glued to M(a) along its entire boundary _e(p). Before discussing the proofs of these theorems, we pause to consider some im- portant corollaries. Corollary 1.5. Suppose M is a simplicial complex with a discrete Morse function. Then M is (simple-)homotopy equivalent to a CW complex with exactly one cell of dimension p for each critical simplex of dimension p. This corollary is often most usefully applied via inequalities, known collectively as the Morse Inequalities, between numerical invariants. Let M be a simplicial complex with a discrete Morse function. Let mp denote the number of critical simplices of dimension p. Let F be any �eld, and bp = dimHp(M;F) the p-th Betti number with respect to F. Then we have the following inequalities. Corollary 1.6. I. (The Weak Morse Inequalities.) (i) For each p = 0; 1; 2; : : :; n, where n is the dimension of M , we have mp � bp: (ii) m0 −m1 +m2 − : : :+ (−1)nmn = �(M) def= b0 − b1 + b2 − : : :+ (−1)nbn. II. (The Strong Morse Inequalities.) For each p = 0; 1; 2; : : :; n; n+ 1, mp −mp−1 + : : :�m0 � bp − bp−1 + : : :� b0: This follows immediately from the previous corollary; see [Milnor 1962]. The Strong Morse Inequalities imply the Weak Morse Inequalities. COMBINATORIAL DIFFERENTIAL TOPOLOGY AND GEOMETRY 183 Every simplicial complex supports a discrete Morse function. Namely, for any complex M and any simplex � of M , set f(�) = dim(�). Then f is a discrete Morse function, and every simplex of M is critical for f . The results we have stated above apply to any simplicial complex. In the case that M is a combinatorial manifold [Glaser 1972, p. 19] one can often say more. For example, one can state a combinatorial analogue of the standard Sphere theorem of smooth Morse theory; see [Milnor 1962, Theorem 4.1]. Corollary 1.7. Suppose M is a combinatorial n-manifold without boundary with a Morse function with exactly two critical points. Then M is a combinatorial n-sphere. The proof of this corollary rests heavily on Whitehead’s wonderful theorem [1939] on the uniqueness of regular neighborhoods, which implies, as a special case, that a combinatorial n-manifold with boundary which simplicially collapses onto a vertex is a combinatorial n-ball. Suppose M is a combinatorial n-manifold with a discrete Morse function f with exactly two critical points. Then the maximum of f must occur at an n-simplex �(n) which is a critical simplex of index n. Thus, f restricts on M −� to a Morse function with exactly one critical simplex. The minimum of f must occur at a vertex which is a critical simplex of index 0, and this is the only critical simplex of f restricted to M−�. Theorem 1.3 implies that M −� simplicially collapses to that vertex. Now we apply Whitehead’s theorem to conclude that M−� is a combinatorial n-ball. It follows that M = (M−�)[� is a combinatorial n-sphere. Rather than prove the main theorems here, we will illustrate the main ideas with an example; see Figure 5. Rigorous proofs appear in [Forman 1998d]. 13 8 4 0 2112 9 3 57 10 11 6 Figure 5. Example of a Morse function. Here f−1(0) is a critical simplex of index 0, f−1(9) is a critical simplex of index 1, and there are no other critical simplices. Thus, it follows from the above corollary that M is homotopy equivalent to a CW complex built from a single 0-cell, and a single 1-cell. The only CW complex which can be built from two such cells is a circle. Therefore, we can conclude that M is homotopy equivalent to a circle, as is evident from the picture. Consider the sequence of level subcomplexes shown in Figure 6. We can see why the theorems are true. If � is not critical, then one of two cases must occur. 184 ROBIN FORMAN M(12) = M(13) = MM(10) = M(11) M(9)M(7) = M(8)M(5) = M(6) M(3) = M(4)M(1) = M(2)M(0) Figure 6. Level subcomplexes of the simplicial complex of Figure 5. The �rst possibility is that � has a codimension one face γ with f(γ) � f(�) (for example � = f−1(1), γ = f−1(2)). In this case, when � is added to M , γ is added at the same time. The new subcomplex collapses onto the previous complex by pushing in � along the free face γ. (There are a few things to check. For example, we must make sure that γ is, in fact, a free face of �. That is, we must check that γ is not a face of any other simplex � with f(�) � f(�), but this is true.) The other possibility is that there is a simplex � with � as a codimension-one face and with f(�) � f(�) (for example � = f−1(2); � = f−1(1)). In this case, � is added to M when � is added to M , and again the new complex collapses onto the previous complex by pushing in � along the free face �. If � is critical (for example f−1(9)), then for every simplex � with � > � we have f(�) > f(�) (this requires a bit of proof). Thus � appears �rst in M(f(�)). On the other hand, for every face γ of �, f(γ) < f(�), and is added earlier. Therefore, when � is added, it is simply glued to M(f(�) − ") along its boundary. This completes our \proof" of the main theorems. While the Morse inequalities are su�cient for many applications, it is some- times desirable to replace the Morse inequalities with equalities. That is, to understand the precise nature of any \extra" critical points which arise. This can be done, and requires the introduction of the gradient vector �eld. In fact, as we will see later, some of the results we have stated above are best understood in terms of the gradient vector �eld, rather than the original Morse function. Returning to the example in Figure 5, let us now indicate pictorially the sim- plicial collapse referred to in the theorem. Suppose �(p) is a noncritical simplex with �(p+1) > � satisfying f(�) � f(�). We then draw an arrow from � to �. The resulting diagram can be seen in Figure 7. A simplex is critical if and only if it is neither the tail nor the head of an arrow. These arrows can be viewed as the discrete analogue of the gradient vector �eld of the Morse function. (To COMBINATORIAL DIFFERENTIAL TOPOLOGY AND GEOMETRY 185 Figure 7. The gradient vector �eld of the Morse function. be precise, when we say \gradient vector �eld" we are really referring to the negative of the gradient vector �eld.) It is better to think of this gradient vector �eld, which we now call V , as a map of oriented simplices. That is, if v is a boundary vertex of an edge e with f(e) � f(v), we want to think of V (v) as a discrete tangent vector leaving v i.e., with e given the orientation indicated by the arrow in Figure 8. v e Figure 8. Edge orientation. More generally, if �(p+1) > �(p) are oriented simplices and satisfy f(�) � f(�) then we set V (�) = �� with the sign chosen so that h�; @V (�)i = −1 where h ; i is the canonical inner product on oriented chains with respect to which the simplices are orthonormal (in other words, h�; @V (�)i is the incidence number of � with respect to V (�)). De�ne V (�) to be 0 for all simplices � for which there is no such �. Now V can be extended linearly to a map V : Cp(M;Z)! Cp+1(M;Z); where, for each p, Cp(M;Z) is the space of integer p-chains on M . In the case of smooth manifolds, the gradient vector �eld de�nes a dynamical system, namely the flow along the vector �eld. Viewing the Morse function from the point of view of this dynamical system leads to important new insights [Smale 1961b]. To proceed further in our combinatorial setting, we now de�ne a (discrete-time) flow along the gradient vector �eld V . De�ne a map � : Cp(M;Z)! Cp(M;Z); the discrete-time flow, by � = 1 + @V + V @: We illustrate by an example. Consider the complex shown in Figure 9, with the indicated gradient vector �eld V . Let e be the top edge oriented from left 186 ROBIN FORMAN Figure 9. A 2-complex with its gradient vector �eld. to right. We calculate �(e) = e+ @V (e) + V @(e) in Figure 10. The map