Discrete Morse theory

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

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 ^[8] 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 ^[9] 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 ^[10] 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 ^[11] 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, ^[12] skeletonization of digital images/volumes, ^[13] graph reconstruction from noisy data, ^[14] denoising noisy point clouds ^[15] and analysing lithic tools in archaeology. ^[16]

See also

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

References

1. Brown, Kenneth S. (1992). "The Geometry of Rewriting Systems: A Proof of the Anick-Groves-Squier Theorem". Algorithms and Classification in Combinatorial Group Theory. Mathematical Sciences Research Institute Publications. Vol. 23. New York, NY: Springer New York. pp. 137–163. doi:10.1007/978-1-4613-9730-4_6. ISBN   978-1-4613-9732-8.
2. 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
3. Perseus: the Persistent Homology software.
4. 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 .
5. 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 .
6. 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. Bibcode:2004ITVCG..10..499L. doi:10.1109/TVCG.2004.18. PMID   15794132. S2CID   2185198. Archived from the original (PDF) on 2012-04-26.
7. "the Topology ToolKit". GitHub.io.
8. 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 .
9. Forman 1998 , Lemma 2.5
10. Forman 1998 , Corollaries 3.5 and 3.6
11. Forman 1998 , Theorem 7.3
12. 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.
13. 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. Bibcode:2015ITPAM..37..654D. doi:10.1109/TPAMI.2014.2346172. hdl: 1885/12873 . ISSN   1939-3539. PMID   26353267. S2CID   7406197.
14. 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.
15. 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.
16. 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.