Discrete Morse theory

Discrete Morse theory is a combinatorial adaptation of Morse theory defined on finite CW complexes.

Notation regarding CW complexes

Let $\mathcal{X}$ be a CW complex. Define the incidence function $\kappa:\mathcal{X}^2 \to \mathbb{Z}$ in the following way: given two cells σ and τ in $\mathcal{X}$, $\kappa(\sigma,~\tau)$ equals the degree of the attaching map from the boundary of σ to τ. 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$.

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 σ 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 σ in their boundary which satisfy $\mu(\sigma) \geq \mu(\tau)$ is at most one.

It can be shown^[1] that both conditions can not hold simultaneously for a fixed cell σ 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 μ value, or a co-boundary cell with smaller μ 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 $\rho = (Q_1, K_1, Q_2, K_2, \ldots, Q_M, K_M)$ is a sequence of cell pairs $K_m,~Q_m = p(K_m)$ so that $\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 μ must decrease across ρ. The path ρ 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) = \sum_{A \stackrel{\rho}{\to} A'}m(\rho) A'$

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

See also

• Digital Morse theory
• Stratified Morse theory
• Piece-wise linear Morse theory
• Shape analysis
• Topological combinatorics
• Discrete differential geometry

References

1. ^ Forman, Robin: Morse Theory for Cell Complexes, Lemma 2.5

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