Posets with maximal Möbius function
type: Item
instance of: scholarly article
title: Posets with maximal Möbius function
zbMATH Open document ID: 0726.05010
DOI: 10.1016/0097-3165(91)90033-D
published in: Journal of Combinatorial Theory. Series A
publication date: 1991-01-01T00:00:00Z
review text: 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 ma…
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 4197996
zbMATH Keywords: Möbius function
zbMATH Keywords: bounded poset
author: Günter M. Ziegler
reviewed by: U. Kaljulaid
MaRDI profile type: MaRDI publication profile
cites work: Combinatorial theory.
cites work: An extended Euler-Poincaré theorem
cites work: Q3852212
cites work: Q4196436
cites work: On cliques in graphs
cites work: On the foundations of combinatorial theory I. Theory of M�bius Functions
cites work: Q3748279
cites work: The Recognition of Series Parallel Digraphs
full work available at URL: 0097-3165(91)90033-d
OpenAlex ID: W2105364514
Recommended article: Maximizing Möbius functions on subsets of Boolean algebras
Recommended article: Remarks on the Möbius function of a subposet
Recommended article: Maximizing the Möbius function of a poset and the sum of the Betti numbers of the order complex
Recommended article: Extremal problems for the Möbius function in the face lattice of the \(n\)-octahedron
Recommended article: On lattices with Möbius function \(\pm 1,0\)
description: scientific article; zbMATH DE number 4197996