Linear decision trees, subspace arrangements, and Möbius functions.

*(English)*Zbl 0811.05070A linear decision tree is a rooted ternary tree with a linear functional \(\ell_ \alpha\) attached to each interior node and leaves labelled YES or NO. The edges connecting an internal node to its three descendants are labelled with the symbols \(<\), \(=\), and \(>\). This model is used to test membership \(x \in P\) for a convex polyhedron \(P \subseteq R^ n\) by moving down the tree, at each node using the sign of \(\ell_ \alpha (x)\) to determine which edge to follow. Upon reaching a leaf, the question “is \(x \in P\)” is answered.

In this paper the authors give lower bounds on the number of YES and NO leaves in terms of the Betti numbers of \(R^ n\setminus P\). Then the theory of arrangements of convex sets (e.g. subspaces) and Möbius functions is used to give asymptotic lower bounds on the size and depth of linear decision trees for various sorting problems, such as the problem of determining, for a given set of \(n\) real numbers, whether some \(k\) of them are equal, or whether some \(k\) of them are pairwise distinct. The arguments involve specific calculation of Möbius functions for various subposets of the partition lattice. The resulting lower bounds are stronger than those derived earlier by the same authors and others.

In this paper the authors give lower bounds on the number of YES and NO leaves in terms of the Betti numbers of \(R^ n\setminus P\). Then the theory of arrangements of convex sets (e.g. subspaces) and Möbius functions is used to give asymptotic lower bounds on the size and depth of linear decision trees for various sorting problems, such as the problem of determining, for a given set of \(n\) real numbers, whether some \(k\) of them are equal, or whether some \(k\) of them are pairwise distinct. The arguments involve specific calculation of Möbius functions for various subposets of the partition lattice. The resulting lower bounds are stronger than those derived earlier by the same authors and others.

Reviewer: M.J.Falk (Madison)

##### MSC:

05E99 | Algebraic combinatorics |

06A07 | Combinatorics of partially ordered sets |

57N99 | Topological manifolds |

68Q25 | Analysis of algorithms and problem complexity |

68R05 | Combinatorics in computer science |

68P10 | Searching and sorting |

52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |

90B50 | Management decision making, including multiple objectives |