Maximizing Möbius functions on subsets of Boolean algebras (Q1318819): Difference between revisions

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 3}, {2n\over 3}- 1\right]\right) &\text{for } n\equiv 0\pmod 3,\\ p_ n \left(\left[\left\lceil{n\over 3}\right\rceil,\;\left\lfloor{2n\over 3}\right\rfloor\right]\right) &\text{for } n\equiv\pm 1\pmod 3,\end{cases} \] where \(p_ n(R)\) denotes the cardinality of \({\mathfrak P}_ n(R)\). Equality holds iff \(R\) is one of the intervals mentioned to guarantee the equations in (1) and (2). Part (1) of the above theorem when interpreted as giving the maximum absolute value of the Euler characteristic of a subcomplex of the \((n- 1)\)-simplex has been found independently by \textit{J. Eckhoff} [Abh. Math. Sem. Univ. Hamb. 50, 135-146 (1980; Zbl 0451.52002)] and \textit{H. Scheid} [J. Comb. Theory, Ser. A 13, 315-331 (1972; Zbl 0247.06001)]. Part (3) has been proved also by \textit{I. Niven} [Nieuw Arch. Wiskunde, III. Ser. 16, 116-123 (1968; Zbl 0164.331)] and \textit{N. G. de Bruijn} [Nieuw Arch. Wiskunde, III. Ser. 18, 61-65 (1970; Zbl 0203.306)]. Analogs of the above results for the (sub)poset (in \({\mathfrak B}(V)\)) of all subspaces of an \(n\)-dimensional vector space \(V\) over the field \(k= \text{GF}(q)\), i.e. \(q\)-analogs with \(\rho(X)= \dim_ k X\leq V\), are also indicated. Numerous interesting comments and further questions are posed in this paper.