Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Partitions with Restricted Block Sizes, Möbius Functions and the k-of-each Problem.

Please always quote using this URN: urn:nbn:de:0297-zib-1363
  • {\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.}

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Svante Linusson
Document Type:ZIB-Report
Date of first Publication:1994/03/10
Series (Serial Number):ZIB-Report (SC-94-06)
ZIB-Reportnumber:SC-94-06
Published in:Appeared in: SIAM Journal on Discrete Mathematics 10 (1997) 18-29
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.