Discrete Morse theory

From Wikipedia, the free encyclopedia

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 [6].

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[7] 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:

  1. For any cell , the number of cells in the boundary of which satisfy is at most one.
  2. For any cell , the number of cells containing in their boundary which satisfy is at most one.

It can be shown[8] 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., 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: , where:

  1. denotes the critical cells which are unpaired,
  2. denotes cells which are paired with boundary cells, and
  3. 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, for instance, 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[9] 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[10] of Homology groups as well as homotopy groups.

See also

References

  1. ^ F. Mori and M. Salvetti: (Discrete) Morse theory for Configuration spaces Archived April 26, 2012, at the Wayback Machine.
  2. ^ Perseus: the Persistent Homology software.
  3. ^ Mischaikow, Konstantin; Nanda, Vidit. "Morse Theory for Filtrations and Efficient computation of Persistent Homology". Springer. Retrieved 3 August 2013. 
  4. ^ U. Bauer, C. Lange, and M. Wardetzky: Optimal Topological Simplification of Discrete Functions on Surfaces
  5. ^ T Lewiner, H Lopez and G Tavares: Applications of Forman's discrete Morse theory to topological visualization and mesh compression
  6. ^ "the Topology ToolKit". 
  7. ^ Mischaikow, Konstantin; Nanda, Vidit. "Morse Theory for Filtrations and Efficient computation of Persistent Homology". Springer. Retrieved 3 August 2013. 
  8. ^ Forman, Robin: Morse Theory for Cell Complexes Archived April 24, 2012, at the Wayback Machine., Lemma 2.5
  9. ^ Forman, Robin: Morse Theory for Cell Complexes Archived April 24, 2012, at the Wayback Machine., Corollaries 3.5 and 3.6
  10. ^ Forman, Robin: Morse Theory for Cell Complexes Archived April 24, 2012, at the Wayback Machine., 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 [1]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Discrete_Morse_theory&oldid=797648654"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Discrete_Morse_theory
This page is based on the copyrighted Wikipedia article "Discrete Morse theory"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA