Frontiers of sphere recognition in practice (Q2098099)

Let \(K\) be a \(d\)-dimensional finite simplicial complex. The authors of the article present a multi-step heuristic for testing if \(K\) is a PL \(d\)-sphere. The first step involves verifying that \(K\) is a combinatorial \(d\)-manifold, and that its homology matches that of a \(d\)-sphere. In the second step, random discrete Morse functions in the style of \textit{B. Benedetti} and \textit{F. H. Lutz} [Exp. Math. 23, No. 1, 66--94 (2014; Zbl 1296.57018)] are generated, and are checked to see if they have single critical faces in dimensions \(0\) and \(d\) only. The third step is to modify \(K\) by applying bistellar flips (Pachner moves) and edge contractions, chosen randomly but with the goal of reducing the \(f\)-vector of \(K\). The resulting complex is checked if it is the boundary of a simplex. The last step involves computing the fundamental group of \(K\) and checking against the trivial group. If last step exits without a definitive result, the heuristic fails and no conclusion is drawn about \(K\). Numerical experiments performed indicate that the heuristic compares favorably, in terms of execution time and the ability to handle large complexes, with existing software programs. In addition, the authors introduce a class of contractible, but not collapsible, two-dimensional cell complexes which can be used to investigate the limits of sphere recognition algorithms.