# Is there a discrete Cerf theory?

Towards the end of the 1990's, Robin Forman developed a discrete version of Morse theory, which concerns maps from a simplicial complex to $\mathbb{R}$ satisfying a combinatorial analogue to the condition that critical points be non-degenerate. The theory has proven quite useful in that it has allowed Morse theoretic arguments to be used in discrete settings, and it forms a part of computational topology.
My attention was recently drawn to the technique as a result of reading a preprint of Conant, Schneiderman, and Teichner. Therefore, this question might well be hopelessly naïve (it's also possible that it's open).

Is there a discrete version of Cerf Theory? Are there at least partial results in this direction? Conversely, is it known that no such theory can exist?

My motivation is that I would imagine that a discrete proof of Kirby's Theorem, among other results which use Cerf Theory, might prove quite valuable in quantum topology (I'd love such a result at my fingertips!). I know that this doesn't (yet?) exist, or I would surely have heard about it. Additionally, a topological "machine" can only be used by a computer if it requires only finite information.

-
Not an answer, just a random remark. There's another version of discrete Morse theory used in geometric group theory, especially by Mladen Bestvina (see his survey here : math.utah.edu/~bestvina/eprints/minicourse.pdf). It seems that a lot of people who are aware of Forman's work are not aware of Bestvina's, and vise-versa. Oddly enough, I've used Bestvina-style discrete Morse theory a lot, but I happen to inhabit Robin's old office and be currently sitting in his old chair =). –  Andy Putman Feb 25 '11 at 5:23
'Additionally, a topological "machine" can only be used by a computer if it requires only finite information.' Would that still be true of a quantum computer? (I realize this isn't helpful, but it came to mind.) –  Greg Friedman Feb 25 '11 at 6:27
@Daniel and Andy: Another random remark: the discrete Morse theory was invented first by Ken Brown and used by Ken Brown and Ross Geoghegan in their 1984 paper in Inventiones about homology of the R. Thompson group $F$, and later by Brown in "The geometry of rewriting systems: A proof of the Anick -- Groves --Squier theorem", 1989. Essentially it is the same version of Morse theory indepently rediscovered later by Bestvina and Forman. –  Mark Sapir Feb 25 '11 at 13:14
I have always wanted to understand the paper "Cerf theory for graphs" by Hatcher and Vogtmann. math.cornell.edu/~hatcher/Papers/Cerfgraph.pdf –  Sam Nead Feb 25 '11 at 14:25

The following simple statement can be made about straight-line homotopies of discrete Morse functions.

A discrete Morse function $f$ with gradient vector field $V_f$ is called flat if $f(\sigma) = f(\tau)$ whenever $(\sigma,\tau) \in V_f$. (For any discrete Morse function there is an equivalent flat function, i.e., having the same sublevel complexes). This definition is also due to Forman (Witten–Morse theory for cell complexes).

Now let $f$ and $g$ be two flat Morse functions with gradient vector fields $V_f$ and $V_g$, respectively. Then $f_t=(1-t)f+tg$ is a flat Morse function with gradient vector field $V=V_f\cap V_g$ for every $t$ with $0\leq t\leq 1$. The proof is straightforward from the definitions.

This means, intuitively, that in the described scenario all changes in the critical set of $f_t$ happen only at $t=0$ and $t=1$. This is due to the use of flat Morse functions. For general discrete Morse functions $f$ and $g$, the function $f_t$ is not always a discrete Morse function, and this can happen not only at discrete values of $t$ but on whole intervals.

-
Start with a simplicial complex $\Delta$ and let $M(\Delta)$ be the set of all possible discrete Morse functions $\mu:\Delta \to \mathbb{R}$. Note that two such functions $\mu$ and $\mu'$ are considered equivalent if they induce the same discrete vector field. We can assume without loss of generality that $M(\Delta)$ has been quotiented by this obvious equivalence relation: $\mu \sim \mu'$ if and only if $\mu(\sigma) > \mu(\tau) \leftrightarrow \mu'(\sigma) > \mu'(\tau)$ for each facet relation $\sigma \prec \tau$ in $\Delta$. Thus, we may as well assume that $M(\Delta)$ is simply the collection of acyclic partial matchings on $\Delta$.
It turns out that $M(\Delta)$ itself can be canonically endowed with the structure of a simplicial complex. Each facet relation $\sigma \prec \tau$ of $\Delta$ is a vertex, and a $D$-dimensional simplex spans $D+1$ facet relations $\sigma_d \prec \tau_d$ if and only if pairing $\sigma_d$ to $\tau_d$ for each $1 \leq d \leq D+1$ creates an acyclic matching on $\Delta$.
The reason that $M(\Delta)$ is interesting with regards to your question, is that each simplex corresponds to a unique acyclic matching on $\Delta$. So, among other things you can try, just impose a Morse function $f:M(\Delta) \to \mathbb{R}$ on $M(\Delta)$ itself so that the two acyclic matchings you wish to compare are critical cells. Now each gradient path between these critical cells corresponds to a "deformation" from one to the other in the set of acyclic matchings on $\Delta$.