Misplaced Pages

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, homology computation, denoising, mesh compression, and topological data analysis.

Notation regarding CW complexes

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

${\displaystyle \partial (\sigma )=\sum _{\tau \in {\mathcal {X}}}\kappa (\sigma ,\tau )\tau .}$

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

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

which is a consequence of the above definition of the boundary operator and the requirement that ${\displaystyle \partial \circ \partial \equiv 0}$.

Discrete Morse functions

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

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

It can be shown that the cardinalities in the two conditions cannot both be one simultaneously for a fixed cell ${\displaystyle \sigma }$, provided that ${\displaystyle {\mathcal {X}}}$ is a regular CW complex. In this case, each cell ${\displaystyle \sigma \in {\mathcal {X}}}$ can be paired with at most one exceptional cell ${\displaystyle \tau \in {\mathcal {X}}}$: either a boundary cell with larger ${\displaystyle \mu }$ value, or a co-boundary cell with smaller ${\displaystyle \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: ${\displaystyle {\mathcal {X}}={\mathcal {A}}\sqcup {\mathcal {K}}\sqcup {\mathcal {Q}}}$, where:

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

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

The fundamental result of discrete Morse theory establishes that the CW complex ${\displaystyle {\mathcal {X}}}$ is isomorphic on the level of homology to a new complex ${\displaystyle {\mathcal {A}}}$ consisting of only the critical cells. The paired cells in ${\displaystyle {\mathcal {K}}}$ and ${\displaystyle {\mathcal {Q}}}$ describe gradient paths between adjacent critical cells which can be used to obtain the boundary operator on ${\displaystyle {\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

${\displaystyle \rho =(Q_{1},K_{1},Q_{2},K_{2},\ldots ,Q_{M},K_{M})}$

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

${\displaystyle \nu (\rho )={\frac {\prod _{m=1}^{M-1}-\kappa (K_{m},Q_{m+1})}{\prod _{m=1}^{M}\kappa (K_{m},Q_{m})}}.}$

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

${\displaystyle \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 ${\displaystyle A}$ to ${\displaystyle A'}$.

Basic results

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

The Morse inequalities

Let ${\displaystyle {\mathcal {A}}}$ be a Morse complex associated to the CW complex ${\displaystyle {\mathcal {X}}}$. The number ${\displaystyle m_{q}=|{\mathcal {A}}_{q}|}$ of ${\displaystyle q}$-cells in ${\displaystyle {\mathcal {A}}}$ is called the ${\displaystyle q}$-th Morse number. Let ${\displaystyle \beta _{q}}$ denote the ${\displaystyle q}$-th Betti number of ${\displaystyle {\mathcal {X}}}$. Then, for any ${\displaystyle N>0}$, the following inequalities hold

${\displaystyle m_{N}\geq \beta _{N}}$, and

${\displaystyle m_{N}-m_{N-1}+\dots \pm m_{0}\geq \beta _{N}-\beta _{N-1}+\dots \pm \beta _{0}}$

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

${\displaystyle \chi ({\mathcal {X}})=m_{0}-m_{1}+\dots \pm m_{\dim {\mathcal {X}}}}$

Discrete Morse homology and homotopy type

Let ${\displaystyle {\mathcal {X}}}$ be a regular CW complex with boundary operator ${\displaystyle \partial }$ and a discrete Morse function ${\displaystyle \mu \colon {\mathcal {X}}\to \mathbb {R} }$. Let ${\displaystyle {\mathcal {A}}}$ be the associated Morse complex with Morse boundary operator ${\displaystyle \Delta }$. Then, there is an isomorphism of homology groups

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

and similarly for the homotopy groups.

Applications

Discrete Morse theory finds its application in molecular shape analysis, skeletonization of digital images/volumes, graph reconstruction from noisy data, denoising noisy point clouds and analysing lithic tools in archaeology.

See also

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

References

1. Mori, Francesca; Salvetti, Mario (2011), "(Discrete) Morse theory for Configuration spaces" (PDF), Mathematical Research Letters, 18 (1): 39–57, doi:10.4310/MRL.2011.v18.n1.a4, MR 2770581
2. Perseus: the Persistent Homology software.
3. Mischaikow, Konstantin; Nanda, Vidit (2013). "Morse Theory for Filtrations and Efficient computation of Persistent Homology". Discrete & Computational Geometry. 50 (2): 330–353. doi:10.1007/s00454-013-9529-6.
4. Bauer, Ulrich; Lange, Carsten; Wardetzky, Max (2012). "Optimal Topological Simplification of Discrete Functions on Surfaces". Discrete & Computational Geometry. 47 (2): 347–377. arXiv:1001.1269. doi:10.1007/s00454-011-9350-z.
5. Lewiner, T.; Lopes, H.; Tavares, G. (2004). "Applications of Forman's discrete Morse theory to topology visualization and mesh compression" (PDF). IEEE Transactions on Visualization and Computer Graphics. 10 (5): 499–508. doi:10.1109/TVCG.2004.18. PMID 15794132. S2CID 2185198. Archived from the original (PDF) on 2012-04-26.
6. "the Topology ToolKit". GitHub.io.
7. Mischaikow, Konstantin; Nanda, Vidit (2013). "Morse Theory for Filtrations and Efficient computation of Persistent Homology". Discrete & Computational Geometry. 50 (2): 330–353. doi:10.1007/s00454-013-9529-6.
8. Forman 1998, Lemma 2.5
9. Forman 1998, Corollaries 3.5 and 3.6
10. Forman 1998, Theorem 7.3
11. Cazals, F.; Chazal, F.; Lewiner, T. (2003). "Molecular shape analysis based upon the morse-smale complex and the connolly function". Proceedings of the nineteenth annual symposium on Computational geometry. ACM Press. pp. 351–360. doi:10.1145/777792.777845. ISBN 978-1-58113-663-0. S2CID 1570976.
12. Delgado-Friedrichs, Olaf; Robins, Vanessa; Sheppard, Adrian (March 2015). "Skeletonization and Partitioning of Digital Images Using Discrete Morse Theory". IEEE Transactions on Pattern Analysis and Machine Intelligence. 37 (3): 654–666. doi:10.1109/TPAMI.2014.2346172. hdl:1885/12873. ISSN 1939-3539. PMID 26353267. S2CID 7406197.
13. Dey, Tamal K.; Wang, Jiayuan; Wang, Yusu (2018). Speckmann, Bettina; Tóth, Csaba D. (eds.). Graph Reconstruction by Discrete Morse Theory. 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs). Vol. 99. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. pp. 31:1–31:15. doi:10.4230/LIPIcs.SoCG.2018.31. ISBN 978-3-95977-066-8. S2CID 3994099.
14. Mukherjee, Soham (2021-09-01). "Denoising with discrete Morse theory". The Visual Computer. 37 (9): 2883–94. doi:10.1007/s00371-021-02255-7. S2CID 237426675.
15. Bullenkamp, Jan Philipp; Linsel, Florian; Mara, Hubert (2022), "Lithic Feature Identification in 3D based on Discrete Morse Theory", Proceedings of Eurographics Workshop on Graphics and Cultural Heritage (GCH), Delft, Netherlands: Eurographics Association, pp. 55–58, doi:10.2312/VAST/VAST10/131-138, ISBN 9783038681786, ISSN 2312-6124, S2CID 17294591, retrieved 2022-10-05

• Forman, Robin (1998). "Morse theory for cell complexes" (PDF). Advances in Mathematics. 134 (1): 90–145. doi:10.1006/aima.1997.1650.
• Forman, Robin (2002). "A user's guide to discrete Morse theory" (PDF). Séminaire Lotharingien de Combinatoire. 48: Art. B48c, 35 pp. MR 1939695.
• Kozlov, Dmitry (2007). Combinatorial algebraic topology. Algorithms and Computation in Mathematics. Vol. 21. Springer. ISBN 978-3540719618. MR 2361455.
• Jonsson, Jakob (2007). Simplicial complexes of graphs. Springer. ISBN 978-3540758587.
• Orlik, Peter; Welker, Volkmar (2007). Algebraic Combinatorics: Lectures at a Summer School In Nordfjordeid. Universitext. Springer. doi:10.1007/978-3-540-68376-6. ISBN 978-3540683759. MR 2322081.
• "Discrete Morse theory". nLab.

• Combinatorics
• Morse theory
• Computational topology