A new proof of a theorem of Harper on the Sperner-Erdős problem
Let P be a finite poset. A weight on P is a function \(v: P\to \{x\in R\); \(x>0\}\), a rank on P is a function \(r: P\to \{0,1,2,...\}\) such that \(r(x)=0\), if x is minimal, and \(r(x)=r(y)+1\), if \(x>y\) (i.e., x covers y). For any subset \(S\subseteq P\) define \(v(S)=\sum_{x\in S}v(x)\). Put \(N_ i=\{x\in P;\quad r(x)=i\},\) \(r(P)=\max \{r(x);\quad x\in P\}.\) The weighted and ranked poset P is called normal, if \(v(A)/v(N_ i)\leq v(R(A))/v(N_{i+1})\) for all \(A\subseteq N_ i\) and \(i\in \{0,...,r(P)- 1\}\) where \(R(A)=\{x\in N_{i+1}\); \(x>a\) for some \(a\in A\}\). Let (P,v) and (Q,w) be weighted posets. A function \(\phi\) : \(P\to Q\) is called a flow morphism, if (i) \(\phi\) is surjective, (ii) \(x<y\) implies \(\phi (x)<\phi (y)\), (iii) \(w(x)=v(\phi^{-1}(x))\) for all \(x\in Q\), (iv) the poset induced on \(\phi^{-1}(x)\cup \phi^{-1}(y)\) is normal and has rank 1 for all x,y\(\in Q\) with \(x<y\). Using the framework of category theory, \textit{L. H. Harper} [Adv. Appl. Math. 1, 158-181 (1980; Zbl 0469.90028)] proved the following theorem: If there is a flow morphism \(\phi\) from (P,v) onto (Q,w), then max \(\{\) v(A); \(A\subseteq P\) is an \(antichain\}=\max \{w(B)\); \(B\subseteq Q\) is an antichain\(\}\). In the paper under review, the author gives another proof of this theorem. This proof is based on the method of linear programming and on the fact that relation graphs of posets are perfect.
scientific article; zbMATH DE number 3920475