Allowing cycles in discrete Morse theory (Q2401549): Difference between revisions

Let \(X\) be a finite-dimensional CW complex and \(f: X \to \mathbb{R}\) be a discrete Morse function in the sense of \textit{R. Forman} [Sémin. Lothar. Comb. 48, B48c, 35 p. (2002; Zbl 1048.57015)]. As in Morse theory, it is a fundamental result in discrete Morse theory that if \(f\) has \(m_i\) critical cells of dimension \(i\), then \(X\) is homotopy-equivalent to a space built out of \(m_i\) cells of dimension \(i\) over all permissible \(i\). For many computational purposes, we desire to reduce a CW complex \(X\) to an equivalent CW complex with much fewer cells. The problem of reducing \(X\) to a CW complex with a fewer number of cells thus reduces to finding a discrete Morse function on \(X\) with few critical cells. The minimum such possibility is given by the so-called optimal discrete Morse vector \((m_0, m_1, \ldots, m_n)\) which is minimal in the sense that if \((m_0', m_1', \ldots, m_n')\) is the discrete Morse vector for any other discrete Morse function, then \(\sum m_i\leq \sum m_i'\). Yet in general, finding such a discrete Morse function is extremely difficult, as it has been shown to be NP-hard. Nevertheless, the purpose of this paper is to find optimal discrete Morse function under certain algebraic conditions. To this end, the authors define a Homological Discrete Vector Field (HDVF), a concept which is meant to generalize the discrete gradient vector field. Because the purpose of this definition is to aid in computation, it is defined in terms of certain properties of matrices boundary operators on the corresponding chain complex of \(X\). The authors give many examples to compute this explicitly, with many illustrations and direct computations. The computation is given in terms of an algorithm, and the authors prove it runs within \(O(n^3)\) operations. The authors devote a chapter to comparing this algorithm with other standard standard ways to compute homology. The paper concludes with a discussion of future directions.