Discrete Morse theory
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] denoising,[3] and mesh compression.[4]
Notation regarding CW complexes
Let be a CW complex. Define the incidence function
in the following way: given two cells
and
in
, let
be the degree of the attaching map from the boundary of
to
. The boundary operator
on
is defined by
It is a defining property of boundary operators that . In more axiomatic definitions[5] one can find the requirement that
which is a corollary of the above definition of the boundary operator and the requirement that .
Discrete Morse functions
A real-valued function is a discrete Morse function if it satisfies the following two properties:
- For any cell
, the number of cells
in the boundary of
which satisfy
is at most one.
- For any cell
, the number of cells
containing
in their boundary which satisfy
is at most one.
It can be shown[6] that the cardinalities in the two conditions cannot both be one simultaneously for a fixed cell , provided that
is a regular CW complex. In this case, each cell
can be paired with at most one exceptional cell
: 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:
, where:
-
denotes the critical cells which are unpaired,
-
denotes cells which are paired with boundary cells, and
-
denotes cells which are paired with co-boundary cells.
By construction, there is a bijection of sets between -dimensional cells in
and the
-dimensional cells in
, which can be denoted by
for each natural number
. It is an additional technical requirement that for each
, the degree of the attaching map from the boundary of
to its paired cell
is a unit in the underlying ring of
. For instance, over the integers
, the only allowed values are
. This technical requirement is guaranteed when one assumes that
is a regular CW complex over
.
The fundamental result of discrete Morse theory establishes that the CW complex is isomorphic on the level of homology to a new complex
consisting of only the critical cells. The paired cells in
and
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.
The Morse complex
A gradient path is a sequence of paired cells
satisfying and
. 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
must decrease across
. The path
is said to connect two critical cells
if
. This relationship may be expressed as
. 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 to
.
Basic Results
Many of the familiar results from continuous Morse theory apply in the discrete setting.
The Morse Inequalities
Let be a Morse complex associated to the CW complex
. The number
of
-cells in
is called the
Morse number. Let
denote the
Betti number of
. Then, for any
, the following inequalities[7] hold
, and
Moreover, the Euler characteristic of
satisfies
Discrete Morse Homology and Homotopy Type
Let be a regular CW complex with boundary operator
and a discrete Morse function
. Let
be the associated Morse complex with Morse boundary operator
. Then, there is an isomorphism[8] of Homology groups as well as homotopy groups.
See also
- Digital Morse theory
- Stratified Morse theory
- Shape analysis
- Topological combinatorics
- Discrete differential geometry
References
- ↑ F. Mori and M. Salvetti: (Discrete) Morse theory for Configuration spaces
- ↑ Perseus: the Persistent Homology software.
- ↑ U. Bauer, C. Lange, and M. Wardetzky: Optimal Topological Simplification of Discrete Functions on Surfaces
- ↑ T Lewiner, H Lopez and G Tavares: Applications of Forman's discrete Morse theory to topological visualization and mesh compression
- ↑ Mischaikow, Konstantin; Nanda, Vidit. "Morse Theory for Filtrations and Efficient computation of Persistent Homology". Springer. Retrieved 3 August 2013.
- ↑ Forman, Robin: Morse Theory for Cell Complexes, Lemma 2.5
- ↑ Forman, Robin: Morse Theory for Cell Complexes, Corollaries 3.5 and 3.6
- ↑ Forman, Robin: Morse Theory for Cell Complexes, Theorem 7.3
- 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.
- nLab Article