✦ LIBER ✦
A Shorter, Simpler, Stronger Proof of the Meshalkin–Hochberg–Hirsch Bounds on Componentwise Antichains
✍ Scribed by Matthias Beck; Thomas Zaslavsky
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 83 KB
- Volume
- 100
- Category
- Article
- ISSN
- 0097-3165
No coin nor oath required. For personal study only.
✦ Synopsis
Meshalkin's theorem states that a class of ordered p-partitions of an n-set has at most maxð n a1;...;ap Þ members if for each k the kth parts form an antichain. We give a new proof of this and the corresponding LYM inequality due to Hochberg and Hirsch, which is simpler and more general than previous proofs. It extends to a common generalization of Meshalkin's theorem and Erd + o os's theorem about r-chainfree set families.