tailieunhanh - Báo cáo toán học: "Optimal Decision Trees on Simplicial Complexes"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Optimal Decision Trees on Simplicial Complexes. | Optimal Decision Trees on Simplicial Complexes Jakob Jonsson Department of Mathematics KTH SE-10044 Stockholm Sweden jakob_jonsson@ Submitted Jun 13 2003 Accepted Oct 15 2004 Published Jan 7 2005 Mathematics Subject Classifications 05E25 55U10 06A11 Abstract 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 sim-plicial 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. Introduction We examine topological properties of decision trees on simplicial complexes the emphasis being on how one may apply decision trees to problems in topological combinatorics. Our work is to a great extent based on Forman s seminal papers 14 15 . Let A be an abstract simplicial complex consisting of subsets of a hnite set E. One may view a decision tree on the pair A E as a deterministic algorithm A that on input a secret set a c E asks repeated questions of the form Is the element x contained in a until all questions but one have been asked. A is allowed to be adaptive in the sense that each question may depend on responses to earlier questions. Let xơ be the one .