Refine
Year of publication
- 1994 (1)
Document Type
- ZIB-Report (1)
Language
- English (1)
Has Fulltext
- yes (1)
Is part of the Bibliography
- no (1)
Institute
- ZIB Allgemein (1)
{\newcommand{\R} {{\rm {\mbox{\protect\makebox[.15em][l]{I}R}}}} Given a list of $n$ numbers in $\R $, one wants to decide wether every number in the list occurs at least $k$ times. I will show that $(1-\epsilon)n\log_3(n/k)$ is a lower bound for the depth of a linear decision tree determining this problem. This is done by using the Björner-Lov\'asz method, which turns the problem into one of estimating the Möbius function for a certain partition lattice. I will also calculate the exponential generating function for the Möbius function of a partition poset with restricted block sizes in general.}