Discrete Morse theory

Discrete Morse theory is a combinatorial adaptation of Morse theory developed by Robin Forman. The theory has various practical applications in diverse fields of applied mathematics and computer science, such as configuration spaces,^[1] homology computation,^[2] denoising,^[3] and mesh compression.^[4]

Notation regarding CW complexes

Let $\mathcal{X}$ be a CW complex. Define the incidence function $\kappa:\mathcal{X} \times \mathcal{X} \to \mathbb{Z}$ in the following way: given two cells $\sigma$ and $\tau$ in $\mathcal{X}$, let $\kappa(\sigma,~\tau)$ be the degree of the attaching map from the boundary of $\sigma$ to $\tau$. The boundary operator $\partial$ on $\mathcal{X}$ is defined by

$\partial(\sigma) = \sum_{\tau \in \mathcal{X}}\kappa(\sigma,\tau)\tau$

It is a defining property of boundary operators that $\partial\circ\partial \equiv 0$. In more axiomatic definitions^[5] one can find the requirement that $\forall \sigma,\tau^{\prime} \in \mathcal{X}$

$\sum_{\tau \in \mathcal{X}} \kappa(\sigma,\tau) \kappa(\tau,\tau^{\prime}) = 0$

which is a corollary of the above definition of the boundary operator and the requirement that $\partial\circ\partial \equiv 0$.

Discrete Morse functions

A real-valued function $\mu:\mathcal{X} \to \mathbb{R}$ is a discrete Morse function if it satisfies the following two properties:

1. For any cell $\sigma \in \mathcal{X}$, the number of cells $\tau \in \mathcal{X}$ in the boundary of $\sigma$ which satisfy $\mu(\sigma) \leq \mu(\tau)$ is at most one.
2. For any cell $\sigma \in \mathcal{X}$, the number of cells $\tau \in \mathcal{X}$ containing $\sigma$ in their boundary which satisfy $\mu(\sigma) \geq \mu(\tau)$ is at most one.

It can be shown^[6] that the cardinalities in the two conditions cannot both be one simultaneously for a fixed cell $\sigma$, provided that $\mathcal{X}$ is a regular CW complex. In this case, each cell $\sigma \in \mathcal{X}$ can be paired with at most one exceptional cell $\tau \in \mathcal{X}$: either a boundary cell with larger $\mu$ value, or a co-boundary cell with smaller $\mu$ value. The cells which have no pairs, i.e., their function values are strictly higher than their boundary cells and strictly lower than their co-boundary cells are called critical cells. Thus, a discrete Morse function partitions the CW complex into three distinct cell collections: $\mathcal{X} = \mathcal{A} \sqcup \mathcal{K} \sqcup \mathcal{Q}$, where:

1. $\mathcal{A}$ denotes the critical cells which are unpaired,
2. $\mathcal{K}$ denotes cells which are paired with boundary cells, and
3. $\mathcal{Q}$ denotes cells which are paired with co-boundary cells.

By construction, there is a bijection of sets between $k$-dimensional cells in $\mathcal{K}$ and the $(k-1)$-dimensional cells in $\mathcal{Q}$, which can be denoted by $p^k:\mathcal{K}^k \to \mathcal{Q}^{k-1}$ for each natural number $k$. It is an additional technical requirement that for each $K \in \mathcal{K}^k$, the degree of the attaching map from the boundary of $K$ to its paired cell $p^k(K) \in \mathcal{Q}$ is a unit in the underlying ring of $\mathcal{X}$. For instance, over the integers $\mathbb{Z}$, the only allowed values are $\pm 1$. This technical requirement is guaranteed when one assumes that $\mathcal{X}$ is a regular CW complex over $\mathbb{Z}$.

The fundamental result of discrete Morse theory establishes that the CW complex $\mathcal{X}$ is isomorphic on the level of homology to a new complex $\mathcal{A}$ consisting of only the critical cells. The paired cells in $\mathcal{K}$ and $\mathcal{Q}$ describe gradient paths between adjacent critical cells which can be used to obtain the boundary operator on $\mathcal{A}$. Some details of this construction are provided in the next section.

The Morse complex

A gradient path is a sequence of paired cells

$\rho = (Q_1, K_1, Q_2, K_2, \ldots, Q_M, K_M)$

