Maximizing Möbius functions on subsets of Boolean algebras

✍ Scribed by Bruce E Sagan; Yeong-Nan Yeh; Günter M Ziegler

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 1008 KB
• Volume: 126
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)90273-9

✦ Synopsis

Let 5 be a family of subsets of an n-set, considered as a subposet of the Boolean algebra B.. Adjoin a minimum 0 and maximum i if necessary to form @. Let ~(95) denote the value of the Mdbius function p(6,i) in &. We compute the maximum value of Ip( as 9 ranges over three types of families in B,: lower order ideals, intervals of rank levels, and arbitrary rank-selections.

The maxima are obtained by taking the lower half, the middle third, and every other rank of B,, respectively. The maximum for the first case was previously found by Eckhoff (1980) and Scheid (1979). It allows us to answer a question raised by Fiiredi based on his joint work with Chung, Graham and Seymour (1988). The third maximum was also previously given by Niven (1968) and de Bruijn (1970). Finally, we consider lower order ideal case for the lattice of subspaces of a vector space, the maximum being achieved by taking the whole poset.