Optimal decision trees on simplicial complexes (Q1773193): Difference between revisions

In this paper, based on \textit{R. Forman's} seminal papers on discrete Morse theory [Adv. Math. 134, No. 1, 90--145 (1998; Zbl 0896.57023); Combinatorica 20, No. 4, 489--504 (2000; Zbl 1028.05110)], the author studies how one may apply decision trees to problems in topological combinatorics. The number of evasive faces of a given dimension \(i\) with respect to a decision tree on a simplicial complex is greater than or equal to the \(i\)th reduced Betti number (over any field) of the complex. When a simplicial complex admits an ``optimal'' decision tree such that equality holds for each \(i\) one may read off the homology directly from the tree. Here the author gives a recursive definition of the class of semi-nonevasive simplicial complexes that admit an optimal decision tree. A certain generalization turns out to yield the class of semi-collapsible simplicial complexes that admit an optimal discrete Morse function in the analogous sense. So he investigates under what conditions the properties of being semi-nonevasive and semi-collapsible are preserved under standard operations such as taking the join of two complexes or forming the barycentric subdivision or Alexander dual of a complex. Finally, the author provides examples demonstrating how optimal decision trees give now proofs for the homotopy type of well-known simplicial complexes.