Matthias Beck

On Sperner's Inequality and Its Generalizations

Abstract for the Combinatorics and Number Theory Seminar
2001 December 6

Sperner's inequality concerns the set P(S) consisting of all subsets of a finite set S, partially ordered by subset inclusion. A chain is a linearly ordered subset of P(S). In 1928, Sperner found a bound (in terms of the size of S) for the size of an antichain, that is, a subset of P(S) in which there are no nontrivial chains. His result was generalized in two different directions: About 25 years later, Erdös extended Sperner's inequality to r-systems, that is, subsets of P(S) in which chains contain at most r elements. Roughly another 25 years later, Meshalkin proved a Sperner-like inequality for a certain family of compositions (ordered partitions) of S. It's been about 25 years since Meshalkin's theorem, and hence about time for another extension. Xueqin Wang and I unify Erdös's and Meshalkin's inequalities and generalize them to a less restrictive family of compositions of S. As with the known theorems, our result has analogues in the poset of subspaces of a vector space.