Change search
ReferencesLink to record
Permanent link

Direct link
Optimal decision trees on simplicial complexes
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
2005 (English)In: The Electronic Journal of Combinatorics, ISSN 1077-8926, Vol. 12, no 1Article in journal (Refereed) Published
Abstract [en]

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
Keyword [en]
shellable nonpure complexes, discrete morse functions, chessboard complexes, connected graphs, decompositions, evasiveness, posets
URN: urn:nbn:se:kth:diva-14446ISI: 000226143800003ScopusID: 2-s2.0-13444252504OAI: diva2:332487
QC 20100525Available from: 2010-08-05 Created: 2010-08-05Bibliographically approved

Open Access in DiVA

No full text


Search in DiVA

By author/editor
Jonsson, Jakob
By organisation
Mathematics (Div.)
In the same journal
The Electronic Journal of Combinatorics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 18 hits
ReferencesLink to record
Permanent link

Direct link