Posets with maximal Möbius function
Let P be any finite poset. P is said to be bounded if it contains a unique minimal element \({\hat 0}\) and a unique maximal element \({\hat 1}\). The Möbius function of a bounded poset P is defined by \(\mu(P)=\mu (\hat 0,\hat 1)\). The question about the maximum absolute value of \(\mu(P)\) was posed by \textit{R. Stanley} [Enumerative Combinatorics, Vol 1 (1986; Zbl 0608.05001); Exer. 3.41 a, with the author's answer announced there on p. 187]. In section 2 of the present paper the author gives a very short proof of this result (Th. 2.5) and indicates some extreme examples, too: Let P be a bounded poset of length \(l+1\), and \(| P\setminus \{\hat 0,\hat 1\}| =n\). Then \[ | \mu (P)| \leq \max_{0\leq k\leq \ell}\max_{p_ i\geq 1,\sum^{k}_{i=1}p_ i=n}\prod^{k}_{i=1}(p_ i-1); \] in the case when the equality appears, P has level type, i.e. is an ordinal sum of antichains. For every poset P there exists a bounded poset \(P^*\) with \(| P^*| =| P|\) and \(\ell (P^*)\leq \ell(P)\) which achieves the bound indicated above. In sect. 3 the author shows how to maximize the Möbius function on graded posets of given rank. He is working there with an induction on n, which depends on removing a suitable element x from P. To overcome the difficulty that there may not exist an element \(x\in P\setminus \{\hat 0,\hat 1\}\) with \(P\setminus x\) graded again, the author works with P such that \(\acute P=P\setminus \hat 1\) is ranked - this property is preserved under removal of maximal elements from \(\acute P\). He proves the following (part of Theorem 3.2): Let P be a bounded poset of length \(2+1\) such that \(\acute P\) is ranked with rank generating function \(1+\sum^{r}_{i}P_ it^ i(p_ i\geq 1).\) Let \(p_{r+1}\doteq 1\) and \(s\doteq \min \{i\geq 1| p_ i=1\};\) then \(| \mu (P)| \leq \prod^{s-1}_{i=1}(p_ i-1).\) A complete analysis of extremal cases that can arise is given also. In sect. 4 another question posed by \textit{R. Stanley} [loc. cit., Ex. 3.42], asking for the maximum Möbius function of a bounded poset of given length \(\ell+1\) and with every its element being covered by at most k other elements, is commented. The author works with such posets P that all elements in their Hasse diagrams (viewed as directed graphs) have not only their out-degrees but also their in-degrees bounded by k. In the last section some (asymptotic) conjectures and comments are given showing that the question about the maximal Möbius function for finite lattices appears to be much more complicated than for arbitrary posets. The methods of this paper are related to the compression techniques of extremal set theory; see [\textit{C. Greene} and \textit{D. J. Kleitman}, Proof techniques in the theory of finite sets, MAA Stud. Math., Vol. 17, Studies in Combinatorics, 22-79 (1978; Zbl 0409.05012)].
scientific article; zbMATH DE number 4197996