A combinatorial method to compute explicit homology cycles using discrete Morse theory (Q2304018)

Suppose we are given a discrete Morse function on a polyhedral complex \(K\). Here we view a discrete Morse function as an acyclic matching \(\mu\) on a subset \(X\) of the face poset \(\mathcal{F}(K)\) of \(K\). The main goal of the paper under review is to use the acyclic matching to explicitly write down the generating homology cycles of \(K\). After giving a very brief background of discrete Morse theory in Section 2, the main result is proved in Section 3. Define a directed graph \(G_d(\mu)\), where \(d\) is any dimension between \(0\) and \(\mathrm{dim}(K)\) as follows: the vertex set of \(G_d(\mu)\) is indexed by the \(d\)-simplices of \(K\) while \((\alpha, \beta)\) is an edge of \(G_d(\mu)\) if and only if \(\mu\_(\beta)\) is defined and \(\alpha\succ \mu\_(\beta)\), where \(\mu\_(\beta)\) is an element covered by \(\beta\) in the poset \(\mathcal{F}(K)\). From here, the author defines what he calls the closure map \(\varphi\) which maps each vertex of \(G_d(\mu)\) to a set of vertices of \(G_d(\mu)\). This may be thought of as mapping a \(d\)-simplex to a \(d\)-chain of \(K\). The main theorem says that given that there are no critical cells in dimensions \(d-1\) or \(d+1\), then \(\varphi(\sigma)\) is a homology cycle, where \(\sigma\) is a unique critical \(d\)-simplex contained in the support of \(\varphi(\sigma)\). It is then an easy corollary to show that the homology classes \([\varphi(\sigma)]\) over all critical \(d\)-simplices form a basis for \(H_d(K)\). Section 4 uses the main result of Section 3 to compute homology generators in the cases where \(K\) is the \(d\)-skeleton of the \(n\)-simplex, the complex of disconnected graphs, and the order complex of the partition lattice. These examples utilize the power of theory in the previous section, in particular, by illustrating that finding homology generators is quite computable. In fact, Section 6 gives an algorithm to compute homology generators given an acyclic matching on a \(d\)-dimensional complex. The running time of the algorithm is linear in the number of \(d\)-cells. This running time is best possible.