A USER'S GUIDE TO DISCRETE MORSE THEORY 0. Introduction A
Contents
1. 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 Complexes 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 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 and Floer homologies in Proc Gare Work shop on Geometry and Topology 93 Seoul 1993 ed H J Kim Lecture Notes Ser 18 Seoul National University pp 1 102 Morse hom2. amp be p simplices Recall from Section 7 that a gradient path from a to a is a sequence of simplices a aP Be aP CER aP Bern a such that a lt Bi gt aj41 for each i 0 1 2 r and flao gt f Go gt f a f Gi gt f G gt flarsi Equivalently if V is the gradient vector field of f we require that for each i a and 8 be paired in V and gt a 4 Qi 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 induces an orientation on a We will not state the precise definition here The idea is that one slides the orientation from along the gradient path to a For example for 24 ROBIN FORMAN the gradient path shown in Figure 7 2 the indicated orientation on induces the indicated orientation on a a A gradient path from the boundary of 3 to a Figure 7 2 We are now ready to state the desired formula Theorem 7 3 Choose an orientation for each simplex Then for any critical p 1 simplex 3 set 7 2 B D Ca bQ critical a P Ca 3 m y ye b a where 1 3 a is the set of gradient paths which go from a maximal face of B to a The multiplicity m y of any gradient path y is equal to 1 depending on whether given y the orientation on B induces the chosen orientation on a or the oppos
3. lt Nplao lt n l1 We now observe that the vertices of a are a subset of the vertices of b Suppose the vertex of 39 which is not in a is the vertex tested in question n 8o Then we must have i A n 1 since ap 4 a1 This demonstrates that n a1 No ao lt n1 Ao lt lt ni 1 0 lt nilai lt lt for some i lt n 1 and such that nj a gt n ao Thus n a gt n ao in the lexicographic order which is sufficient to prove that there are no closed orbits QED 32 ROBIN FORMAN 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 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 th
4. 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 80 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 This work was partially supported by the National Science Foundation 2 ROBIN FORMAN We take a slightly different approach than that taken in these references Rather than choosing a suitable class of continuous functions on our spaces to play the role of Morse functions we will be assigning a single number to each cell of our complex and all associated processes will be discrete Hence we have chosen the name discrete Morse Theo
5. G is any graph in NV which contains the edge 1 2 then G 1 2 and G are paired in Vip 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 to the empty simplex in Mn and may not be paired in a discrete vector field Thus G is unpaired in Viv The graphs in M other than G which are unpaired in Viz are those that do not contain the edge 1 2 and have the property that G 1 2 Ma 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 G and Gg resp See Figure 5 1 A USER S GUIDE TO DISCRETE MORSE THEORY 19 a connected graph G G 1 2 The graphs other than G which are unpaired in the vector field Vj Figure 5 1 Let G be a graph other than G which is unpaired in Vi2 and consider vertex 3 This vertex must either be in G or G2 Suppose that vertex 3 is in G1 If G does not contain the edge 1 3 then G 1 3 is also unpaired in Viz 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
6. Math 120 1993 pp 175 182 V Turchin Homology of Complexes of Biconnected Graphs Uspekhi Mat Nauk 52 1997 pp 189 190 translation in Russian Math Surveys 52 1997 426 427 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
7. a boundary map For example let us choose a coefficient field F and tensor everything with F to get a differential complex j 6 00 On Ee 6110 ee ee LR ea Pi NY which calculates H X F where now Ca 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 cq 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 ba 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 b b tbo then we also have K X co Cr tae 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 Ca Cai Ca 2 1 ep gt ba ba ba 1 bo 8 ROBIN FORMAN Comparing Strong Morse Inequalities for consecutive values of d and using the fact that b 0 for i larger than the dimension of K yields Theorem 1 7 We mentioned earlier that a great benefit of passing from simplicial complexes to the mor
8. 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 o 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 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 than n 1 questions 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 ness of K and its algebraic topology Theorem 10 1 If H K 4 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 vp v and vs with K the subcomplex consisting of the edge
9. the 2 torus has at least 7 vertices 21 edges and 14 triangles 4 ROBIN FORMAN X Xa X3 A CW decomposition of a 2 torus e Xo 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 U depends only on the homotopy type of X and the homotopy class of f Theorem 1 3 Leth X X denote a homotopy equivalence o a cell and f ao X fo a6 X two continuous maps If ho f is homotopic to fo then X Us o and X Up 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 X two continuous maps If f and fz are homotopic then X Up a and X Us 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 classes of the attaching maps Since homotopy classes are discrete objects we have now recaptured a bit of the combinatorial atmosphere that we seemingl
10. vo v1 together with the vertex vz A USER S GUIDE TO DISCRETE MORSE THEORY 29 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 a v2 vo v2 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 Ne ve is yrs Te IS o olla e olfe u v lv v luv v A guessing algorithm 30 ROBIN FORMAN 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 vi vo lt vo vil ve lt vo va v1 v2 lt vo v1 val 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 algorithm 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 dis
11. 2 and one containing vertex 3 Similarly if vertex 3 is in Gj 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 20 ROBIN FORMAN gt K 3s Va 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 Vi We continue in this fashion considering in turn the vertices labelled 5 6 n Let V denote the discrete vector 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 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 vert
12. EORY 15 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 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 satisfies exactly one of properties i ii iii above Then how do we know if that set of arrows is the gradient vector field of a discrete 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 a lt Bt 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 Bt 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 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
13. Hats e e e Pd Vi V V3 i IO e e e ee 2 i i 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 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 K is homotopy equivalent to a CW complez with 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
14. 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 C Xo C Xi 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 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 StA 8 where denotes homotopy equivalence If the winding number is 6 ROBIN FORMAN 1 then without altering the homotopy type of X we may 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 ca
15. 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 a which implies in turn that each face of a appears in a previous level subcomplex Thus the entire boundary of a appears in an earlier level subcomplex so that 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 dim qa for each simplex a In this case every simplex is critical and Theorem 2 5 is a rather A USER S GUIDE TO DISCRETE MORSE THEORY 13 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 b dim H K F the pt Betti number 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 inequa
16. P gives rise to a simplicial complex KC 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 X Said in another way if P is nonempty then the vertices of K are the edges of K and a collection of vertices in K span a simplex if the spanning subgraph of Kn 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 18 ROBIN FORMAN for example 6 7 21 22 27 37 These papers contain some beautiful math ematics in which the authors construct by hand explicit discrete gradient vector 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 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 conn
17. S minaire Lotharingien de Combinatoire 48 2002 Article B48c A USER S GUIDE TO DISCRETE MORSE THEORY ROBIN FORMAN ABSTRACT A number of questions from a variety of areas of mathematics lead one to the problem of analyzing the topology of a simplicial complex 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 In this paper we present a combinatorial adaptation of Morse Theory which we call discrete Morse Theory that may be applied to any simplicial complex or more general cell complex The goal of 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 know before one can become a user 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
18. a combinato rial d 1 sphere if K and X4 have isomorphic subdivisions where ig denotes the boundary of X4 with its induced simplicial structure A simplicial complex K is a 26 ROBIN FORMAN 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 simplicially 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 combinatorial 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 a vertex v and the maximum of f which must occur at a d simplex a Then X a is a combinatorial 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 combinat
19. ace 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 gt is homotopy equivalent to a wedge of two d spheres When constructing X by attaching a d cell to X2 the relevant information is a map from S t to X 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 tq_1 X2 S ma 1 S4 A S S 0 Since X 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 S 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 might 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
20. ake 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 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 ex amination 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 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 of 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 existen
21. alent to K a In fact K b collapses to K a this will be explained later Lemma 2 7 If there is a single critical simplex a with f a a b then there is a map F S K a where d is the dimension of a such that K b is homotopy equivalent to K a Up B A USER S GUIDE TO DISCRETE MORSE THEORY 11 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 5 2 2 4 2 I 1 j l 3 e 0 0 0 0 K 0 K 1 K 2 K 3 K 4 K 5 K The level subcomplexes of the discrete Morse function shown in Figure 2 2 it Figure 2 8 Let us begin with Lemma 2 6 Consider the transition from A 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 K 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 is not the face of any 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 1 2 This is a ver
22. ath 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 Mp 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 compler 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 We begin with the Hasse diagram of K that is the partially ordered set of simplices of K 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 K and there is a directed edge from to a if and only if a is a codimension one face of G 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 and so that it now goes from a to 8 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 22 ROBIN FORMAN
23. cal 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 HEP gt a f 8 lt f a 9 or 2 y lt a FO gt fla 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 Theorem 2 5 Suppose K is a simplicial complex with a discrete Morse function Then K 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 Usa se Upsa P That is K c is the subcomplex consisting of all simplices a of K such that f a lt c along 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 K b is homotopy equiv
24. ce 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 combinato rial 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 34 10 11 12 13 14 15 17 18 19 20 21 22 23 24 25 26 ROBIN FORMAN REFERENCES E Babson A Bj rner S Linusson 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 to appear in Topology E Batzies and V Welker Discrete Morse Theory for Cellular Resolutions J Reine Angew Math 543 2002 pp 147 168 M Betz and R Cohen Graph moduli space and cohomology operations Turk J of Math 18 1994 pp 23 41
25. crete 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 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 such that both simplices are in K For example in our example this results in the vector field Vic vo lt vo v 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 closed 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 for now the simplex which is paired with the emptyset Thus the critical simplices A USER S GUIDE TO DISCRETE MORSE THEORY 31 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 evade
26. d 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 1 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 ii 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 BCX CX C CK X such that for each i 0 1 2 n X is the result of attaching a cell to Xq_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 cq 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 precisely 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
27. dge 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 14 ROBIN FORMAN 5 The gradient vector field of the Morse function shown in Figure 2 2 ii 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 3 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 1 0 and one critical edge f 11 Theorem 2 5 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 are really referring to the negative of the gradient vector field i i Another example of a gradient vector field A USER S GUIDE TO DISCRETE MORSE TH
28. e 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 example The relevant study takes place in Section 6 of 10 In 12 we study 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 described 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 subcomp
29. e 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 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 bg 1 Cc gt b 2 Co gt ba 1 A simplicial decomposition is a special case of a CW decomposition so these in equalities are satisfied when cq denotes the number of d simplices in a fixed simplicial decomposition However every simplicial decomposition has at least 7 0 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 1 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 CW 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
30. ected 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 Mn the simplicial complex 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 vertex set 1 2 3 n The con struction will be in steps Let Viz 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 Vj is that if
31. egin 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 x lt 1 The boundary of B is the unit d 1 sphere S x Et z 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 SY C B under any homeomorphism between B 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 X a continuous map We let X Uy denote the disjoint union of X and o quotiented out by the equivalence relation that each point s a is identified with f s X We refer to this operation by saying that A USER S GUIDE TO DISCRETE MORSE THEORY 3 X Uso 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 ao That is the entire boundary of o must be glue
32. ence 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 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 1 Gi i A triangulation of the real projective plane ii A discrete gradient vector field on P A USER S GUIDE TO DISCRETE MORSE THEORY 17 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 if 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 poin
33. et 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 complex 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 8 1 aP AP aP AP al BPD at such that for each i 0 r a lt 8 V and i gt aiz1 a We say such a path is a non trivial closed path if r gt 0 and ao amp r 1 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 39 1 is a V path if and only if a lt Bi gt ais for each i 0 1 r and a0 2 f b gt Flar 2 F81 gt gt f gt Flara 16 ROBIN FORMAN That is the gradient paths of f are precisely those continuous sequences of simplices along whic
34. ex 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 Mn 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 V z is a gradient vector field Let y a oe aP denote a Vjo path Then ao must be the tail of an arrow i e the smaller graph of some pair in Vj2 with Go being the head of the arrow i e Bo amp o 1 2 The simplex a is a codimension one face of 6o other than ao Thus a corresponds to a graph of the form ag 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 Vio i e the larger graph of some pair in Viz which implies that y cannot be continued to a longer Vj2 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 then the vertices 3 4 5 in order Let A USER S GUIDE TO DISCRETE MORSE THEORY 21 Y Qo 39 1 denote a V path In particular ag and Gy must be paired in V The reader can check that if j 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 p
35. extended L homology J Funct Anal 168 1999 pp 84 110 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 Algebraic 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
36. f topological spaces for which it was rather easy to define homology and cohomology i e in terms the simplicial 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 cg 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 each endowed with an orientation The following is one of the fundamental results in the theory of CW complexes Theorem 1 6 There are boundary maps Og Cal X Z gt Ca_ 1 X Z for each d so that Oj 4007 0 A USER S GUIDE TO DISCRETE MORSE THEORY 7 and such that the resulting differential complex iO OCD PC eT SS OCT 50 calculates the homology of X That is if we define Ker 0q Hg C o fa then for each d Ha C 0 Ha X Z where Ha X Z denotes the singular homology of X 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
37. 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 0 gt a f 8 lt fla lt 1 and 2 0 lt a f y f 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 1 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 5 5 2 4 2 4 1 3 1 3 0 0 i 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 10 ROBIN FORMAN Definition 2 3 A simplex a is critical if 1 G gt a f 8 lt fla 0 and 2 y lt a fy f a 0 For example Figure 2 2 ii the vertex f 0 and the edge f 1 5 are criti
38. g 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 to e and with the illustrated orientation for t both induce the chosen orientation on e so that O t 2e Therefore the homology of the real projective plane can be calculated from the following differential complex x2 gt 0 gt S SL EG 0 Thus we see that 1 2 A gradient vector field on the real projective plane Figure 7 4 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 un fortunately have to be defined only cursorily or not at all So far we have not placed any restrictions on the simplicial complexes under consideration The main idea of this section is that 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 ball if K and the standard d simplex ig have isomorphic subdivisions A simplicial complex K is
39. h 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 illustrate 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 h
40. his new Morse function while the criticality of all other simplices is unchanged This completes the proof 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 3 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 28 ROBIN FORMAN 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 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 treatment of the content of this section The problem we study is a topological version of a standard type of search prob lem The
41. ite orientation With this differential the complex 7 1 computes the homology of K where A proof of this theorem appears in Section 8 of 10 We refer to the complex 7 1 with the differential 7 2 as the Morse complex it goes by many different names in the literature 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 O cell one 1 cell and one 2 cell Here we will see how Morse Theory can distinguish between the spaces which have such a CW de composition In Figure 7 4 we redraw the gradient vector field and indicate a chosen orientation on the critical edge e and the critical triangle t Let us now calculate the boundary map in the Morse complex To calculate O e we must count all of the gradient paths from the boundary of e to v There are precisely 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 A USER S GUIDE TO DISCRETE MORSE THEORY 25 on the tail of e adding these two paths with their correspondin
42. lex 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 K 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 A USER S GUIDE TO DISCRETE MORSE THEORY 33 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 not 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 m
43. lities Theorem 2 11 I The Weak Morse Inequalities i For each p 0 1 2 n where n is the dimension of K Mp Dy ii mo m Ma lt 1 My bo b bg 1 bn x K II The Strong Morse Inequalities For each p 0 1 2 n n 1 Mp Miger 1 P mo bp bp 1 1 Pbo 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 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 indicate 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 e
44. of the Hasse diagram of K then K collapses onto a vertex so that in particular K is contractible A USER S GUIDE TO DISCRETE MORSE THEORY 23 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 decompo 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 Mp C Cp 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 critical p simplices then we obviously have Mp Z 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 1 for each d so that Oa_1 0 Og 0 and such that the resulting differential complex 7 1 I eG calculates the homology of X That is if we define Ker Heys Im 0q 1 then for each d 7 Ha M 0 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 0 This requires a closer look at of the notion of a gradient path Let a and
45. orial d sphere 9 CANCELLING 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 88 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 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 f
46. otopy and its quantization in Geometric Topology Athens GA 1993 AMS IP Stud Adv Math21 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 Grenzgebiete 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 Sn and some related CW compleres Proc Amer Math Soc 128 2000 pp 2253 2259 Topology of spaces of hyperbolic polynomials with multiple roots to appear in Israel J Math W Kihnel Triangulations of Manifolds with few Vertices in Advances in Differential Geometry and Topology World Sci Publishing N J 1990 pp 59 114 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 A USER S GUIDE TO DISCRETE MORSE THEORY 35 S Linusson and J Shareshian Complexes of t colorable graphs preprint 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
47. rs in K is at least dim F 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 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 have 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 sequence of integers n a nola lt nila lt lt n a 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 1 D p aP is a V path then ao Go is in V which means that ao and are not distinguished until the n 1 question Thus n Go nolao lt n ao Kri lt
48. ry 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 of 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 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 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 b
49. se 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 X is the result of attaching a 2 cell to Xo In this case X is a 2 sphere and X Xo is the result of attaching a 1 cell to X The attaching map is a map of S into Since S is connected i e 7 S 0 all such maps are homotopic to a constant map Taking the attaching map to be a constant map yields that X St 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 X be a CW decomposition of a finite CW complex X Then X is homotopy equivalent to a finite CW decomposition with precisely the same number of cells of each dimension 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 o
50. t is discussed further in Section 7 where we will return to this example of the triangulated projective plane 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 K 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 E 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 Gi C G2 E Gn if Go E P then Gi 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 6 for any fixed 6 graphs which are not connected graphs which are not i connected for any fixed i 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
51. this section we present a technique discrete Morse 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 modifica tions 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 IVCK 2 fac K and GCathen Ge 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 a and we will use the notation a lt 8 or B gt a to indicate that a is a proper subset of 8 thinking of a and 8 as subsets of V and say that a is a A USER S GUIDE TO DISCRETE MORSE THEORY 9 face of 8 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 indicate how some of our conclusions can be strengthened in the case that the complexes are assumed to have additional structure A discrete Morse function on K is a
52. unctions Moreover in the combinatorial setting the proof is much simpler The main result is that if a and 3 are 2 critical simplices and if there is exactly 1 gradient path from the boundary of 8 to a then a and 8 can be cancelled More precisely A USER S GUIDE TO DISCRETE MORSE THEORY 27 Theorem 9 1 Suppose f is a discrete Morse function on M such that BP 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 that a and B 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 p 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 3 to a then we can reverse the gradient vector field along this path replacing the figure by the vector field shown in the bottom drawing in Figure 9 2 RIS 2S Cancelling critical points Figure 9 2 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 a and 8 are not critical for t
53. y 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 K C Ky are simplicial complexes and K has exactly two simplices a and that are not in Ko where 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 simplicial collapse If one can transform a simplicial complex K into a subcomplex K by simplicial collapses then we say that K collapses to K2 and we indicate this by K N Ko Figure 2 10 shows a 2 dimensional simplex collapsing to one of its vertices 12 ROBIN FORMAN N A simplicial collapse Figure 2 9 ASLAN A 2 simplex 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 category 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
54. y 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 X X The space Xo must be the 0 cell and X Xj 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 A USER S GUIDE TO DISCRETE MORSE THEORY 5 Xo is the 0 cell and for each 7 1 2 n the space X is the result of attaching a d cell to X _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 X is homotopic to a constant map since mq 1 X1 ma 1 S 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 S A 4 The wedge of a collection of topological spaces is the space resulting from choosing a point in each sp
Download Pdf Manuals
Related Search