Search: onr:"swepub:oai:DiVA.org:kth-14446" >
Optimal decision tr...
Abstract
Subject headings
Close
- We consider topological aspects of decision trees on simplicial complexes, concentrating on how to use decision trees as a tool in topological combinatorics. By Robin Forman's discrete Morse theory, 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 ith reduced Betti number (over any field) of the complex. Under certain favorable circumstances, a simplicial complex admits an optimal decision tree such that equality holds for each i; we may hence read off the homology directly from the tree. We provide a recursive definition of the class of semi-nonevasive simplicial complexes with this property. 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. In addition, we develop some elementary theory about semi-nonevasive and semi-collapsible complexes. Finally, we provide explicit optimal decision trees for several well-known simplicial complexes.
Keyword
- shellable nonpure complexes
- discrete morse functions
- chessboard complexes
- connected graphs
- decompositions
- evasiveness
- posets
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database