Discrete Morse theory

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

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

It is a defining property of boundary operators that $\backslash partial\backslash circ\backslash partial\; \backslash equiv\; 0$. In more axiomatic definitions{{cite journal|last1=Mischaikow|first1=Konstantin|last2=Nanda|first2=Vidit|title=Morse Theory for Filtrations and Efficient computation of Persistent Homology|journal=Discrete & Computational Geometry|volume=50|issue=2|pages=330–353|doi=10.1007/s00454-013-9529-6|year=2013|doi-access=free}} one can find the requirement that $\backslash forall\; \backslash sigma,\backslash tau^\{\backslash prime\}\; \backslash in\; \backslash mathcal\{X\}$

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

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

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

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

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

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

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

The fundamental result of discrete Morse theory establishes that the CW complex $\backslash mathcal\{X\}$ is isomorphic on the level of homology to a new complex $\backslash mathcal\{A\}$ consisting of only the critical cells. The paired cells in $\backslash mathcal\{K\}$ and $\backslash mathcal\{Q\}$ describe gradient paths between adjacent critical cells which can be used to obtain the boundary operator on $\backslash mathcal\{A\}$. Some details of this construction are provided in the next section.

A gradient path is a sequence of paired cells

:$\backslash rho\; =\; (Q\_1,\; K\_1,\; Q\_2,\; K\_2,\; \backslash ldots,\; Q\_M,\; K\_M)$

satisfying $Q\_m\; =\; p(K\_m)$ and $\backslash kappa(K\_m,~Q\_\{m+1\})\; \backslash neq\; 0$. The index of this gradient path is defined to be the integer

:$\backslash nu(\backslash rho)\; =\; \backslash frac\{\backslash prod\_\{m=1\}^\{M-1\}-\backslash kappa(K\_m,Q\_\{m+1\})\}\{\backslash prod\_\{m=1\}^\{M\}\backslash kappa(K\_m,Q\_m)\}.$

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

