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. It is named after Emanuel Sperner, who published it in 1928.
This result is sometimes called Sperner's lemma, but the name "Sperner's lemma" also refers to an unrelated result on coloring triangulations. To differentiate the two results, the result on the size of a Sperner family is now more commonly known as Sperner's theorem.
A family of sets in which none of the sets is a strict subset of another is called a Sperner family, or an antichain of sets, or a clutter. For example, the family of k-element subsets of an n-element set is a Sperner family. No set in this family can contain any of the others, because a containing set has to be strictly bigger than the set it contains, and in this family all sets have equal size. 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. For this choice, the number of sets in the family is
\tbinom{n}{\lfloorn/2\rfloor}
Sperner's theorem states that these examples are the largest possible Sperner families over an n-element set.Formally, the theorem states that,
|S|\le\binom{n}{\lfloorn/2\rfloor},
\lfloorn/2\rfloor
\lceiln/2\rceil
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
\binom{n}{\lfloorn/2\rfloor}
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).
The following proof is due to . Let sk denote the number of k-sets in S. For all 0 ≤ k ≤ n,
{n\choose\lfloor{n/2}\rfloor}\ge{n\choosek}
and, thus,
{sk\over{n\choose\lfloor{n/2}\rfloor}}\le{sk\over{n\choosek}}.
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
n{s | |
\sum | |
k |
\over{n\choose\lfloor{n/2}\rfloor}}\le
n{s | |
\sum | |
k |
\over{n\choosek}}\le1,
which means
|S|=
n | |
\sum | |
k=0 |
sk\le{n\choose\lfloor{n/2}\rfloor}.
This completes the proof of part 1.
To have equality, all the inequalities in the preceding proof must be equalities. Since
{n\choose\lfloor{n/2}\rfloor}={n\choosek}
k=\lfloor{n/2}\rfloor
\lceil{n/2}\rceil,
\lfloor{n/2}\rfloor
\lceil{n/2}\rceil.
For odd n there is more work to do, which we omit here because it is complicated. See, pp. 3–4.
There are several generalizations of Sperner's theorem for subsets of
lP(E),
A chain is a subfamily
\{S0,S1,...,Sr\}\subseteqlP(E)
S0\subsetS1\subset...\subsetSr
\binom{n}{i}
In the set
lP(E)p
(S1,...,Sp)
(T1,...,Tp),
Si\subseteqTi
(S1,...,Sp)
S1,...,Sp
\binom{n}{n1 n2 ... np},
The case p = 2 is Sperner's theorem, because then
S2=E\setminusS1
S1
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
i=1,2,...,p-1
rp-1
In the finite projective geometry PG(d, Fq) of dimension d over a finite field of order q, let
lL(p,Fq)
lL(p,Fq)
\begin{bmatrix}d+1\ k\end{bmatrix};
They further proved that the largest size of an r-chain-free family in
lL(p,Fq)
obtained a Meshalkin-like generalization of the Rota - Harper theorem. In PG(d, Fq), a Meshalkin sequence of length p is a sequence
(A1,\ldots,Ap)
d-p+1
i=1,2,...,p-1,
rp-1
\begin{bmatrix}d+1\ n1 n2 ... np\end{bmatrix}
s2(n1,\ldots,np) | |
q |
,
\begin{bmatrix}d+1\ n1 n2 ... np\end{bmatrix}
d+1=n1+ … +np
\begin{bmatrix}d+1\ n1\end{bmatrix}\begin{bmatrix}d+1-n1\ n2\end{bmatrix} … \begin{bmatrix}d+1-(n1+ … +np-1)\ np\end{bmatrix}
s2(n1,\ldots,np):=n1n2+n1n3+n2n3+n1n4+ … +np-1np,
n1,n2,...,np.