Optimal decision trees on simplicial complexes

MaRDI QIDQ1773193zbMATH OpenFDO

Authors Jakob Jonsson

Publication date 25 April 2005

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/125246, http://www.emis.de/journals/EJC/Volume_12/Abstracts/v12i1r3.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

decision treesMorse theory

Mathematics Subject Classification ID

Algebraic aspects of posets (06A11) Simplicial sets and complexes in algebraic topology (55U10)

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.

Recommendations

• Morse theory and evasiveness
• Decision tree complexity and Betti numbers
• Simplicial complexes of graphs
• A user's guide to discrete Morse theory
• On the complexity of the representation of simplicial complexes by trees

Cited in

(12)

• Matching complexes of small grids
• Matching complexes of trees and applications of the matching tree algorithm
• Matching and independence complexes related to small grids
• Vertex decomposability of 2-CM and Gorenstein simplicial complexes of codimension 3
• Chains of modular elements and shellability
• The decision tree polytope and its application to sequential decision problems
• Combinatorial realization of the Thom-Smale complex via discrete Morse theory
• On the homotopy and strong homotopy type of complexes of discrete Morse functions
• Decision tree complexity and Betti numbers
• Morse theory and evasiveness
• Evasiveness through binary decision diagrams
• Simple and optimal output-sensitive construction of contour trees using monotone paths

This page was built for publication: Optimal decision trees on simplicial complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1773193)