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, homology computation and mesh compression.
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 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 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 .
Many of the familiar results from continuous Morse theory apply in the discrete setting.
The Morse Inequalities
- , 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 of Homology groups as well as homotopy groups.
- Digital Morse theory
- Stratified Morse theory
- Piece-wise linear Morse theory
- Shape analysis
- Topological combinatorics
- Discrete differential geometry
- F. Mori and M. Salvetti: (Discrete) Morse theory for Configuration spaces
- Perseus: Software for computing persistent homology groups.
- 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.