Maximizing Möbius functions on subsets of Boolean algebras
type: Item
instance of: scholarly article
title: Maximizing Möbius functions on subsets of Boolean algebras
zbMATH Open document ID: 0809.05004
DOI: 10.1016/0012-365X(94)90273-9
author: Bruce E. Sagan
author: Yeong-Nan Yeh
author: Günter M. Ziegler
published in: Discrete Mathematics
publication date: 1994-04-04T00:00:00Z
review text: Denote by \(\mu(P)\) the value \(\mu_ P(\widehat 0,\widehat 1)\) of the Möbius function \(\mu_ P\) for a bounded, graded poset \(P\); such a poset has the rank function \(\rho: P\to \mathbb{N}\). The authors find and interpret the maximum value of \(|\mu(P)|\) for certain types of posets \(P\). Let \(F\) be a subposet of the poset \({\mathfrak B}(S)\) of all subsets of an \(n\)-element set \(S\) ordered by inclusion. Also, adjoin, if necessary, the subsets \(\varnothing\) and \(S\) to \(\mathfrak F\) to form a bounded poset \(\widehat{\mathfrak F}= {\mathfrak F}\cup \{\varnothing\}\cup \{S\}\), and denote by \(\mu({\mathfrak F})\) the value \(\mu_{\widehat F}(\varnothing, S)\). Further, for a given family \({\mathfrak F}\subseteq {\mathfrak B}(S)\backslash\{\varnothing, S\}\) and any subset \(R\subseteq\overline{1,n-1}\) denote by \({\mathfrak F}(R)\) the rank-selected subposet \({\mathfrak F}(R)= \{X\in {\mathfrak F}\mid \rho(X)= | X|\in R\}\). The main result (Theorem 1.2) in this paper can be formulated as follows: (1) If \(\mathfrak F\) is a lower order ideal, i.e. from \(X\in {\mathfrak F}\) and \(Y\subseteq X\) follows \(Y\in {\mathfrak F}\), then \[ | \mu({\mathfrak F})|\leq \left({n-1\atop \left\lfloor{n-1\over 2}\right\rfloor}\right) \] with equality iff \({\mathfrak F}= {\mathfrak P}_ n(\mathbb{K})\). Here \({\mathfrak P}_ n(\mathbb{K})\) is defined as the set \[ \{\alpha= (a_ 1 a_ 2\cdots a_ n)\mid \{i\mid a_ i> a_{i+1}\}\equiv \mathbb{R}\}. \] (2) If \({\mathfrak F}= {\mathfrak P}_ n(R)\) for some \(R\subseteq \overline {1,n-1}\), then \(_ |\mu({\mathfrak F})|\leq E_ n\), where the sequence \((E_ n\mid n\geq 0)= (1,1,1,2,5,16,61,\dots)\), i.e. the Euler numbers can be defined by \(\sum_{n\geq 0} E_ n{x^ n\over n!}= \tan x+ \text{sec }x\). Equality occurs iff \(R= \{1,2,3,\dots\}\) or \(R= \{2,4,6,\dots\}\). (3) If \({\mathfrak F}= {\mathfrak P}_ n(R)\) for \(R=[k,\ell]\leq \{k,k+1,\dots,\ell\}\), then \[ |\mu(F)|\leq\begin{cases} p_ n\left(\left[{n\over …
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 540945
zbMATH Keywords: Boolean algebras
zbMATH Keywords: simplex
zbMATH Keywords: Möbius function
zbMATH Keywords: poset
zbMATH Keywords: subposet
zbMATH Keywords: Euler characteristic
zbMATH Keywords: subcomplex
Wikidata QID: Q89354640
reviewed by: U. Kaljulaid
MaRDI profile type: Publication
cites work: Q3050437
cites work: Q3741626
cites work: Q3952144
cites work: An extended Euler-Poincaré theorem
cites work: Q5603208
cites work: On induced subgraphs of the cube
cites work: Die Euler-Charakteristik von Vereinigungen konvexer Mengen im R
cites work: Limits of values of the Möbius function
cites work: Q5549086
cites work: On the foundations of combinatorial theory I. Theory of M�bius Functions
cites work: Q3748279
cites work: Posets with maximal Möbius function
DBLP publication ID: journals/dm/SaganYZ94
description: scientific article; zbMATH DE number 540945