Discrete Morse function from smooth one - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T23:13:25Z http://mathoverflow.net/feeds/question/110029 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/110029/discrete-morse-function-from-smooth-one Discrete Morse function from smooth one Niles 2012-10-18T18:02:27Z 2012-10-28T13:45:59Z <p>Suppose I have a smooth manifold $M$ and a smooth Morse function $f$ on $M$. Is there a standard way to replace $M$ with a cell complex and $f$ with a discrete Morse function such the resulting homology (via discrete Morse theory) is the same as that of $M$?</p> <p>My question is motivated by a situation where I know the critical points of $f$, but not how they are connected by gradient flow lines. So I am interested in a solution which doesn't depend on that information. I imagine something like the following: Triangulate so that every critical point of $f$ lies on a simplex of the appropriate dimension, then define a discrete vector field by [some process]. This vector field has no nontrivial closed paths [for some reason]. By [some observation], the resulting homology is isomorphic to that of $M$. </p> <p>For an expert in Morse theory, does this even sound plausible? Are there "well-known" methods or results which would fill in the gaps? Even better, does such a result exist somewhere already?</p> <hr> <p>UPDATE: Mainly I am interested in computing the homology of $M$ without having complete information about the gradient flow of $f$. In particular, I have a specific smooth function on $\mathbb{R}^9$ coming from some data analysis. I would like to find the homology of the region $M =$ { $f \le C$ }. I have a strategy for finding the critical points of $f$, but determining how they are connected by flow lines seems problematic. Converting to a discrete problem would, I hope, provide a way around this.</p> <p>I'm also not worried about pathologies: $f$ has finitely many critical points, and $M$ is compact.</p> <hr> <p>UPDATE 2: Thanks for the comments everyone! I will now go to think some more.</p> http://mathoverflow.net/questions/110029/discrete-morse-function-from-smooth-one/110039#110039 Answer by Liviu Nicolaescu for Discrete Morse function from smooth one Liviu Nicolaescu 2012-10-18T19:53:58Z 2012-10-28T13:45:59Z <p>World seems to be small. I have tried the approach you outlined with a former student of mine and we got stuck in the simplest case, the height function on a torus.The saddle point was (and is) a serious headache.</p> <p>Let me mention our strategy maybe you get lucky. In a recent <a href="http://www.nd.edu/~lnicolae/tameflow.pdf" rel="nofollow">paper</a> I showed that given any triangulated space together with a Morse-Forman function on it, there exists a genuine flow on this space with the following properties</p> <ol> <li>The critical points are the exactly barycenters of all the faces.</li> <li>The Conley index of the barycenter of a critical face is a sphere of the same dimension as the face.</li> <li>The Conley index of the barycenter of a non-critical face is homotopically trivial</li> </ol> <p>The flows are easily described and visualized and they belong to a class of flows I called tame. There examples of tame flows beyond the class generated by a Morse-Forman function and they are as well behaved. To get such flows on a triagulated space it suffices to label the vertices. The flow runs from the higher label to the lower label. We thought that using the Morse function for labeling would do the trick.</p> <p>Given a Morse function on a manifold one could envisage constructing such a flow by choosing a sufficiently fine triangulation and trying to guess how the gradient flow would behave on each face. Things get hairy near the critical points. However I still believe this approach has legs.</p> <p>As for associating a Morse-Forman function to a Morse function there are some recent results in this direction <a href="http://front.math.ucdavis.edu/1010.0548" rel="nofollow">arXiv: 1010.0548</a> or <a href="http://front.math.ucdavis.edu/0803.2616" rel="nofollow">arXiv: 0803.2616</a>.</p> <p><strong>Remark.</strong> This in reply to your new question. There are as many stationary points as faces. The barycenter of <em>each</em> face is a stationary point. However, only few of these stationary points have <em>nontrivial</em> Conley index. I will refer to the other stationary points as <em>ghosts</em>, and the level sets containing ghosts as <em>ghost levels</em>. </p> <p>The Conley index of a barycenter of a face is nontrivial if and only if that face is critical in the sense of Forman. In my paper mentioned in my answer I describe a general process (flip-flop) that generalizes the process of handle attachment. Crossing a ghost level does not change the homotopy type of the sublevel set.</p> <p>The process of crossing of ghost level does not even change the <em>simple homotopy</em> type. If $\lbrace f=c\rbrace$ is a ghost level, then $\lbrace f\leq c+\varepsilon\rbrace$ is simple homotopic to the space obtained from $\lbrace f\leq c-\varepsilon\rbrace$ by attaching a cone over a contractibe subset $B\subset \lbrace f=c-\varepsilon\rbrace$.</p> <p>The space $\lbrace f\leq c+\varepsilon \rbrace$ is $PL$ homeomorphic to the space obtained from $\lbrace f\leq c-\varepsilon\rbrace$ by a flip-flop which is essentially a blowdown followed by a blowup along clearly defined loci.</p> http://mathoverflow.net/questions/110029/discrete-morse-function-from-smooth-one/110068#110068 Answer by Vidit Nanda for Discrete Morse function from smooth one Vidit Nanda 2012-10-19T04:53:16Z 2012-10-19T12:36:52Z <p>This is a rapidly developing area, and there are many short-cuts if all you want to do is compute the homology of sub-level sets of $f$. To answer your main question, as Liviu has already mentioned: <strong>there is no standard way</strong>. However, you should be able to compute the homology you desire as follows.</p> <p>My impression is that you have three jobs, in chronological order:</p> <ol> <li>Construct a simplicial complex $X_M$ homologically faithful to $M$.</li> <li>Construct a discrete Morse function $\mu:X_M \to \mathbb{R}$ which approximates $f$, and</li> <li>Compute homology of everything in sight.</li> </ol> <p>First, the easiest way to build a simplicial approximation if you know your $M$ is to embed it in some suitable $\mathbb{R}^n$ and sample the hell out of it. Since you are working on data analysis, this should not be too drastic a step. Given a point sample $P$ coming from a submanifold of Euclidean space, for each radius $\epsilon$ you can construct a Cech complex of radius $\epsilon$ around $P$. Precise bounds on how many points $P$ should have and how large $\epsilon$ can be in order for the Cech complex to recover the homology of $M$ with high confidence are available in the work of Niyogi, Smale and Weinberger <a href="http://people.cs.uchicago.edu/~niyogi/papersps/NiySmaWeiHom.pdf" rel="nofollow">here</a> in the case when $P$ is uniformly sampled. These bounds are in terms of the injectivity radius of the embedding of $M$ into Euclidean space, and of course once these bounds are satisfied it doesn't hurt to add your known critical points to $P$. You have your homologically faithful Cech complex $X_M$.</p> <p>Next, for 2, you can easily infer a discrete Morse function on an entire simplicial complex just from knowing its values on the vertices using the <a href="http://ftp4.de.freesbie.org/pub/misc/EMIS/journals/EM/expmath/volumes/14/14.4/King.pdf" rel="nofollow">work</a> of King, Knudson and Mramor. You may be required to perturb $f$ slightly so that its restriction to $P$ is injective, but this is easy and generically true. You have $\mu$!</p> <p>And finally, I have written <a href="http://www.math.rutgers.edu/~vidit/perseus.html" rel="nofollow">software</a> to handle 3 if you already have a $\mu:X_M \to \mathbb{R}$: you can input a filtered simplicial complex and compute not just homology at each sub-level set of $\mu$ but the persistent homology across all level-sets in the case of field coefficients. Meaning, instead of just knowing the homology of the subcomplexes $X_M^c$ consisting of all simplices with $\mu$-value less than or equal to $c$, you also recover the morphism on homology groups induced by including $X_M^c$ into $X_M^d$ whenever $c \leq d$.</p> <p>All the best with your computations.</p>