A User's Guide to Discrete Morse Theory

Full paper: https://webhomes.maths.ed.ac.uk/~v1ranick/papers/forman1.pdf

---

CW Complexes

The author works in the realm of CW complexes to keep the main results as general as possible. Below is a brief recap of CW complexes, more information can be found at Cell Complexes.

Let $B^d=\{x\in {\mathbb{R}}^d:|x|\le 1\}$ be the closed unit ball in $d$-dimensional Euclidean space. The boundary of $B^d$ is the unit $(d-1)$-sphere

$$\partial B^d=S^{d-1}=\{x\in {\mathbb{R}}^d:|x|=1\}.$$

Define a $d$-cell as a topological space that is homeomorphic to $B^d$. Let $X$ be a topological space, $\sigma$ a $d$-cell and $f:\partial \sigma \cong S^{d-1}\to X$ a continuous map (more specifically the domain is the subset that is homeomorphic to $S^{d-1}$). Denote by $X{\cup }_f\sigma$ the space $X\bigsqcup \sigma /\sim$ where $\sim$ is the equivalence relation given by identifying each $s\in S^{d-1}$ with $f(s)\in X$. Intuitively, we are taking a $d$-cell and gluing the entire boundary to $X$.

A finite CW complex is the finite nested sequence

$$\varnothing \subset X_0\subset X_1\subset \cdots \subset X_n=X$$

where each $X_i$ is the result of attaching a cell to $X_{i-1}$. Let $C_d(X,\mathbb{Z})$ denote the free abelian group generated by the $d$-cells of $X$. Then there are boundary maps

$${\partial }_d:C_d(X,\mathbb{Z})\to C_{d-1}(X,\mathbb{Z})$$

such that ${\partial }^2=0$ and the exact sequence

$$0\to C_n(X,\mathbb{Z})\stackrel{{\partial }_n}{\to }{C}_{n-1}(X,\mathbb{Z})\stackrel{{\partial }_{n-1}}{\to }\cdots \stackrel{{\partial }_1}{\to }{C}_0(X,\mathbb{Z})\to 0$$

gives the homology of $X$, i.e.,

$$H_d(X,\mathbb{Z})\cong \text{Ker}({\partial }_d)/\text{Im}({\partial }_{d+1}).$$

The Strong Morse Inequalities

Let $c_d$ be the number of $d$-cells of $X$. Denote the Betti numbers of $X$ by ${\beta }_d=\text{dim}(H_d(X,\mathbb{Z}))$. Then for any $d=0,1,2,\dots$ $c_d-c_{d-1}+c_{d-2}-\cdots +(-1{)}^d{c}_0\ge b_d-b_{d-1}+b_{d-2}-\cdots +(-1{)}^d{b}_0.$

Consequently, we get the Weak Morse Inequalities:

$$c_d\ge {\beta }_d,\forall d=0,1,2,\dots$$

The Basics of Discrete Morse Theory

Recall that a finite simplicial complex is given by a finite set of vertices $V$ along with a set of subsets $K$ of $V$ such that

1. $V\subseteq K$
2. If $\alpha \in K$ and $\beta \subseteq \alpha$ then $\beta \in K$.

We call the elements of $K$ simplices and $K$ the simiplicial complex. A $p$-dimensional simplex, $\alpha$, has $p+1$ vertices and we denote its dimension by ${\alpha }^{(p)}$. We say that $\alpha$ is a face of $\beta$, denoted $\alpha \le \beta$, if $\alpha \subseteq \beta$.

Discrete Morse Fucntion

A function $f:K\to \mathbb{R}$ is a discrete Morse function if for every ${\alpha }^{(p)}\in K$, the following two properties hold:

1. $\#\{{\beta }^{(p+1)}>\alpha :f(\beta )\le f(\alpha )\}\le 1$; and
2. $\#\{{\gamma }^{(p-1)}<\alpha :f(\gamma )\ge f(\alpha )\}\le 1$.

We say a simplex ${\alpha }^{(p)}\in K$ is critical if both of these sets are empty, i.e.,

1. $\#\{{\beta }^{(p+1)}>\alpha :f(\beta )\le f(\alpha )\}=0$; and
2. $\#\{{\gamma }^{(p-1)}<\alpha :f(\gamma )\ge f(\alpha )\}=0$.

One may show, that for any simplex ${\alpha }^{(p)}\in K$, at least one of the critical properties must hold.

