nLab
discrete Morse theory

Discrete Morse Theory

Discrete Morse theory aims to do for simplicial complexes and more generally, finite CW complexes what standard Morse theory does for manifolds.

Partial Matchings on CW Complexes

Let XX be a finite CW complex. The central idea is to make extensive use of simple homotopy theory. Although the initial formulation of discrete Morse theory involved certain families of locally constant functions f:Xf:X \to \mathbb{R} playing the role of Morse functions, a cleaner treatment may be given as follows. An acyclic matching on XX consists of the following data: a partition of the cells into three disjoint classes A,BA, B and CC along with a distinguished set-bijection w:ABw: A \to B. This data is required to obey the following axioms:

  • for each cell aAa \in A, the matched cell w(a)w(a) is a regular co-face of aa, meaning that dim(w(a))=dim(a)+1\dim (w(a)) = \dim (a) + 1 and the degree of the attaching map from w(a)w(a) to aa is ±1\pm 1,
  • the relation \prec on AA generated by aaa \prec a' whenever aa is a (not necessarily regular) face of w(a)w(a') defines a partial order.

Homotopy

A central result of discrete Morse theory is as follows: if XX is any finite CW complex which admits an acyclic matching with nn critical cells, then XX is homotopy equivalent to a CW complex with nn cells. The proof is similar in spirit to the traditional Morse lemmas: instead of deforming along flow lines between adjacent critical points, one uses simple homotopy collapses to obtain the desired equivalence.

Gradient Paths and Morse Homology

The unmatched cells CC play the role of critical points, while the matched cells in AA and BB generate gradient-like paths between critical cells. In fact, if we denote the face relation in XX by \leq, then a gradient path from critical cell cc to critical cell cc' consists precisely of an alternating sequence of distinct matched cells which fit together like this:

ca 0w(a 0)a 1w(a 1)a nw(a n)cc \geq a_0 \leq w(a_0) \geq a_1 \leq w(a_1) \geq \ldots \geq a_n \leq w(a_n) \geq c'

Each such path can be assigned an multiplicity given by a product of attaching degrees: reading from left to right, each time one sees xyx \geq y, one multiplies by the degree of the attaching map from xx to yy, and each time one sees yxy \leq x one divides by this degree. The first axiom of the partial matching guarantees that one only divides by ±1\pm 1, while the second axiom guarantees that no such path can go “backwards” from cc' up to cc.

The Morse Complex (C,d)(C,d) is the free chain complex built on the critical cells in CC where the component of the boundary operator dd from cc to cc' is the sum of multiplicity over all gradient paths from cc to cc'. The main Theorem is that the Morse complex has the same integer homology groups as XX.

Applications

Discrete Morse theory has been used in topological combinatorics to show that certain simplicial complexes are homotopy-equivalent to wedges of spheres. It has also been used in commutative algebra to construct minimal resolutions of ideals in polynomial rings. Discrete Morse theory is also used extensively in homology and persistent homology computations as in the CHomP and Perseus software packages.

Last revised on June 4, 2014 at 12:52:48. See the history of this page for a list of all contributions to it.