A USER'S GUIDE TO DISCRETE MORSE THEORY 0. IntRoDuction
Contents
1. ness of K and its algebraic topology Theorem 10 1 If H K 0 where H K denotes the reduced homology of K then K is evasive In fact they proved something stronger and we will come back to this point later We illustrate the previous theorem with a simple example Let S be the 2 simplex shown in Figure 10 2 spanned by the vertices vo v and v2 with K the subcomplex consisting of the edge vo v1 together with the vertex v2 V v v An example of an evasive subcomplex of the 2 dimensional simplex Figure 10 2 A possible guessing algorithm is shown in Figure 10 3 Define an evader of a guessing algorithm to be a face o of S with the property that when questions are asked in the order determined by the algorithm one must ask all three questions before it is known whether or not is in K In particular the evaders of the illustrated guessing algorithm are o v vo v2 A USER S GUIDE TO DISCRETE MORSE THEORY 37 Note that the subcomplex K has nonzero reduced homology so the theorem of Kahn Saks and Sturtevant guarantees that every guessing algorithm has some evaders a ve Is yk ISIS o ollu umli Iu v w uwv A guessing algorithm Figure 10 3 Morse Theory comes to the fore when one observes that a guessing algorithm induces a discrete vector field on S For example the guessing algorithm shown in Figure 10 3 induces the vector field V 0 lt v1 vo lt vo vi v22. Babson A Bj rner S Linussion J Shareshian and V Welker Complexes of not i Connected Graphs Topology 38 1999 pp 271 299 E Babson P Hersh Discrete Morse functions from lexicographic orders preprint E Batzies and V Welker Discrete Morse Theory for Cellular Resolutions to appear in J Reine Angw Math M Betz and R Cohen Graph moduli space and cohomology operations Turk J of Math 18 1994 pp 23 41 R Bott Stable homotopy of the classical groups Ann of Math 70 1959 pp 313 337 M Chari On Discrete Morse Functions and Combinatorial Decompositions Discrete Math 217 2000 pp 101 113 X Dong The Topology of Bounded Degree Graph Complexes and Finite Free Resolutions thesis Univ of Minn 2001 A Duval A Combinatorial Decomposition of Simplicial Complezes Israel J of Math 87 1994 pp 77 87 R Forman A Discrete Morse Theory for Cell Complexes in Geometry Topology amp Physics for Raoul Bott S T Yau ed International Press 1995 Morse Theory for Cell Complexes Adv in Math 134 1998 pp 90 145 Witten Morse Theory for Cell Complexes Topology 37 1998 pp 945 979 Combinatorial Vector Fields and Dynamical Systems Math Zeit 228 1998 pp 629 681 Combinatorial differential topology and geometry in New Perspectives in alge braic Combinatorics Berkeley CA 1996 97 Math Sci Res Inst Publ 38 Cambridge Univ Press
3. In 16 we show how one can recover the ring structure of the cohomology of a simplicial complex from the point of view of discrete Morse Theory this follows work of Betz and Cohen 4 and Fukaya 17 18 in the smooth setting In 34 Novikov presents a generalization of standard smooth Morse Theory in which the role of the Morse function is now played by a closed 1 form the classical case arises when the closed 1 form is exact In 15 we present the analogous generalization for discrete Morse Theory In 45 Witten shows how smooth Morse Theory can be seen as arising from considerations of supersymmetry in quantum physics In 11 we present a combinatorial version of Witten s derivation We believe that this latter work may have greater significance At crucial points in 45 Witten appeals to path integral arguments which are rather standard in quantum physics but are ill defined mathematically In the corresponding moments in 11 what arises is a well defined discrete sum Perhaps the approach in 11 can find uses in the analysis of other quantum field theories One topic which we have only touched upon is the study of the dynamics associated to flowing along the gradient vector field associated to a discrete Morse function In fact an understanding of the dynamics is crucial to the proof of theorem 7 3 for A USER S GUIDE TO DISCRETE MORSE THEORY Al example The relevant study takes place in section 6 of 10 In 12 we study
4. In particular Morse s first great triumph with Morse Theory was his investigation of the set of geodesics between two points in a Riemannian manifold 32 see also Part HI pf 30 The geodesics are precisely the critical points of the natural Morse function on the path space and Morse used the Morse inequalities along with a knowledge of the topology of the path space to deduce the existence of many critical points It is intriguing to this author that there are as yet no corresponding examples in the combinatorial setting I know of no examples in which a collection of classically studied objects in combinatorics can be naturally identified with the critical simplices of a Morse function on some larger complex Indeed I believe that soon combinatorial examples of interest will be found that fit into this third category I wonder if applications of discrete Morse theory will be found that approach the beauty depth and fundamental significance of the applications of smooth Morse Theory mentioned in this paragraph On a broader note I believe that discrete Morse Theory is only a small part of what someday will be a more complete theory of combinatorial differential topology although I hesitate to predict at least in print what form such a theory will take 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 A USER S GUIDE TO DISCRETE MORSE THEORY 43 REFERENCES E
5. gt X two continuous maps If f and fa are homotopic then X Us o and X Up a are homotopy equivalent See Theorem 2 3 on page 120 of 28 Therefore the homotopy type of a CW complex is determined by the homotopy class of the attaching maps Since homotopy clases are discrete objects we have now recaptured a bit of the combinatorial atmosphere that we seemingly lost when generalizing from simplicial complexes to CW complexes Let us now present some examples 1 Suppose X is a topological space which has a CW decomposition consisting of exactly one 0 cell and one d cell Then X has a CW decomposition C Xo C X4 X The space Xo must be the O cell and X X is the result of attaching the d cell to Xo Since Xo consists of a single point the only possible attaching map is the constant map Thus X is constructed from taking a closed d ball and identifying all of the points on its boundary One can easily see that this implies that the resulting space is a d sphere 2 Suppose X is a topological space which has a CW decomposition consisting of exactly one 0 cell and n d cells Then X has a CW decomposition as in 1 1 such that Xo is the 0 cell and for each i 1 2 n X is the result of attaching a d cell to Xq_1 From the previous example we know that X is a d sphere The space X is constructed by attaching a d cell to X The attaching map is a continuous map from a d 1 sphere to X Every map of the d 1 sphere into
6. 10 MORSE THEORY AND EVASIVENESS So far we have indicated some applications of discrete Morse Theory to combina torics and topology We now present an application to computer science The reader should see the reference 14 for a more complete treatement of the content of this section The problem we study is a topological version of a standard type of search prob lem The generalized version that we will present first appeared in 35 Let S be an n dimensional simplex with vertices vo v1 Un and K a subcomplex of S which is known to you Let be a face of S which is not known to you Your goal is to determine if is in K In particular you need not determine the face just whether or not it is in K You are permitted to ask questions of the form Is v in a You may use the answers to the questions you have already asked in determining which vertex to ask about next Of course you can determine if o is in K by asking n 1 questions since by asking about all n 1 vertices you can completely determine You win this game if you answer the given question after asking fewer that n 1 questions 36 ROBIN FORMAN Say that K is nonevasive if there is a winning strategy for this game i e there is a question algorithm that determines whether or not o K in fewer than n 1 questions no matter what o is Say K is evasive otherwise Kahn Saks and Sturtevant proved the following relationship between the evasive
7. Morse function with exactly two critical points which implies that M is a topological sphere A key step in this proof is the cancellation theorem which provides a sufficient condition for two critical points to be cancelled see Theorem 5 4 in 31 which Milnor calls The First Cancellation Theorem or the original proof in 33 In this section we will see that the analogous theorem holds for discrete Morse functions Moreover in the combinatorial setting the proof is much simpler The main result is that if a and B are 2 critical simplices and if there is exactly 1 gradient path from the boundary of 6 to a then a and can be cancelled More precisely Theorem 9 1 Suppose f is a discrete Morse function on M such that B and a are critical and there is exactly one gradient path from the boundary B to a Then there is another Morse function g on M with the same critical simplices except 34 ROBIN FORMAN that a and 6 are no longer critical Moreover the gradient vector field associated to g is equal to the gradient vector field associated to f except along the unique gradient path from the boundary B to a In the smooth case the proof either as presented originally by Morse in 33 or as presented in 31 is rather technical In our discrete case the proof is simple If in the top drawing in Figure 9 2 the indicated gradient path is the only gradient path from the boundary of 8 to a then we can reverse
8. The actual definition of the boundary map is slightly nontrivial and we will not go into it here see Ch V sec 2 of 28 for the details At first it may seem that without knowing this boundary map there is little to be gained from Theorem 1 6 In fact much can be learned from just knowing of the existence of such a boundary A USER S GUIDE TO DISCRETE MORSE THEORY 9 map For example let us choose a coefficient field F and tensor everything with F to get a differential complex Ce Ty OOO Se Oe 0 which calculates H X F where now C X F F From basic linear algebra we can deduce the following inequalities Theorem 1 7 Let X be a CW complex with a fixed CW decomposition with cp cells of dimension d for each d Fix a coefficient field F and let b denote the Betti numbers of X with respect to F i e bq dim H X F i The Weak Morse Inequalities For each d Cd gt ba ii Let x X denote the Euler characteristic of X i e x X ba b bo then we also have K X 60 a e As the name Weak Morse Inequalities implies this theorem can be strengthened The following inequalities known as the Strong Morse Inequalities also follow from standard linear algebra Theorem 1 8 The Strong Morse Inequalities With all notation as in Theorem 1 7 for each d 0 1 2 Cd Cai Cg_2 1 e9 gt ba ba ba 2 1 bp Comparing Strong Morse Inequalities for
9. X be a CW decomposition of a finite CW compler X Then X is homotopy equivalent to a finite CW decomposition with precisely the same number of cells of each dimension 8 ROBIN FORMAN as in 1 2 and with the cells attached so that their dimensions form a nondecreasing sequence I first learned of simplicial complexes in an algebraic topology course They were introduced as a category of topological spaces for which it was rather easy to define homology and cohomology i e in terms the simplical chain and cochain complexes One might be concerned that in the transition from simplicial complexes to CW complexes we have lost this ability to easily compute the homology In fact much of this computability remains Let X be a CW complex with a fixed CW decomposition Suppose that in this decomposition X is constructed from exactly ca cells of dimension d for each d 0 1 2 n dim K and let Ca X Z denote the space Z more precisely Ca X Z denotes the free abelian group generated by the d cells of X The following is one of the fundamental results in the theory of CW complexes Theorem 1 6 There are boundary maps a Ca X Z gt Cai X Z for each d so that Oq 1 6 Ou 0 and such that the resulting differential complex OO OD a ie Oe 7 calculates the homology of X That is if we define Ker 0q A C 0 aC 9 Im dq41 then for each d AAC H X Z where H X Z denotes the singular homology of X
10. X That is if we define Ke Bites Lo Im 0a41 then for each d Ay M H X Z In fact this statement is equivalent to the Strong Morse inequalities The main goal of this section is to present an explicit formula for the boundary operator This requires a closer look at of the notion of a gradient path Let a and amp be p simplices Recall from section 7 that a gradient path from amp to a is a sequence of simplices a af BPD aP BPD aP BD a a such that a lt 6 gt aj41 for each i 0 1 2 r and f ao gt f 8o gt f a f 1 gt gt f 8 gt f arsi Equivalently if V is the gradient vector field of f we require that for each 7 a and 6 be paired in V and 6 gt aj41 a In Figure 7 2 we show a single gradient path from the boundary of a critical 2 simplex to a critical edge a where the arrows indicate the gradient vector field V Given a gradient path as shown in Figure 7 2 an orientation on 6 induces an orientation on a We will not state the precise definition here The idea is that one slides the orientation from 6 along the gradient path to a For example for 30 ROBIN FORMAN the gradient path shown in Figure 7 2 the indicated orientation on 6 induces the indicated orientation on a a A gradient path from the boundary of b to a Figure 7 2 We are now ready to state the desired formula Theorem 7 3 Choose an orientation for each simpler Then for an
11. X4 is homotopic to a constant map since 7 q 1 X1 m1 S 0 If the attaching map is actually a constant map then it is easy to see that the space X is the wedge of two d spheres denoted by Sf A S4 The wedge of a collection of topological spaces is the space 6 ROBIN FORMAN resulting from choosing a point in each space taking the disjoint union of the spaces and identifying all of the chosen points Since the attaching map must be homotopic to a constant map Corollary 1 4 implies that X is homotopy equivalent to a wedge of two d spheres When constructing X3 by attaching a d cell to Xo the relevant information is a map from 4 to X2 and the homotopy type of the resulting space is determined by the homotopy class of this map All such maps are homotopic to a constant map since a 1 X2 amp ma 1 S A S S 0 Since Xz is homotopy equivalent to a wedge of two d spheres and the attaching map is homotopic to a constant map it follows from Theorem 1 3 that X3 is homotopy equivalent to the space that would result from attaching a d cell to S A Sf via a constant map i e X3 is homotopy equivalent to a wedge of three d spheres Continuing in this fashion we can see that X must be homotopy equivalent to a wedge of n d spheres The reader should not get the impression that the homotopy type of a CW complex is determined by the number of cells of each dimension This is true only for very few spaces and the reader migh
12. a vertex v and the maximum of f which must occur at a d simplex a Then X a is a combinatorial A USER S GUIDE TO DISCRETE MORSE THEORY 33 d manifold with boundary with a discrete Morse function with only a single critical simplex namely the vertex v It follows from Lemma 2 6 that X a collapses to v Whitehead s theorem now implies that X a is a combinatorial d ball which implies that X is a combinatorial d sphere 9 CANCELING CRITICAL POINTS One of the main problems in Morse Theory whether in the combinatorial or smooth setting is to find a Morse function for a given space with the fewest possible critical points much of the book 38 is devoted to this topic In general this is a very difficult problem since in particular it contains the Poincar conjecture spheres can be recognized as those spaces which have a Morse function with precisely 2 critical points In 31 Milnor presents Smale s proof 40 of the higher dimensional Poincar conjecture in fact a proof is presented of the more general h cobordism theorem completely in the language of Morse Theory Drastically oversimplifying matters the proof of the higher Poincar conjecture can be described as follows Let M be a smooth manifold of dimension gt 5 which is homotopy equivalent to a sphere Endow M with a smooth Morse function f One then proceeds to show that the critical points of f can be cancelled out in pairs until one is left with a
13. consecutive values of d yields Theorem 1 7 We mentioned earlier that a great benefit of passing from simplicial complexes to the more general CW complexes is that one often can use many fewer cells Let us take another look at this phenomenon in light of the Morse inequalities Consider the 10 ROBIN FORMAN case where X is a two dimensional torus so that with respect to any coefficient field bo 1 0 2 b2 1 From the weak Morse inequalities we have that for any CW decomposition Co gt bo 1 amp gt b 2 Co gt bp 1 A simplicial decomposition is a special case of a CW decomposition so these in equalities are satisfied when cg denotes the number of d simplices in a fixed simplicial decomposition However every simplicial decomposition has at least 7 O0 simplices 21 1 simplices and 14 2 simplices so these inequalities are far from equality It is generally the case that for a simplicial decomposition these inequalities are very far from optimal and hence are generally of little interest On the other hand earlier we demonstrated a CW decomposition of the two torus with exactly one 0 cell two l cells and one 2 cell The inequalities tell us in particular that one cannot build a two torus using fewer cells 2 THE BASICS OF DISCRETE MORSE THEORY The discussion in the previous section leads us to an important question Suppose one is given a finite simplicial complex X Typically we can expect that X has a C
14. imply that each simplex is in at most one pair of V This leads us to the following definition Definition 3 3 A discrete vector field V on K is a collection of pairs a lt B tYY of simplices of K such that each simplex is in at most one pair of V Such pairings were studied in 41 and 8 as a tool for investigating the possible f vectors for a simplicial compex Here we take a different point of view If one has a smooth vector field on a smooth manifold it is quite natural to study the dynamical system induced by flowing along the vector field One can begin the same sort of study for any discrete vector field In 12 we present a study of the dynamics associated to a discrete vector field Here we present just enough to continue our discussion of discrete Morse Theory Given a discrete vector field V on a simplicial complex K a V path is a sequence of simplices 3 1 aP P aP per a 0 oO BEY a gee r41 such that for each i 0 r lt 6 V and 6 gt ajy1 Qi We say such a path is a non trivial closed path if r gt 0 and ap a If V is the gradient vector field of a discrete Morse function f then we sometimes refer to a V path as a gradient path of f One idea behind this definition is the following result Theorem 3 4 Suppose V is the gradient vector field of a discrete Morse function f Then a sequence of simplices as in 3 1 is a V path if and only if a lt Bi gt ais for 20 ROB
15. 0 and 2 0 lt a f y fla 0 For example Figure 2 2 ii the vertex f 0 and the edge f 5 are critical and there are no other critical simplices We mention for later use that it follows from the axioms that a simplex cannot simultaneously fail both conditions in the test for criticality Lemma 2 4 If K is a simplicial complex with a Morse function f then for any simplex a either 1 6 gt a f 8 lt f a 0 or 2 y lt a f y gt f a 0 See Lemma 2 5 of 10 This lemma will play a crucial role in Section 3 We can now state the main theorem of discrete Morse Theory A USER S GUIDE TO DISCRETE MORSE THEORY 13 Theorem 2 5 Suppose M is a simplicial complex with a discrete Morse function Then M is homotopy equivalent to a CW complex with exactly one cell of dimension p for each critical simplex of dimension p Rather than present a proof of this theorem we will content ourselves here with a brief discussion of the main ideas A discrete Morse function gives us a way to build the simplicial complex by attaching the simplices in the order prescribed by the function i e adding first the simplices which are assigned the smallest values More precisely for any simplicial complex K with a discrete Morse function f and any real number c define the level subcomplex K c by K c Us a lt e Us lt a That is K c is the subcomplex consisting of all simplices a of K such that f a lt c a
16. A USER S GUIDE TO DISCRETE MORSE THEORY ROBIN FORMAN 0 INTRODUCTION A number of questions from a variety of areas of mathematics lead one to the problem of analyzing the topology of a simplicial complex We will see some examples in these notes However there are few general techniques available to aid us in this study On the other hand some very general theories have been developed for the study of smooth manifolds One of the most powerful and useful of these theories is Morse Theory There is a very close relationship between the topology of a smooth manifold M and the critical points of a smooth function f on M For example if f is compact then M must achieve a maximum and a minimum Morse Theory is a far reaching extension of this fact Milnor s beautiful book 30 is the standard reference on this subject In this paper we present an adaptation of Morse Theory that may be applied to any simplicial complex or more general cell complex There have been other adaptations of Morse Theory that can be applied to combinatorial spaces For example a Morse theory of piecewise linear functions appears in 26 and the very powerful Stratified Morse Theory was developed by Goresky and MacPherson 19 20 These theories especially the latter have each been successfully applied to prove some very striking results We take a slightly different approach than that taken in these references Rather than choosing a suitable class of co
17. Cambridge 91999 pp 177 206 Morse Theory and Evasiveness Combinatorica 20 2000 pp 498 504 Novikov Morse theory for cell complexes to appear in Int J of Math The Cohomology Ring and Discrete Morse Theory preprint 2001 K Fukaya Morse homotopy A category anf Floer homologies in Proc Garc Workshop on Geometry and Topology 93 Seoul 1993 Lecture Note ed H J Kim Lecture Note Ser 18 Seoul National University pp 1 102 Morse homotopy and its quantization in Geometric Topology Athens GA 1993 AMS IP Stud Adv Math 21 Amer Math Soc Prov RI 1997 pp 409 440 M Goresky and R MacPherson Stratified Morse Theory in Singularities Part I Arcata CA 1981 Proc Sympos Pure Math 40 Amer Math Soc R I 1983 pp 517 533 Stratified Morse Theory Ergebnisse der Mathematik und ihrer Grenzgebeite 3 14 Springer Verlag Berlin New York 1988 J Jonsson On the homology of some complexes of graphs preprint 1998 The decision tree method preprint 1999 J Kahn M Saks and D Sturtevant A topological approach to evasiveness Combinatorica 4 1984 pp 297 306 D Kozlov Collapsibility of A IIn Sp and some related CW complexes Proc of the AMS 128 2000 pp 2253 2259 Topology of spaces of hyperbolic polynomials with multiple roots preprint 2000 W Kihnel Triangulations of Manifolds with few Vertices in Advances in Differential Geometry and Topology World Sci Publis
18. IN FORMAN each i 0 1 r and F a 2 bo gt Flai 2 F 81 gt 2 F Br gt Flara That is the gradient paths of f are precisely those continuous sequences of simplices along which f is decreasing In particular this theorem implies that if V is a gradient vector field then there are no nontrivial closed V paths In fact the main result of this section is that the converse is true Theorem 3 5 A discrete vector field V is the gradient vector field of a discrete Morse function if and only if there are no non trivial closed V paths We will not prove this theorem here However many readers may notice the simi larity with the following standard theorem from the subject of directed graphs Theorem 3 6 Let G be a directed graph Then there is a real valued function of the vertices that is strictly decreasing along each directed path if and only if there are no directed loops We will show in section 6 that in fact Theorem 3 6 implies Theorem 3 5 The power of Theorem 3 5 is indicated in the next two sections in which we construct some discrete vector fields and use Theorem 3 5 to verify that they are gradient vector fields 4 Our FIRST EXAMPLE THE REAL PROJECTIVE PLANE Figure 4 1 i shows a triangulation of the real projective plane P Note that the vertices along the boundary with the same labels are to be identified as are the edges whose endpoints have the same labels In Figure 5 ii we illustra
19. W decomposition with many fewer cells than in the original simplicial decomposition How can one go about finding such an efficient CW decomposition for X In this section we present a technique discrete Morseh Theory which can be useful in such an investigation We note that the ideas we will describe can be applied with no modification at all to any finite regular CW complex and with only minor modifications to a general finite CW complex However for simplicity in this paper we will restrict attention to simplicial complexes We begin by recalling that a finite simplicial complex is a finite set of vertices V along with a set of subsets K of V The set K satisfies two main properties VCK A USER S GUIDE TO DISCRETE MORSE THEORY 11 2 IfaeK and 6Cathen fe K By a slight abuse of notation we will refer to the simplicial complex simply as K The elements of K are called simplices If a K and a contains p 1 vertices then we say that the dimension of a is p and we will sometimes denote this by a For simplices and 6 we will use the notation a lt 6 or 8 gt a to indicate that amp is a subset of 6 thinking of a and 6 as subsets of V and say that a is a face of 2 We emphasize that at this point we will not be placing any restrictions on the finite simplicial complexes under investigation In particular the complexes need not be manifolds even though many of our examples will be In section 9 we will briefly i
20. We will mention only that Vassiliev has shown how one can derive finite type knot invariants from the study of the space of singular knots i e maps from St to R which are not embeddings The homology of the simplicial complexes of not connected and not 2 connected graphs show up in his spectral sequence calculation of the homology of this space This is explained in 43 where Vassiliev derives the homotopy type of the complex of not connected graphs In 42 and 1 the topology of the space of not 2 connected graphs is determined with discrete Morse Theory playing a minor role in the latter reference This topic is reexamined in 37 in which the entire investigation is framed in the language of discrete Morse Theory Discrete Morse Theory is used to determine the topology of not 3 connected graphs in 21 In this section we will provide an introduction to this work by taking a look at the simpler case of the complex of not connected graphs We will show how the ideas of this paper may be used to determine the topology of Nn the simplicial compex of not connected graphs on n vertices Let me begin by pointing out that this complex can be well studied by more classical methods and the answer has also been found by Vassiliev in 43 The only novelty of this section is our use of discrete Morse Theory Our goal is to construct a discrete gradient vector field V on Mp the simplicial complex of all not connected graphs with the verte
21. any fixed 7 graphs which do not have a Hamiltonian cycle graphs which do not contain a minor isomorphic to H for any fixed graph H graphs which are r colorable for any fixed r and bipartite graphs Any monotone decreasing graph property P gives rise to a simplicial complex K where the d simplices of K are the graphs G P which have d 1 edges In particular if G is a d simplex in K then the faces of G are all of the nontrivial spanning subgraphs of G the monotonicity of P implies that each of these graphs is in Said in another way if P is nonempty then the vertices of K are the edges of Kn and a collection of vertices in K span a simplex if the spanning subgraph of K consisting of all edges which correspond to these vertices lies in P The simplicial complexes induced by many of the above mentioned monotone de creasing graph properties have been studied using the techniques of this paper See for example 6 7 21 22 27 37 These papers contain some beautiful mathe matics in which the authors construct by hand explicit discrete gradient vector A USER S GUIDE TO DISCRETE MORSE THEORY 23 fields along the way illuminating some of the intricate finer structures of the graph properties Some monotone graph properties have recently been the focus of intense interest because of their relation to knot theory Unfortunately this is probably not a good time for an in depth discussion of this fascinating topic
22. ay assume that the attaching map is a homeomorphism in which case X is a 2 dimensional disc If the winding number is 2 then without altering the homotopy type of X we may assume that the attaching map is a standard degree 2 mapping i e that wraps one circle around the other twice with no backtracking The reader should convince him herself that the result in this case is that X is the 2 dimensional projective space P In fact each winding number results in a homotopically distinct space These spaces can be distinguished by their homology since H X Z for the space X resulting from an attaching map with winding number n is isomorphic to Z nZ It seems that we are not quite done with this example because we assumed that the 1 cell was attached before the 2 cell and we must consider the alternative order in which Xj is the result of attaching a 2 cell to Xo In this case X is a 2 sphere and X X is the result of attaching a 1 cell to X The attaching map is a map of S into S Since S is connected i e mo S 0 all such maps are homotopic to a constant map Taking the attaching map to be a constant map yields that X S A S Thus adding the cells in this order merely resulted in fewer possibilities for the homotopy type of X This is a general phenomenon Generalizing the argument we just presented using the fact that 7 S 0 for i lt d yields the following statement Theorem 1 5 Let 1 2 OCXoCX C CX
23. e really referring to the negative of the gradient vector field i ii Another example of a gradient vector field Figure 3 2 As we will see in examples later these arrows are much easier to work with than the original discrete Morse function In fact this gradient vector field contains all of the information that we will need to know about the function for most applications The upshot is that if one is given a simplicial complex and one wishes to apply the theory of the previous section one need not construct find a discrete Morse function One only needs to find a gradient vector field This leads us to the following question Suppose we attach arrows to the simplices so that each simplex satifies exactly one of properties i ii iii above Then how do A USER S GUIDE TO DISCRETE MORSE THEORY 19 we know if that set of arrows is the gradient vector field of a discret Morse function This is the question we will answer in the remainder of this section Let K be a simplicial complex with a discrete Morse function f Then rather than thinking about the discrete gradient vector field V of f as a collection of arrows we may equivalently describe V as a collection of pairs q lt Beryy of simplices of K where a lt B t is in V if and only if f 8 lt f a In other words fa lt B is in V if and only if we have drawn an arrow that has a as its tail and 8 as its head The properties of a discrete Morse function
24. ecisely two such paths Namely following the unique gradient path beginning at each endpoint of e leads us to v The gradient path beginning at the head of e is the trivial path of 0 steps Since the orientation of e induces a orientation on the head of e and a orientation on the tail of e adding these two paths with their corresponding signs leads us to the formula that e 0 It can be seen from the illustration that there are precisely two gradient paths from the boundary of t to e and with the illustrated orientation for t both induce the chosen orientation on e so that A t 2e Therefore the homology of the real projective plane can be calculated from the following differential complex x2 0 Z Z Z 0 Thus we see that H P Z Z H P Z Z 2Z H2 P Z 0 A gradient vector field on the real projective plane Figure 7 4 32 ROBIN FORMAN 8 SPHERE THEOREMS As mentioned in our discussion at the end of section 4 one can sometimes use discrete Morse Theory to make statements about more than just the homotopy type of the simplicial complex One can sometimes classify the complex up to homeomor phism or combinatorial equivalence This will be a very short section as this topic seems a bit far from the main thrust of this paper In addition some terms will unfortunately have to be defined only cursorily or not at all So far we have not placed any restrictions on the simplicial complex
25. ence of integers n a nola lt nila lt lt nla where the n a s are the numbers of the questions answered yes if o a If V is the vector field induced by the guessing algorithm and aP pen aP is a V path then a 6o is in V which means that and 6o are not distinguished until the n 1 question Thus n Bo nolao lt n ao Krenna Nplao lt n l We now observe that the vertices of a are a subset of the vertices of b Suppose the vertex of 69 which is not in a is the vertex tested in question n 9 Then we must have i n 1 since ag a This demonstrates that n az nolao lt nilan lt gt lt Nj 1 A0 lt nilai lt 40 ROBIN FORMAN for some i lt n 1 and such that nj a1 gt ni ao Thus n ai gt n ao in the lexicographic order which is sufficient to prove that there are no closed orbits QED 11 FURTHER THOUGHTS We close this paper with some additional thoughts on the subjects discussed in this paper I would like to begin by encouraging the reader to take a look at the papers 24 25 and 3 In these papers discrete Morse Theory is used to investigate quite interesting problems These references were not mentioned earlier only because they did not easily fit into any of the previous sections of this paper There are a number of directions in which discrete Morse Theory can be extended and generalized Here we mention a few such possibilities
26. es under consideration The main idea of this section is that is if our simplicial complex has some additional structure then one may be able to strengthen the conclusion This idea rests on some very deep work of J H C Whitehead 44 Recall that a simplicial complex K is a combinatorial d ballif K and the standard d simplex ig have isomorphic subdivisions A simplicial complex K is a combinato rial d 1 sphere if K and q have isomorphic subdivisions where X4 denotes the boundary of Yq with its induced simplicial structure A simplicial complex K is a combinatorial d manifold with boundary if the link of every vertex is either a combi natorial d 1 sphere or a combinatorial d 1 ball The following is a special case of the main theorem of 44 Theorem 8 1 Let K be a combinatorial d manifold with boundary which simpliciallly collapses to a vertex Then K is a combinatorial d ball It is with this theorem and its generalizations that one can strengthen the con clusion of Theorem 2 5 beyond homotopy equivalence We present just one example Theorem 8 2 Let X be a combinatorial d manifold with a discrete Morse function with exactly two critical simplices Then X is a combinatoral d sphere The proof is quite simple given Theorem 8 1 If X is a combinatorial d manifold with a discrete Morse function f with exactly two critical simplices then the criti cal simplices must be the minimum of f which must occur at
27. f Morse Theory can give us any additional information as to how the cells are attached In fact one can deduce much of this information if one has enough information about the gradient paths of the Morse function This point is discussed further in section 7 where we will return to this example of the triangulated projective plane 22 ROBIN FORMAN 5 OUR SECOND EXAMPLE THE COMPLEX OF NOT CONNECTED GRAPHS A number of fascinating simplicial complexes arise from the study of monotone graph properties Let K denote the complete graph on n vertices and suppose we have labelled the vertices 1 2 n Let Gn denote the spanning subgraphs of Kn that is the subgraphs of Kp that contain all n vertices A subset P C Gn is called a graph property of graphs with n vertices if inclusion in P only depends on the isomorphism type of the graph That is P is a graph property if for all pairs of graphs G1 G2 Gn if Gi and G are isomorphic ignoring the labellings on the vertices then Gi P if and only if Gz P A graph property P of graphs with n vertices is said to be monotone decreasing if for any graphs G1 C G2 Gn if Ga E P then G1 E P Monotone decreasing properties abound in the study of graph theory Here are some typical examples graphs having no more than k edges for any fixed k graphs such that the degree of every vertex is less that for any fixed graphs which are not connected graphs which are not i connected for
28. gebraic and Topological Aspects Trans of Math Monographs 131 Amer Math Soc Providence R I 1993 S Smale On Gradient Dynamical Systems Annals of Math 74 1961 pp 199 206 The Generalized Poincar Conjecture in Dimensions Greater than Four Annals of Math 74 1961 pp 391 406 R Stanley A Combinatorial Decomposition of Acyclic Simplicial Complexes Discrete Math 118 1993 V Turchun Homology of Complexes of Biconnected Graphs Uspekhi Mat Nauk 52 1997 pp 189 190 V Vassiliev Complexes of Connected Graphs in The Gelfand Mathematical Seminars 1990 1992 pp 223 235 Birkhauser Boston Boston 1993 J H C Whitehead Simplicial Spaces Nuclei and m Groups Proc London Math Soc 45 1939 pp 243 327 E Witten Supersymmetry and Morse Theory J Diff Geom 17 1982 pp 661 692 DEPARTMENT OF MATHEMATICS RICE UNIVERSITY HousTON TX 77251
29. hen the vertices 3 4 5 in order Let y Qo 59 a denote a V path In particular ag and 69 must be paired in V The reader can check that if ag and 6o are first paired in V i gt 3 then either a is the head of an arrow in V in which case the V path cannot be continued or a is paired in V It follows by induction that there can be no closed V paths In summary V is a discrete gradient vector field on M with exactly one unpaired vertex and n 1 unpaired n 3 simplices We can now apply Theorem 2 5 to conclude Theorem 5 3 43 The complex Nn of not connected graphs on n vertices is ho motopy equivalent to the wedge of n 1 spheres of dimension n 3 6 A COMBINATORIAL POINT OF VIEW The notion of a gradient vector field has a very nice purely combinatorial description due to Chari 6 using which we can recast the Morse Theory in an appealing form A USER S GUIDE TO DISCRETE MORSE THEORY 27 We begin with the Hasse diagram of M that is the partially ordered set of simplices of M ordered by the face relation Consider the Hasse diagram as a directed graph The vertices of the graph are in 1 1 correspondence with the simplices of M and there is a directed edge from 8 to a if and only if is a codimension one face of p See Figure 6 1 i Now let V be a combinatorial vector field We modify the directed graph as follows If a lt 3 V then reverse the orientation of the edge between a a
30. hing N J 1990 pp 59 114 S Linusson and J Shareshian Complexes of t colorable graphs preprint 44 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 ROBIN FORMAN A Lundell and S Weingram The Topology of CW Complexes Van Nostrand Reinhold Company New York 1969 V Mathai and S G Yates Discrete Morse theory and extended L homology preprint 1999 J Milnor Morse Theory Annals of Mathematics Study No 51 Princeton University Press 1962 Lectures on the h Cobordism Theorem Princeton Mathematical Notes Princeton University Press 1965 M Morse The Calculus of Variations in the Large Amer Math Soc Colloquium Pub 18 Amer Math Soc Providence R I 1934 Bowls of a Non Degenerate Function on a Compact Differentiable Manifold in Differential and Combinatorial Topology A Symposium in Honor of M Morse Princeton University Press 1965 pp 81 104 S Novikov Multivalued functions and functions An analogue of the Morse theory Soviet Math Dokl 24 1981 pp 222 226 R L Rivest and J Vuillemin On recognizing graph properties from adjacency matrices Theor Comp Sci 3 1976 pp 371 384 M Schwartz Morse Homology Progress in Mathematics 111 Birkhauser Verlag Basel 1993 J Shareshian Discrete Morse Theory for Complexes of 2 Connected Graphs to appear in Topology V Sharko Functions on Manifolds Al
31. know before one can become a user Those interested in a more complete presentation of the theory can consult the reference 10 Earlier surveys of this work have appeared in 9 and 13 1 CW COMPLEXES The main theorems of discrete and smooth Morse Theory are best stated in the language of CW complexes so we begin with an overview of the basics of such complexes J H C Whitehead introduced CW complexes in his foundational work on homotopy theory and all of the results in this section are due to him The reader should consult 28 for a very complete introduction to this topic In this paper we will consider only finite CW complexes so many of the subtleties of the subject will not appear The building blocks of CW complexes are cells Let B denote the closed unit ball in d dimensional Euclidean space That is B x E s t z lt 1 The boundary A USER S GUIDE TO DISCRETE MORSE THEORY 3 of B4 is the unit d 1 sphere S x E4s t 2 1 A d cell is a topological space which is homeomorphic to B If is d cell then we denote by the subset of o corresponding to SIY C B4 under any homeomorphism between B4 and o A cell is a topological space which is a d cell for some d The basic operation of CW complexes is the notion of attaching a cell Let X bea topological space a d cell and f gt X a continuous map We let X Uy denote the disjoint union of X and o quotiented out by the equivalence re
32. lation that each point s is identified with f s X We refer to this operation by saying that X Uy o is the result of attaching the cell o to X The map f is called the attaching map We emphasize that the attaching map must be defined on all of That is the entire boundary of o must be glued to X For example if X is a circle then Figure 1 1 i shows one possible result of attaching a 1 cell to X Attaching a l cell to X cannot lead to the space illustrated in Figure 1 1 ii since the entire boundary of the 1 cell has not been glued to X 1 Gi i A 1 cell attached to a circle ii This is not a 1 cell attached to a circle Figure 1 1 We are now ready for our main definition A finite CW complex is any topological space X such that there exists a finite nested sequence 1 1 OCX CXC CX X 4 ROBIN FORMAN such that for each 1 0 1 2 n X is the result of attaching a cell to X _1 Note that this definition requires that Xo be a 0 cell If X is a CW complex we refer to any sequence of spaces as in 1 1 as a CW decomposition of X Suppose that in the CW decomposition 1 1 of the n 1 cells that are attached exactly cq are d cells Then we say that the CW complex X has a CW decomposition consisting of ca d cells for every d We note that a closed d simplex is a d cell Thus a finite simplicial complex is a CW complex and has a CW decomposition in which the cells are precisel
33. long with all of their faces Theorem 2 5 follows from two basic lemmas Lemma 2 6 If there are no critical simplices a with f a a b then M b is homotopy equivalent to M a In fact M b collapses to M a this will be explained later Lemma 2 7 If there is a single critical simpler a with f a a b then there is a map F S M a where d is the dimension of a such that M b is homotopy equivalent to M a Up B In Figure 2 8 we illustrate all of the level subcomplexes in the case that K is the circle triangulated with 3 edges and 3 vertices and f is the Morse function shown in Figure 2 2 ii Here we can see why these lemmas are true 14 ROBIN FORMAN 5 2 2 4 2 4 1 1 3 1 3 e 0 0 0 0 KO K 1 K 2 K 3 K 4 K 5 K The level subcomplezes of the discrete Morse function shown in Figure 2 2 ii Figure 2 8 Let us begin with Lemma 2 6 Consider the transition from K 0 to K 1 We have not added any critical simplices and just as the lemma predicts K 0 and K 1 are homotopy equivalent Let us try to understand why the homotopy type did not change To construct A 1 from K 0 we first have to add the edge f 1 This edge is not critical because it has a codimension one face which is assigned a higher value namely the vertex f 2 In order to have K 1 be a subcomplex we must also add this vertex Thus we see that the edge f 1 in K 1 has a free face i e a face which not the face of an
34. lt vo v2 v1 v2 lt vo v1 v2 That is V consists of those pairs of faces of S which are not distinguished by the guessing algorithm until the last question There is slight subtlety here in that a guessing algoithm pairs a vertex with the empty simplex while in our original definition it was not permitted to pair a simplex with Thus to get a true discrete vector field we must remove this pair from V It is precisely this subtle point that results in the reduced homology of K being the relevant measure of topological complexity rather than the nonreduced homology However for simplicity from now on we will simply ignore this technical point 38 ROBIN FORMAN V v v The vector field induced by the guessing algorithm shown in Figure 10 3 Figure 10 4 Theorem 10 5 This induced vector field is always a gradient vector field We will postpone the proof of this result until the end of this section Now restrict V to K by taking only those pairs in V s t both simplices are in K For example in our example this results in the vector field Vr vo lt vo vi From the previous theorem V has no closed orbits Any discrete vector field consisting of a subset of the pairs of V has fewer paths and hence also has no close orbits Therefore Vx is a gradient vector field on K Note that V pairs every face of S with another face and hence there are no critical simplices we are continuing to ignore f
35. nd 8 so that it now goes from a to 6 See Figure 6 1 ii A V path can be thought of as a directed path in this modified graph There are some directed paths in this modified Hasse diagram which are not V paths as we have defined them However the following result is not hard to check rian e e e gt PP Vi Vy V3 1 uM e e e AS Vi V V3 11 From a discrete vector field to a directed Hasse diagram Figure 6 1 Theorem 6 2 There are no nontrivial closed V paths if and only if there are no nontrivial closed directed paths in the corresponding directed Hasse diagram 28 ROBIN FORMAN Thus in this combinatorial language a discrete vector field is a partial matching of the Hasse diagram and a discrete vector field is a gradient vector field if the partial matching is acyclic in the above sense Note that using Theorem 6 2 we can see that Theorem 3 5 does follow from Theorem 3 6 We can now restate some of our earlier theorems in this language There is a very minor complication in that one usually includes the empty set as an element of the Hasse diagram considered as a simplex of dimension 1 while we have not considered the empty set previously Theorem 6 3 Let V be an acyclic partial matching of the Hasse diagram of K of the sort described above assume that the empty set is not paired with another simplex Let up denote the number of unpaired p simplices Then M is homotopy equivalent to a CW complezx wi
36. ndicate how some our conclusions can be strengthened in the case that the complexes are assumed to have additinal structure A discrete Morse function on K is a function which roughly speaking assigns higher numbers to higher dimensional simplices with at most one exception locally at each simplex More precisely Definition 2 1 A function f K R is a discrete Morse function if for every a K 1 B gt a f 8 lt fa lt 1 and 2 y lt a f y gt fla lt 1 A simple example will serve to illustrate the definition Consider the two complexes shown in Figure 2 2 Here we indicate functions by writing next to each simplex the value of the function on that simplex The function i is not a discrete Morse function as the edge f 0 violates rule 2 since it has 2 lower dimensional neighbors on which f takes on higher values and the vertex f 5 violates rule 1 since it has 2 higher dimensional neighbors on which f takes on lower values The function ii is a Morse function Note that a discrete Morse function is not a continuous function on K Rather it is an assignment of a single number to each simplex 12 ROBIN FORMAN 0 0 1 Gi i This is not a discrete Morse function ii This is a discrete Morse function Figure 2 2 The other main ingredient in Morse Theory is the notion of a critical point Definition 2 3 A simpler aP is critical if 1 6 gt a f 8 lt fla
37. ndicate this pairing by drawing an arrow from the vertex f 2 pointing into the edge f 1 Similarly we draw an arrow from the vertex f 4 pointing into the edge f 3 See Figure 3 1 One can think of these arrows as pictorially indicating the simplicial collapse that is referred to in the proof of Lemma 2 6 The gradient vector field of the Morse function shown in Figure 2 2 it Figure 3 1 We can apply this process to any simplicial complex with a discrete Morse function The arrows are drawn as follows Suppose a is a non critical simplex with B gt a satisfying f 8 lt f a We then draw an arrow from a to 3 Figure 3 2 illustrates a more complicated example Note that the discrete Morse function drawn in this figure has one critical vertex f 0 and one critical edge f 11 Theorem 2 5 18 ROBIN FORMAN implies this simplicial complex is homotopy equivalent to a CW complex with exactly one 0 cell and one 1 cell i e a circle It follows from Lemma 2 4 that that every simplex a satisfies exactly one of the following i a is the tail of exactly one arrow ii a is the head of exactly one arrow iii a is neither the head nor the tail of an arrow Note that a simplex is critical if and only if it is neither the tail nor the head of any arrow These arrows can be viewed as the discrete analogue of the gradient vector field of the Morse function To be precise when we say gradient vector field we ar
38. ntinuous functions on our spaces to play the role of Morse functions we will be assigning a single number to each cell of our complex This work was partially supported by the National Science Foundation 1 2 ROBIN FORMAN and all associated processes will be discrete Hence we have chosen the name discrete Morse Theory for the ideas we will describe Of course these different approaches to combinatorial Morse Theory are not dis tinct One can sometimes translate results from one of these theories to another by smoothing out a discrete Morse function or by carefully replacing a continuous function by a discrete set of its values However that is not the path we will follow in this paper Instead we show that even without introducing any continuity one can recreate in the category of combinatorial spaces a complete theory that captures many of the intricacies of the smooth theory and can be used as an effective tool for a wide variety of combinatorial and topological problems The goal this paper is to present an overview of the subject of discrete Morse Theory that is sufficient both to understand the major applications of the theory to combinatorics and to apply the the theory to new problems We will not be presenting theorems in their most recent or most general form and simple examples will often take the place of proofs We hope to convey the fact that the theory is really very simple and there is not much that one needs to
39. or now the simplex which is paied with the emptyset Thus the critical simplices of Vx are precisely the simplices of K which are paired in V with a face of S which is not in K These are precisely the simplices of K which are the evaders of the guessing algorithm The Morse inequalities of Theorem 2 11 i imply that the number of evaders in K is at least dim H K Evaders occur in pairs with each pair having one face of K and one face not in K This yields the following quantitative refinement of Theorem 10 1 A USER S GUIDE TO DISCRETE MORSE THEORY 39 Theorem 10 6 For any guessing algorithm of evaders gt 2dim H K Suppose that K is nonevasive Then there is some guessing algorithm which has no evaders From our above discussion we seen that this implies that K has a gradient vector field with no critical simplices Actually this is not quite true The gradient vector field must have a critical vertex the vertex that is paired with the empty set this is that minor technicality that we have been ignoring Applying Lemma 2 6 yields the following strengthening of Theorem 10 1 Theorem 10 7 If K is nonevasive then K simplicially collapses to a point This theorem appears in 23 The interested reader can consult 14 for some addi tional refinements of this theorem We end this section with a proof of Theorem 10 5 Fix a subcomplex K of an n simplex S and a guessing algorithm Associate to each p simplex a of S the sequ
40. or field that has been constructed after the consideration of vertex i and V V the final discrete vector field When we are done the only unpaired 26 ROBIN FORMAN graphs in V will be G and those graphs that are the union of two connected trees one containing the vertex 1 and one containing the vertex 2 In addition both trees have the property that the vertex labels are increasing along every ray starting from the vertex 1 or the vertex 2 There are precisely n 1 such graphs and they each have n 2 edges and hence correspond to an n 3 simplex in Ny It remains to see that the discrete vector field V is a gradient vector field i e that there are no closed V paths We first check that Vig is a gradient vector field Let y aP BP aP i e the smaller graph of some pair in Vi2 with bo being the head of the arrow i e denote a Vi2 path Then apo must be the tail of an arrow Bo ao 1 2 The simplex a is a codimension one face of fo other than o Thus a corresponds to a graph of the form ap 1 2 e where e is an edge of ag other than 1 2 Since a contains the edge 1 2 it is the head of an arrow in V 2 i e the larger graph of some pair in Vj2 which implies that y cannot be continued to a longer Vjo path This certainly implies that there are no closed Vi2 paths The same sort of argument will work for V Recall that V is constructed in stages by first considering the edge 1 2 and t
41. t enjoy coming up with some other examples The fact that wedges of spheres can in fact be identified by this numerical data partly explains why the main theorem of many papers in combinatorial topology is that a certain simplicial complex is homotopy equivalent to a wedge of spheres Namely such complexes are the easiest to recognize However that does not explain why so many simplicial complexes that arise in combinatorics are homotopy equivalent to a wedge of spheres I have often wondered if perhaps there is some deeper explanation for this 3 Suppose that X is a CW complex which has a CW decomposition consisting of exactly one 0 cell one 1 cell and one 2 cell Let us consider a CW decomposition for X with these cells 0 C Xo C X C X X We know that Xo is the 0 cell Suppose that X is the result of attaching the 1 cell to Xo Then X must be a circle and X arises from attaching a 2 cell to X The attaching map is a map from the A USER S GUIDE TO DISCRETE MORSE THEORY 7 boundary of the 2 cell i e a circle to X which is also a circle Up to homotopy such a map is determined by its winding number which can be taken to be a nonnegative integer If the winding number is 0 then without altering the homotopy type of X we may assume that the attaching map is a constant map which yields that X S A S where denotes homotopy equivalence If the winding number is 1 then without altering the homotopy type of X we m
42. t essential to any problem it is usually only a convenient and efficient language Anything that can be done with Morse Theory can be done without it It seems to me that Morse Theory takes on a special significance in three different cases First are the cases in which Morse Theory is not intrinsic to the problem but where the existence of such an efficient language may make the difference between whether or not one is able to see the way to the end of a problem The best example of this in the smooth setting I think is the proof of the higher dimensional Poincar conjecture 39 31 Most of the applications of discrete Morse Theory mentioned in section 5 for example seem to fall into this category Second are the cases in which the space one is studying comes naturally endowed with a Morse function or a gradient 42 ROBIN FORMAN vector field Here the prime example is Bott s proof of Bott periodicity 5 see also Part IV of 30 resting on the fact that the loop space of a Riemannian manifold is endowed with a natural Morse function In the combinatorial setting I would place the Morse theoretic examination of evasiveness of the previous section in this category Third are the cases in which the objects under investigation can be naturally identified as the critical points of a Morse function on a larger space Examples of this phenomenon abound in differential geometry where one often studies extremals of energy functionals
43. te a discrete vector field V on this simplicial complex One can easily see that there are no closed V paths since all V paths go to the boundary of the figure and there are no closed V paths on the boundary and hence is a gradient vector field The only simplices which are neither the head nor the tail of an arrow are the vertex labelled 1 the edge e and the triangle t Thus by Theorem 2 5 the projective plane is homotopy equivalent A USER S GUIDE TO DISCRETE MORSE THEORY 21 to a CW complex with exactly one 0 cell one 1 cell and one 2 cell Of course we already knew this from our discussion of example 3 in section 2 3 3 e 2 1 2 1 1 3 2 1 e 3 2 i ii i A triangulation of the real projective plane ii A discrete gradient vector field on PP Figure 4 1 This example gives rise to two potential concerns The first is that from the main theorem we learn only a statement about homotopy equivalence This is sufficient if one is only interested in calculating homology or homotopy groups However one might be interested in determining the PL homeomorphism type of the complex This is possible in some cases using deep results of J H C Whitehead We revisit this topic in section 8 The second potential point of concern is that as we saw in section 2 there are an infinite number of different homotopy types of CW complexes which can be built from exactly one 0 cell one 1 cell and one 2 cell One might wonder i
44. tegory of simple homotopy equivalence Now let us turn to Lemma 2 7 and investigate what happens when one adds a critical simplex for example when making the transition from K 4 to K 5 In this case we are adding a critical edge We can see clearly from the illustration that we pass from K 4 to K 5 by attaching a 1 cell just as predicted by Lemma 2 7 To see why this works in general consider a critical d simplex a It follows from the definition of a critical simplex that each face of a is assigned a smaller value than 16 ROBIN FORMAN a which implies in turn that each face of appears in a previous level subcomplex Thus the entire boundary of a appears in an earlier level subcomplex sothat when it comes time to add a we must glue it in along its entire boundary This is precisely the process of attaching a d cell This completes our discussion of the proof Perhaps this is a good time to point out that one can define a discrete Morse function on any simplicial complex Namely one can simply let f a dimension a for each simplex a In this case every simplex is critical and Theorem 2 5 is a rather uninteresting tautology However as we will see in examples one can often construct discrete Morse functions with many fewer critical simplices Let K be a simplicial complex with a discrete Morse function Let mp denote the number of critical simplices of dimension p Let F be any field and bp dimH K F the p Betti n
45. th exactly up cells of dimension p for each p gt 0 An important special case is when V is a complete matching that is every simplex this time including the empty simplex is paired with another simplex In this case Lemma 2 9 implies the following result Theorem 6 4 Let V be a complete acyclic matching of the Hasse diagram of K then K collapses onto a vertex so that in particular K is contractible This result was used in a very interesting fashion in 1 7 THE MORSE COMPLEX In this section we will see how knowledge of the gradient paths of a discrete Morse function on a space K can allow one to strengthen the conclusions of the main theo rems In particular rather than just knowing the number of cells in a CW deompo sition for K one can calculate the homology exactly Let K be a simplicial complex with a Morse function f Let C X Z denote the space of p simplicial chains and M C C X Z the span of the critical p simplices We refer to M as the space of Morse chains If we let m denote the number of A USER S GUIDE TO DISCRETE MORSE THEORY 29 critical p simplices then we obviously have Mp SD Since homotopy equivalent spaces have isomorphic homology the following theorem follows from Theorems 2 5 and 1 6 Theorem 7 1 There are boundary maps a Mp gt Ma for each d so that Ona fe ay 0 and such that the resulting differential complex dn Be B MM og a ET calculates the homology of
46. the dynamical properties of the flow associated to a general discrete vector field One area in which much work remains to be done is the investigation of discrete Morse Theory for infinite simplicial complexes The theory as desribed in this paper can be applied without change to an infinite simplicial complex K endowed with a discrete Morse function f which is proper i e one in which for each real number c the level subcomplex K c is a finite complex Unfortunately properness is often an unnatural requirement when considering the infinite simplicial complexes which arise in practice In the interesting paper 29 discrete Morse Theory is applied to the investigation of infinite simplicial complexes K which arise as a covering space of a finite simplicial complex K In this case the authors restrict attention to discrete Morse functions which are lifts of a Morse function on A and compare the number of critical simplices to the L Betti numbers of K While it appears to be too much to hope that one can develop a useful theory that applies to all infinite simplicial complexes with no restrictions on the discrete Morse function it seems likely that there is room for very useful investigations of large classes of complexes and functions with restrictions different than those already considered I will close these notes with some comments of a less rigorous nature Whether in the smooth category or the combinatorial category Morse Theory is no
47. the gradient vector field along this path replacing the figure by the vector field shown in the botton drawing in Figure The uniqueness of the gradient path implies that the resulting discrete vector field has no closed orbits and hence by Theorem 3 5 is the gradient vector field of some Morse function Moreover and 8 are not critical for this new Morse function while the criticality of all other simplices is unchanged This completes the proof A USER S GUIDE TO DISCRETE MORSE THEORY 35 The proof in the smooth case proceeds along the same lines However in addition to turning around those vectors along the unique gradient path from 6 to a one must also adjust all nearby vectors so that the resulting vector field is smooth Moreover one must check that the new vector field is the gradient of a function so that in particular modifying the vectors did not result in the creation of a closed orbit This is an example of the sort of complications which arise in the smooth setting but which do not make an appearance in the discrete theory This theorem was recently put to very good use in 2 in which discrete Morse Theory is used to determine the homotopy type of some simplicial complexes arising in the study of partitions It is fascinating and quite pleasing to see the same idea play a central role in two subjects the Poincar conjecture and the study of partitions which seem to have so little to do with one another
48. umber with respect to F Combining Theorems 2 5 1 7 and 1 8 and the fact that homotopy equivalent spaces have isomorphic homology we have the following inequalities Theorem 2 11 I The Weak Morse Inequalities i For each p 0 1 2 n where n is the dimension of K Mp gt bp it Mo M My 1 m bo bi b2 1 bn x K l II The Strong Morse Inequalities For each p 0 1 2 n n 1 Mp Mp1 E Mo bp bp 1 bo 3 GRADIENT VECTOR FIELDS Any ambitious reader who has already started trying some examples will have noticed that the theory as presented in the previous section can be a bit unwieldy After all how is one to go about assigning numbers to each of the simplices of a simplicial complex so that they satisfy the axioms of a discrete Morse function A USER S GUIDE TO DISCRETE MORSE THEORY 17 Fortunately in practice one need not actually find a discrete Morse function Finding the gradient vector field of the Morse function is sufficient This requires a bit of explanation Let us now return to the example in Figure 2 2 ii Noncritical simplices occur in pairs For example the edge f 1 is not critical because it has a lower dimensional neighbor which is assigned a higher value i e the vertex f 2 Similarly the vertex f 2 is not critical because it has a higher dimensional neighbor which is assigned a lower value i e the edge f 1 We i
49. unpaired in Vj2 so we can pair G with G 1 3 If vertex 3 is in G4 then the graph G is still unpaired if and only if G contains the edge 1 3 and G 1 3 is the union of three connected components one containing vertex 1 one containing vertex 2 and one containing vertex 3 A USER S GUIDE TO DISCRETE MORSE THEORY 25 Similarly if vertex 3 is in Gy and G does not contain the edge 2 3 then pair G with G 2 3 Let V3 denote the resulting discrete vector field The unpaired graphs in V3 are G and those that either contain the edge 1 3 and have the property that G 1 3 is the union of three connected components one containing vertex 1 one containing vertex 2 and one containing vertex 3 or contain the edge 2 3 and have the property that G 2 3 is the union of three connected components one containing vertex 1 one containing vertex 2 and one containing vertex 3 We illustrate these graphs in Figure 5 2 The circles in this figure indicate connected graphs A aK y A The graphs other than G which are unpaired in the vector field V3 Figure 5 2 Now consider the location of the vertex labelled 4 and pair any graph G which is unpaired in V3 with G 1 4 G 2 4 or G 3 4 if possible at most one of these graphs is unpaired in V3 Call the resulting discrete vector field V4 We continue in this fashion considering in turn the vertices labelled 5 6 n Let V denote the discrete vect
50. x set 1 2 3 n The con struction will be in steps Let Vio denote the discrete vector field consisting of all pairs G G 1 2 where G is any graph in Mp which does not contain the edge 1 2 and such that G 1 2 Mn Another way of describing Vig is that if G is any graph in Mp which contains the edge 1 2 then G 1 2 and G are paired in Vig Actually there is one exception to this rule Let G denote the graph consisting of only the single edge 1 2 Then G 1 2 is the empty graph which corresponds 24 ROBIN FORMAN to the empty simplex in Mn and may not be paired in a discrete vector field Thus G is unpaired in Vj The graphs in Mn other than G which are unpaired in Vig are those that do not contain the edge 1 2 and have the property that G 1 2 Ny That is those disconnected graphs G with the property that G 1 2 is connected Such a graph must have exactly two connected components one of which contains the vertex labelled 1 and one which contains the vertex labelled 2 We denote these connected components by Gi and Go resp See Figure 5 1 a a connected connected graph graph G G 1 2 The graphs other than G which are unpaired in the vector field Vio Figure 5 1 Let G be a graph other than G which is unpaired in Vj2 and consider vertex 3 This vertex must either be in G4 or Gg Suppose that vertex 3 is in G If G does not contain the edge 1 3 then G 1 3 is also
51. y critical p 1 simpler 3 set 7 1 b 5 Caga critical aP Ca m q YET 8a where 6 a is the set of gradient paths which go from a maximal face of p to a where The multiplicity m y of any gradient path y is equal to 1 depending on whether given y the orientation on p induces the chosen orientation on a or the opposite orientation With this differential the complex 7 1 computes the homology of K A proof this theorem appears in section 8 of 10 We refer to this complex 7 1 with the differential 7 1 as the Morse complex it goes by many different names in the litereature An extensive study of the Morse complex in the smooth category appears in 36 We end this section with a demonstration of how the ideas of this section may be applied to the example of the real projective plane P as illustrated in Figure 4 1 ii We saw in section 2 how discrete Morse Theory can help us see that P has a CW decomposition with exactly one 0 cell one 1 cell and one 2 cell Here we A USER S GUIDE TO DISCRETE MORSE THEORY 31 will see how Morse Theory can distinguish between the spaces which have such a CW decomposition In Figure 7 4 we redraw the gradient vector field and indicate a chosen orientation on the critial edge e and the critical triangle t Let us now calculate the boundary map in the Morse complex To calculate a e we must count all of the gradient paths from the boundary of e to v There are pr
52. y other simplex in K 1 We can deformation retract K 1 to K 0 by pushing in the edge f 1 starting at the vertex f 2 This is a very general phenomenon That is it follows from the axioms for a discrete Morse function that for any simplicial complex with any discrete Morse function when passing from one level subcomplex to the next the noncritical simplices are added in pairs each of which consists of a simplex and a free face Suppose that Ky C Ky are simplicial complexes and K has exactly two simplices a and that are not in Ko where 8 is a free face of a Then it is easy to see that K is a deformation retract of K and hence K and K are homotopy equivalent see Figure 2 9 This special sort of combinatorial deformation retract is called a simplical collapse If one can transform a simplicial complex Ky into a subcomplex K by simplicial collapses then A USER S GUIDE TO DISCRETE MORSE THEORY 15 we say that K collapses to Kz and we indicate this by K N K2 Figure 2 10 shows a 2 dimensional simplex collapsing to one of its vertices OO Ky A simplicial collapse Figure 2 9 Af A 2 simplezx collapsing to a vertex Figure 2 10 The process of simplicial collapse was studied by J H C Whitehead and he defined simple homotopy equivalence to be the equivalence relation generated by simplicial collapse This indicates that discrete Morse Theory may be particularly useful when working in the ca
53. y the closed simplices In Figure 1 2 we demonstrate a CW decomposition of a 2 dimensional torus which beginning with the 0 cell requires attaching two 1 cells and then one 2 cell Here we can see one of the most compelling reasons for considering CW complexes rather than just simplicial complexes Every simplicial decomposition of the 2 torus has at least 7 vertices 21 edges and 14 triangles QO Ca is Ky Xi x X A CW decomposition of a 2 torus Figure 1 2 It may seem that quite a bit has been lost in the transition from simplicial complexes to general CW complexes After all a simplicial complex is completely described by a finite amount of combinatorial data On the other hand the construction of a CW decomposition requires the choice of a number of continuous maps However if one is only concerned with the homotopy type of the resulting CW complex then things begin to look a bit more manageable Namely the homotopy type of X Uy o depends only on the homotopy type of X and the homotopy clas of f A USER S GUIDE TO DISCRETE MORSE THEORY 5 Theorem 1 3 Let h X X denote a homotopy equivalence o a cell and fy a gt X fo a X two continuous maps If ho f is homotopic to fo then X Us o and X Us o are homotopy equivalent An important special case is when h is the identity map We state this case separately for future reference Corollary 1 4 Let X be a topological space o a cell and fi fo
Download Pdf Manuals
Related Search