satisfying $Q_m = p(K_m)$ and $\kappa(K_m,~Q_{m+1}) \neq 0$. The index of this gradient path is defined to be the integer

$\nu(\rho) = \frac{\sum_{m=1}^{M-1}-\kappa(K_m,Q_{m+1})}{\sum_{m=1}^{M}\kappa(K_m,Q_m)}$.

The division here makes sense because the incidence between paired cells must be $\pm 1$. Note that by construction, the values of the discrete Morse function $\mu$ must decrease across $\rho$. The path $\rho$ is said to connect two critical cells $A,A' \in \mathcal{A}$ if $\kappa(A,Q_1) \neq 0 \neq \kappa(K_M,A')$. This relationship may be expressed as $A \stackrel{\rho}{\to} A'$. The multiplicity of this connection is defined to be the integer $m(\rho) = \kappa(A,Q_1)\cdot\nu(\rho)\cdot\kappa(K_M,A)$. Finally, the Morse boundary operator on the critical cells $\mathcal{A}$ is defined by

$\Delta(A) = \kappa(A,A') + \sum_{A \stackrel{\rho}{\to} A'}m(\rho) A'$

where the sum is taken over all gradient path connections from $A$ to $A'$.

Basic Results

Many of the familiar results from continuous Morse theory apply in the discrete setting.

The Morse Inequalities

Let $\mathcal{A}$ be a Morse complex associated to the CW complex $\mathcal{X}$. The number $m_q = |\mathcal{A}_q|$ of $q$-cells in $\mathcal{A}$ is called the $q^{th}$ Morse number. Let $\beta_q$ denote the $q^{th}$ Betti number of $\mathcal{X}$. Then, for any $N > 0$, the following inequalities^[7] hold

$m_N \geq \beta_N$, and

$m_N - m_{N-1} + \ldots \pm m_0 \geq \beta_N - \beta_{N-1} + \ldots \pm \beta_0$

Moreover, the Euler characteristic $\chi(\mathcal{X})$ of $\mathcal{X}$ satisfies

$\chi(\mathcal{X}) = m_0 - m_1 + \ldots \pm m_{\dim \mathcal{X}}$

Discrete Morse Homology and Homotopy Type

Let $\mathcal{X}$ be a regular CW complex with boundary operator $\partial$ and a discrete Morse function $\mu:\mathcal{X} \to \mathbb{R}$. Let $\mathcal{A}$ be the associated Morse complex with Morse boundary operator $\Delta$. Then, there is an isomorphism^[8] of Homology groups as well as homotopy groups.

$H_*(\mathcal{X},\partial) \simeq H_*(\mathcal{A},\Delta)$

See also

• Digital Morse theory
• Stratified Morse theory
• Shape analysis
• Topological combinatorics
• Discrete differential geometry

References

1. F. Mori and M. Salvetti: (Discrete) Morse theory for Configuration spaces
2. Perseus: the Persistent Homology software.
3. U. Bauer, C. Lange, and M. Wardetzky: Optimal Topological Simplification of Discrete Functions on Surfaces
4. T Lewiner, H Lopez and G Tavares: Applications of Forman's discrete Morse theory to topological visualization and mesh compression
5. Mischaikow, Konstantin; Nanda, Vidit. "Morse Theory for Filtrations and Efficient computation of Persistent Homology". Springer. Retrieved 3 August 2013.
6. Forman, Robin: Morse Theory for Cell Complexes, Lemma 2.5
7. Forman, Robin: Morse Theory for Cell Complexes, Corollaries 3.5 and 3.6
8. Forman, Robin: Morse Theory for Cell Complexes, Theorem 7.3

• Robin Forman (2002) A User's Guide to Discrete Morse Theory, Séminare Lotharinen de Combinatore 48
• Dmitry Kozlov (2007). Combinatorial Algebraic Topology. Springer. ISBN 978-3540719618.
• Jakob Jonsson (2007). Simplicial Complexes of Graphs. Springer. ISBN 978-3540758587.
• Peter Orlik, Volkmar Welker (2007). Algebraic Combinatorics: Lectures at a Summer School In Nordfjordeid. Springer. ISBN 978-3540683759.
• nLab Article