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][3] denoising,^[4] and mesh compression.^[5]

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^[6] 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^[7] 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., whose 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, for instance, 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^[8] 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^[9] 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. Mischaikow, Konstantin; Nanda, Vidit. "Morse Theory for Filtrations and Efficient computation of Persistent Homology". Springer. Retrieved 3 August 2013.
4. U. Bauer, C. Lange, and M. Wardetzky: Optimal Topological Simplification of Discrete Functions on Surfaces
5. T Lewiner, H Lopez and G Tavares: Applications of Forman's discrete Morse theory to topological visualization and mesh compression
6. Mischaikow, Konstantin; Nanda, Vidit. "Morse Theory for Filtrations and Efficient computation of Persistent Homology". Springer. Retrieved 3 August 2013.
7. Forman, Robin: Morse Theory for Cell Complexes, Lemma 2.5
8. Forman, Robin: Morse Theory for Cell Complexes, Corollaries 3.5 and 3.6
9. 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