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][3] denoising,[4] mesh compression,[5] and topological data analysis.
be the degree of the attaching map from the boundary of
The boundary operator is the endomorphism
of the free abelian group generated by
In more axiomatic definitions[7] one can find the requirement that
which is a consequence of the above definition of the boundary operator and the requirement that
is a discrete Morse function if it satisfies the following two properties: It can be shown[8] that the cardinalities in the two conditions cannot both be one simultaneously for a fixed cell
value, or a co-boundary cell with smaller
Thus, a discrete Morse function partitions the CW complex into three distinct cell collections:
, where: By construction, there is a bijection of sets between
It is an additional technical requirement that for each
, the degree of the attaching map from the boundary of
is a unit in the underlying ring of
This technical requirement is guaranteed, for instance, when one assumes that
The fundamental result of discrete Morse theory establishes that the CW complex
is isomorphic on the level of homology to a new complex
describe gradient paths between adjacent critical cells which can be used to obtain the boundary operator on
Some details of this construction are provided in the next section.
A gradient path is a sequence of paired cells satisfying
The index of this gradient path is defined to be the integer The division here makes sense because the incidence between paired cells must be
Note that by construction, the values of the discrete Morse function
The multiplicity of this connection is defined to be the integer
) ⋅ ν ( ρ ) ⋅ κ (
Finally, the Morse boundary operator on the critical cells
is defined by where the sum is taken over all gradient path connections from
Many of the familiar results from continuous Morse theory apply in the discrete setting.
, the following inequalities[9] hold Moreover, the Euler characteristic
be a regular CW complex with boundary operator
Discrete Morse theory finds its application in molecular shape analysis,[11] skeletonization of digital images/volumes,[12] graph reconstruction from noisy data,[13] denoising noisy point clouds[14] and analysing lithic tools in archaeology.