A new proof of a theorem of Harper on the Sperner-Erdős problem
type: Item
instance of: scholarly article
title: A new proof of a theorem of Harper on the Sperner-Erdős problem
zbMATH Open document ID: 0576.05001
DOI: 10.1016/0097-3165(85)90079-2
author: Konrad Engel
published in: Journal of Combinatorial Theory. Series A
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 3920475
zbMATH Keywords: Harper's theorem
zbMATH Keywords: Sperner families
zbMATH Keywords: ranked poset
zbMATH Keywords: weighted posets
zbMATH Keywords: linear programming
zbMATH Keywords: relation graphs of posets
MaRDI profile type: Publication
full work available at URL: 0097-3165(85)90079-2
OpenAlex ID: W2095113088
cites work: Q3673576
cites work: Optimal representations of partially ordered sets and a limit Sperner theorem
cites work: Q5514188
cites work: Blocking and anti-blocking pairs of polyhedra
cites work: Q4196436
cites work: The structure of Sperner k-families
cites work: Maximal sized antichains in partial orders
cites work: The global theory of flows in networks
cites work: A short proof of the existence of k-saturated partitions of partially ordered sets
description: scientific article; zbMATH DE number 3920475