Optimal decision trees on simplicial complexes
type: Item
instance of: scholarly article
title: Optimal decision trees on simplicial complexes
zbMATH Open document ID: 1075.05088
author: Jakob Jonsson
published in: The Electronic Journal of Combinatorics
publication date: 2005-04-25T00:00:00Z
full work available at URL: https://eudml.org/doc/125246
full work available at URL: v12i1r3.html
review text: 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.
reviewed by: F. J. Díaz
Mathematics Subject Classification ID: 05E25
Mathematics Subject Classification ID: 06A11
Mathematics Subject Classification ID: 55U10
zbMATH DE Number: 2161304
zbMATH Keywords: Morse theory
zbMATH Keywords: decision trees
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2161304