:$\backslash Delta(A)\; =\; \backslash kappa(A,A\text{'})\; +\; \backslash sum\_\{A\; \backslash stackrel\{\backslash rho\}\{\backslash to\}\; A\text{'}\}m(\backslash rho)\; A\text{'}$

where the sum is taken over all gradient path connections from $A$ to $A\text{'}$.

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

Let $\backslash mathcal\{A\}$ be a Morse complex associated to the CW complex $\backslash mathcal\{X\}$. The number $m\_q\; =\; |\backslash mathcal\{A\}\_q|$ of $q$-cells in $\backslash mathcal\{A\}$ is called the $q$-th Morse number. Let $\backslash beta\_q$ denote the $q$-th Betti number of $\backslash mathcal\{X\}$. Then, for any $N\; >\; 0$, the following inequalities{{harvnb|Forman|1998|loc=Corollaries 3.5 and 3.6}} hold

:$m\_N\; \backslash geq\; \backslash beta\_N$, and

:$m\_N\; -\; m\_\{N-1\}\; +\; \backslash dots\; \backslash pm\; m\_0\; \backslash geq\; \backslash beta\_N\; -\; \backslash beta\_\{N-1\}\; +\; \backslash dots\; \backslash pm\; \backslash beta\_0$

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

:$\backslash chi(\backslash mathcal\{X\})\; =\; m\_0\; -\; m\_1\; +\; \backslash dots\; \backslash pm\; m\_\{\backslash dim\; \backslash mathcal\{X\}\}$

Let $\backslash mathcal\{X\}$ be a regular CW complex with boundary operator $\backslash partial$ and a discrete Morse function $\backslash mu\backslash colon\backslash mathcal\{X\}\; \backslash to\; \backslash mathbb\{R\}$. Let $\backslash mathcal\{A\}$ be the associated Morse complex with Morse boundary operator $\backslash Delta$. Then, there is an isomorphism{{harvnb|Forman|1998|loc=Theorem 7.3}} of homology groups

:$H\_*(\backslash mathcal\{X\},\backslash partial)\; \backslash simeq\; H\_*(\backslash mathcal\{A\},\backslash Delta),$

and similarly for the homotopy groups.

Discrete Morse theory finds its application in molecular shape analysis,{{Cite book |last1=Cazals |first1=F. |last2=Chazal |first2=F. |last3=Lewiner |first3=T. |title=Proceedings of the nineteenth annual symposium on Computational geometry |chapter=Molecular shape analysis based upon the morse-smale complex and the connolly function |date=2003 |chapter-url=http://portal.acm.org/citation.cfm?doid=777792.777845 |publisher=ACM Press |pages=351–360 |doi=10.1145/777792.777845 |isbn=978-1-58113-663-0|s2cid=1570976 }} skeletonization of digital images/volumes,{{Cite journal |last1=Delgado-Friedrichs |first1=Olaf |last2=Robins |first2=Vanessa |last3=Sheppard |first3=Adrian |date=March 2015 |title=Skeletonization and Partitioning of Digital Images Using Discrete Morse Theory |url=https://ieeexplore.ieee.org/document/6873268 |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence |volume=37 |issue=3 |pages=654–666 |doi=10.1109/TPAMI.2014.2346172 |pmid=26353267 |hdl=1885/12873 |s2cid=7406197 |issn=1939-3539|hdl-access=free }} graph reconstruction from noisy data,{{Cite conference |last1=Dey |first1=Tamal K. |last2=Wang |first2=Jiayuan |last3=Wang |first3=Yusu |date=2018 |editor-last=Speckmann |editor-first=Bettina |editor2-last=Tóth |editor2-first=Csaba D. |title=Graph Reconstruction by Discrete Morse Theory |url=http://drops.dagstuhl.de/opus/volltexte/2018/8744 |conference=34th International Symposium on Computational Geometry (SoCG 2018) |series=Leibniz International Proceedings in Informatics (LIPIcs) |location=Dagstuhl, Germany |publisher=Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik |volume=99 |pages=31:1–31:15 |doi=10.4230/LIPIcs.SoCG.2018.31 |doi-access=free |isbn=978-3-95977-066-8|s2cid=3994099 }} denoising noisy point clouds{{Cite journal |last=Mukherjee |first=Soham |date=2021-09-01 |title=Denoising with discrete Morse theory |journal=The Visual Computer |volume=37 |issue=9 |pages=2883–94 |doi=10.1007/s00371-021-02255-7 |s2cid=237426675 }} and analysing lithic tools in archaeology.

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

{{Reflist|refs=

{{citation

|first1=Jan Philipp|last1=Bullenkamp

|first2=Florian|author3-link=Hubert Mara

|last2=Linsel

|first3=Hubert|last3=Mara

|periodical=Proceedings of Eurographics Workshop on Graphics and Cultural Heritage (GCH)

|title=Lithic Feature Identification in 3D based on Discrete Morse Theory

|publisher=Eurographics Association

|location=Delft, Netherlands

|pages=55–58

|issn=2312-6124

|date=2022

|doi=10.2312/VAST/VAST10/131-138

|isbn=9783038681786

|s2cid=17294591

|url=https://diglib.eg.org:443/handle/10.2312/gch20221224

|access-date=2022-10-05}}

}}

{{refbegin}}

• {{cite journal |first=Robin |last=Forman |title=Morse theory for cell complexes |journal=Advances in Mathematics |volume=134 |issue=1 |pages=90–145 |date=1998 |doi=10.1006/aima.1997.1650 | doi-access=free |url=https://core.ac.uk/download/pdf/82268273.pdf}}
• {{cite journal|first=Robin|last= Forman |year=2002| url=http://www.emis.de/journals/SLC/wpapers/s48forman.pdf|title= A user's guide to discrete Morse theory|journal= Séminaire Lotharingien de Combinatoire|volume= 48|pages=Art. B48c, 35 pp|mr=1939695 }}
• {{cite book | first=Dmitry|last= Kozlov | title=Combinatorial algebraic topology | series=Algorithms and Computation in Mathematics|volume= 21 |publisher=Springer |year=2007 | isbn=978-3540719618|mr=2361455}}
• {{cite book | first=Jakob|last= Jonsson | title=Simplicial complexes of graphs | publisher=Springer | year=2007 | isbn=978-3540758587}}
• {{cite book | first1=Peter|last1= Orlik|author1-link=Peter Orlik|first2= Volkmar|last2= Welker | title=Algebraic Combinatorics: Lectures at a Summer School In Nordfjordeid | publisher=Springer|series=Universitext | year=2007 | isbn=978-3540683759|mr=2322081|doi=10.1007/978-3-540-68376-6}}
• {{cite web|url=http://ncatlab.org/nlab/show/discrete+Morse+theory|title=Discrete Morse theory|publisher=nLab}}

{{refend}}

Category:Combinatorics

Category:Morse theory

Category:Computational topology