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.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: A new proof of a theorem of Harper on the Sperner-Erdős problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1065006)