A discrete Morse function provides a way to build the simplicial complex by attaching simplices in the order prescribed by the function. More specifically, by defining $K(c)$ to be the subcomplex consisting of all simplices $\alpha$ of $K$ such that $f(\alpha )\le c$ along with all of their faces.

Lemma 2.6

If there are no critical simplices $\alpha$ with $f(\alpha )\in (a,b]$, then $M(b)$ is homotopy equivalent to $M(a)$.

In other words, the complex only changes when we add critical simplices. When we add non-critical simplices they collapse down to the same complex we had. This stems from a very general phenomenon. Suppose that $K_2\subset K_1$ are both simplicial complexes differing by two simplices, $\alpha$ and $\beta$ where $\beta$ is a free face of $\alpha$, i.e., a face that is not the face of any other simplex in $K_1$. Then one may deformation retract $K_1$ into $K_2$, hence $K_1$ and $K_2$ are homotopy equivalent. This is known as simplicial collapse and denoted $K_1\searrow K_2$.

Lemma 2.7

If there is a single critical simplex $\alpha$ with $f(\alpha )\in (a,b]$, then there is a map $F:S^{(d-1)}\to M(a)$, where $d$ is the dimension of $\alpha$, such that $M(b)$ is homotopy equivalent to $M(a){\cup }_F{B}^d$.

That is, when we add a critical simplex to the complex, we get a new structure, $M(b)$, formed by attaching a $d$-cell to the current complex, $M(a)$.

Gradient Vector Fields

Noncritical simplices occur in pairs. If an edge $f^{-1}(1)$ is not critical because it has a vertex, $f^{-1}(2)$, of higher value, then it follows that $f^{-1}(2)$ is also not critical. Thus, we get a pairing, which we denote by an arrow $f^{-1}(2)\to f^{-1}(1)$. One may think of these arrows as pointing in the direction of simplicial collapse.

From this, we get that every simplex $\alpha$ satisfies exactly one of the following properties:

1. $\alpha$ is the tail of exactly one arrow
2. $\alpha$ is the head of exactly one arrow
3. $\alpha$ is neither the head nor tail of an arrow (in which case it is critical)

This results in the following definition:

Discrete Vector Field

A discrete vector field $V$ on $K$ is a collection of pairs $\{{\alpha }^{(p)}<{\beta }^{(p+1)}\}$ of simplices of $K$ such that each simplex is in at most one pair of $V$.

Given a discrete vector field $V$ on $K$, we form a $V$-path by a sequence of simplices

$${\alpha }_0^{(p)},{\beta }_0^{(p+1)},{\alpha }_1^{(p)},{\beta }_1^{(p+1)},\dots ,{\beta }_r^{(p+1)},{\alpha }_{r+1}^{(p)}$$

such that $\{{\alpha }_i<{\beta }_i\}\in V$ and ${\beta }_i>a_{i+1}\ne {\alpha }_i$. If ${\alpha }_0={\alpha }_{r+1}$, we call the path a non-trivial closed path.

Theorem 3.4

Let $V$ be a gradient vector field of a discrete Morse function $f$. Then a sequence of simplies is a $V$-path if and only if ${\alpha }_i<{\beta }_i>{\alpha }_{i+1}$ for each $i=0,1,\dots ,r$, and $f({\alpha }_0)\ge f({\beta }_0)>f({\alpha }_1)\ge f({\beta }_1)>\cdots \ge f({\beta }_r)>f({\alpha }_{r+1}).$

This result implies that 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.

A Combinatorial Point of View

Consider the Hasse diagram (without the $\varnothing$) of a complex $M$ and let $V$ be a discrete vector field. We modify the Hasse diagram as follows: if $\{\alpha <\beta \}\in V$ then flip the orientation of edge $\alpha \leftarrow \beta$ so that it goes from $\alpha \to \beta$. Then a $V$-path is simply a directed path in the modified Hasse diagram. Note, that not all directed paths form $V$-paths.

Thus, we may think of a discrete vector field as a partial matching of the Hasse diagram. Therefore, a discrete vector field is a gradient vector field if this partial matching is acyclic in our modified Hasse diagram.

Theorem 6.3

Let $V$ be an acyclic partial matching of the Hasse diagram of $K$ as described above. Let $u_p$ denote the number of unpaired $p$-simplices. Then $M$ is homotopy equivalent to a CW-complex with exactly $u_p$ cells of dimension $p$, for each $p\ge 0$.

As a special case, if $V$ is a complete matching then the complex $K$ is contractible.

The Morse Complex