Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)

 

Linear decision trees, subspace arrangements and Möbius functions


Authors: Anders Björner and László Lovász
Journal: J. Amer. Math. Soc. 7 (1994), 677-706
MSC: Primary 52B55; Secondary 05C05, 06A09, 57M99, 68Q25
MathSciNet review: 1243770
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Topological methods are described for estimating the size and depth of decision trees where a linear test is performed at each node. The methods are applied, among others, to the questions of deciding by a linear decision tree whether given $ n$ real numbers (1) some $ k$ of them are equal, or (2) some $ k$ of them are unequal. We show that the minimum depth of a linear decision tree for these problems is at least (1) $ {\text{max}}\{ n - 1,\quad n\;{\text{lo}}{{\text{g}}_3}(n/3k)\} $, and (2) $ {\text{max}}\{ n - 1,\quad n\;{\text{lo}}{{\text{g}}_3}(k - 1) - k + 1\} $.

Our main lower bound for the size of linear decision trees for polyhedra $ P$ in $ {{\mathbf{R}}^n}$ is given by the sum of Betti numbers for the complement $ {{\mathbf{R}}^n}\backslash P$. The applications of this general topological bound involve the computation of the Möbius function of intersection lattices of certain subspace arrangements. In particular, this leads to computing various expressions for the Möbius function of posets of partitions with restricted block sizes. Some of these formulas have topological meaning. For instance, we derive a formula for the Euler characteristic of the subset of $ {{\mathbf{R}}^n}$ of points with no $ k$ coordinates equal in terms of the roots of the truncated exponential $ \sum\nolimits_{i < k} {{x^i}} /i!$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC: 52B55, 05C05, 06A09, 57M99, 68Q25

Retrieve articles in all journals with MSC: 52B55, 05C05, 06A09, 57M99, 68Q25


Additional Information

DOI: http://dx.doi.org/10.1090/S0894-0347-1994-1243770-0
PII: S 0894-0347(1994)1243770-0
Article copyright: © Copyright 1994 American Mathematical Society