Optimal decision trees on simplicial complexes
2005 (English)In: The Electronic Journal of Combinatorics, ISSN 1077-8926, Vol. 12, no 1Article in journal (Refereed) Published
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.
Place, publisher, year, edition, pages
2005. Vol. 12, no 1
shellable nonpure complexes, discrete morse functions, chessboard complexes, connected graphs, decompositions, evasiveness, posets
IdentifiersURN: urn:nbn:se:kth:diva-14446ISI: 000226143800003ScopusID: 2-s2.0-13444252504OAI: oai:DiVA.org:kth-14446DiVA: diva2:332487
QC 201005252010-08-052010-08-05Bibliographically approved