Sökning: onr:"swepub:oai:DiVA.org:kth-14446" >
Optimal decision tr...
Abstract
Ämnesord
Stäng
- 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.
Nyckelord
- shellable nonpure complexes
- discrete morse functions
- chessboard complexes
- connected graphs
- decompositions
- evasiveness
- posets
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas