Sperner's theorem

Sperner's theorem, in discrete mathematics, describes the largest possible families of finite sets none of which contain any other sets in the family.

It is one of the central results in extremal set theory.

This result is sometimes called Sperner's lemma, but the name "Sperner's lemma" also refers to an unrelated result on coloring triangulations.

The value of k that makes this example have as many sets as possible is n/2 if n is even, or either of the nearest integers to n/2 if n is odd.

Sperner's theorem states that these examples are the largest possible Sperner families over an n-element set.

Formally, the theorem states that, Sperner's theorem can also be stated in terms of partial order width.

The family of all subsets of an n-element set (its power set) can be partially ordered by set inclusion; in this partial order, two distinct elements are said to be incomparable when neither of them contains the other.

The width of a partial order is the largest number of elements in an antichain, a set of pairwise incomparable elements.

Translating this terminology into the language of sets, an antichain is just a Sperner family, and the width of the partial order is the maximum number of sets in a Sperner family.

Thus, another way of stating Sperner's theorem is that the width of the inclusion order on a power set is

A graded partially ordered set is said to have the Sperner property when one of its largest antichains is formed by a set of elements that all have the same rank.

In this terminology, Sperner's theorem states that the partially ordered set of all subsets of a finite set, partially ordered by set inclusion, has the Sperner property.

There are many proofs of Sperner's theorem, each leading to different generalizations (see Anderson (1987)).

Let sk denote the number of k-sets in S. For all 0 ≤ k ≤ n, and, thus, Since S is an antichain, we can sum over the above inequality from k = 0 to n and then apply the LYM inequality to obtain which means This completes the proof of part 1.

we conclude that equality implies that S consists only of sets of sizes

For odd n there is more work to do, which we omit here because it is complicated.

The chain has r + 1 members and length r. An r-chain-free family (also called an r-family) is a family of subsets of E that contains no chain of length r. Erdős (1945) proved that the largest size of an r-chain-free family is the sum of the r largest binomial coefficients

form a partition of E. Meshalkin (1963) proved that the maximum size of an antichain of p-compositions is the largest p-multinomial coefficient

that is, the coefficient in which all ni are as nearly equal as possible (i.e., they differ by at most 1).

Beck & Zaslavsky (2002) combined the Erdös and Meshalkin theorems by adapting Meshalkin's proof of his generalized LYM inequality.

They showed that the largest size of a family of p-compositions such that the sets in the i-th position of the p-tuples, ignoring duplications, are r-chain-free, for every

When partially ordered by set inclusion, this family is a lattice.

Rota & Harper (1971) proved that the largest size of an antichain in

this is the projective-geometry analog, or q-analog, of Sperner's theorem.

They further proved that the largest size of an r-chain-free family in

is the sum of the r largest Gaussian coefficients.

Their proof is by a projective analog of the LYM inequality.

Beck & Zaslavsky (2003) obtained a Meshalkin-like generalization of the Rota–Harper theorem.

The theorem is that a family of Meshalkin sequences of length p in PG(d, Fq), such that the subspaces appearing in position i of the sequences contain no chain of length r for each

) denotes the p-Gaussian coefficient and the second elementary symmetric function of the numbers