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]and mesh compression[3].
Contents |
Let be a CW complex. Define the incidence function in the following way: given two cells and in , equals 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 .
A Real-valued function is a discrete Morse function if it satisfies the following two properties:
It can be shown[4] that both conditions can not hold 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:
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.
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.
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 [5] hold
Moreover, the Euler characteristic of satisfies
Let be a regular CW complex with boundary operator a discrete Morse function . Let be the associated Morse complex with Morse boundary operator . Then, there is an isomorphism[6] of Homology groups