# Discrete Morse function from smooth one

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$?

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$.

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?

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.

I'm also not worried about pathologies: $f$ has finitely many critical points, and $M$ is compact.

UPDATE 2: Thanks for the comments everyone! I will now go to think some more.

-
Niles: You should specify which form of discrete Morse theory you are interested in, since there are at least 2: Bestvina-Brady's and Forman's. –  Misha Oct 18 '12 at 19:13
Could you perhaps tell us something about what you'd like to use the output discrete Morse function for, what you'd like to do with it? It might help people find a more useful answer for you. –  Ryan Budney Oct 18 '12 at 19:23
Oh, I wasn't aware of Bestvina-Brady -- thanks for the pointer. I was thinking of Forman, but a cursory look indicates that Bestvina-Brady may work for me. –  Niles Oct 18 '12 at 19:28
My paper "On optimizing discrete Morse functions" has a result on how to deduce information about cell incidences among critical cells from the data from a larger triangulation and a discrete Morse function having these as its critical cells. If you really have software to do that, maybe the paper will help a little bit too. –  Patricia Hersh Oct 18 '12 at 20:33
Maybe the paper of Bruno Benedetti found at arxiv.org/pdf/1010.0548v4.pdf would be of interest to you. –  John Shareshian Oct 19 '12 at 1:25

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: there is no standard way. However, you should be able to compute the homology you desire as follows.

My impression is that you have three jobs, in chronological order:

1. Construct a simplicial complex $X_M$ homologically faithful to $M$.
2. Construct a discrete Morse function $\mu:X_M \to \mathbb{R}$ which approximates $f$, and
3. Compute homology of everything in sight.

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 here 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$.

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 work 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$!

And finally, I have written software 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$.

All the best with your computations.

-
Thanks! These are indeed useful, although the Niyogi-Smale-Weinberger strategy pushes the question to estimating tau (e.g. via the second fundamental form) and to determining a uniform distribution on M. Also, "sampling the hell out of it" is problematic as the ambient dimension grows. It looks reasonable to give a local version of NSW, so that the sampling density doesn't have to be uniform over M. I don't suppose anyone has done this, have they? –  Niles Oct 19 '12 at 13:04
Niles: no one has done this yet, at least no one that I know of. –  Vidit Nanda Oct 19 '12 at 13:17

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.

Let me mention our strategy maybe you get lucky. In a recent paper 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

1. The critical points are the exactly barycenters of all the faces.
2. The Conley index of the barycenter of a critical face is a sphere of the same dimension as the face.
3. The Conley index of the barycenter of a non-critical face is homotopically trivial

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.

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.

As for associating a Morse-Forman function to a Morse function there are some recent results in this direction arXiv: 1010.0548 or arXiv: 0803.2616.

Remark. This in reply to your new question. There are as many stationary points as faces. The barycenter of each face is a stationary point. However, only few of these stationary points have nontrivial Conley index. I will refer to the other stationary points as ghosts, and the level sets containing ghosts as ghost levels.

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.

The process of crossing of ghost level does not even change the simple homotopy 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$.

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.

-
Thanks! These look promising. Do you think one could finish your program with an assumption that nothing too wild happens near critical points -- maybe with some bounds on second or third derivatives of $f$? –  Niles Oct 18 '12 at 20:10
The problem you have in mind in its complete generality, and no additional assumption on $f$ seems difficult. Homology is after all a global object and at some point you need to extract some global information from somewhere. –  Liviu Nicolaescu Oct 18 '12 at 20:23
In your first point, do you mean to say that the critical points of the genuine flow are barycenters of the critical faces, or all faces? –  Vidit Nanda Oct 28 '12 at 5:01
I'll reply on my post since I do not have enough space on the comment section. –  Liviu Nicolaescu Oct 28 '12 at 13:35