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:

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

$\mathcal{A}$ denotes the critical cells which are unpaired,
$\mathcal{K}$ denotes cells which are paired with boundary cells, and
$\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)

References

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

This article is issued from Wikipedia - version of the Friday, November 06, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.