Linear decision trees, subspace arrangements and Möbius functions
Anders Björner, László Lovász · Journal of the American Mathematical Society · 1994
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 n real numbers (1) some k k of them are equal, or (2) some k k of them are unequal. We show that the minimum depth of a linear decision tree for these problems is at least (1) max { n − 1 , n lo g 3 ( n / 3 k ) } {\text {max}}\{ n - 1,\quad n\;{\text {lo}}{{\text {g}}_3}(n/3k)\} , and (2) max { n − 1 , n lo g 3 ( k − 1 ) − k + 1 } {\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 P in R n {{\mathbf {R}}^n} is given by the sum of Betti numbers for the complement R n ∖ P {{\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 le