Sperner's Antichain Theorem

Sperner's Antichain Theorem

Recall from the Antichains of Subsets of a Set page that if $A$ is an $n$-element set then a collection of subsets $B_1, B_2, ..., B_k$ of $A$ is said to be an antichain if for all $i, j \in \{1, 2, ..., k \}$ where $i \neq j$ we have that $B_i \not \subset B_j$ and $B_i \not \supset B_j$. In other words, none of the subsets in this collection are contained in one another.

Also recall from The Lubell-Yamamoto-Meshalkin Inequality page that if $A$ is a finite $n$-element set and $B$ is a collection of subsets of $A$ that form an antichain and $a_k$ is the number of subsets of $A$ of size $k$ in $B$ then:

(1)
\begin{align} \quad \quad \sum_{k=0}^{n} \frac{a_k}{\binom{n}{k}} \leq 1 \end{align}

We will now prove the famous Sperner's Theorem using the LYM inequality from above.

 Theorem 1 (Sperner's Theorem): If $A$ is a finite $n$-element set and if $B$ is a collection of subsets from $A$ that form an antichain then $\displaystyle{\lvert B \rvert \leq \binom{n}{\left \lfloor \frac{n}{2} \right \rfloor}}$.
• Proof: Let $A$ be a finite $n$-element set and let $B$ be a collection of subsetse from $A$. In general, we note that for any $n \in \{0, 1, 2, ..., \}$ and nonnegative integer $k$ where $0 \leq k \leq n$ we have that:
(2)
\begin{align} \quad \binom{n}{\left \lfloor \frac{n}{2} \right \rfloor} \geq \binom{n}{k} \end{align}
• Let $a_k$ be the number of subsets of $A$ that are in the antichain $B$ whose size is $k$. Then for any $a_k$ we have:
(3)
\begin{align} \quad \frac{a_k}{\binom{n}{\left \lfloor \frac{n}{2} \right \rfloor}} \leq \frac{a_k}{\binom{n}{k}} \end{align}
• Now since $B$ is an antichain of subsets of $A$ we can take the sum from $0$ to $n$ and apply the LYM inequality and get:
(4)
\begin{align} \quad \sum_{k=0}^n \frac{a_k}{\binom{n}{\left \lfloor \frac{n}{2} \right \rfloor}} \leq \sum_{k=0}^{n} \frac{a_k}{\binom{n}{k}} \leq 1 \end{align}
• The denominator of the sum on the lefthand side is not affected by the variable $k$ and so:
(5)
\begin{align} \quad \sum_{k=0}^n \frac{a_k}{\binom{n}{\left \lfloor \frac{n}{2} \right \rfloor}} \leq 1 \\ \quad \sum_{k=0}^n a_k \leq \binom{n}{\left \lfloor \frac{n}{2} \right \rfloor} \\ \quad \lvert B \rvert \leq \binom{n}{\left \lfloor \frac{n}{2} \right \rfloor} \quad \blacksquare \end{align}
 Corollary 1: Let $A$ be a finite $n$-element set. If $n$ is even then the only antichain with the maximum $\binom{n}{\left \lfloor \frac{n}{2} \right \rfloor}$ subsets of $A$ is the collection of all $\frac{n}{2}$-element subsets of $A$. If $n$ is odd then the only antichains with the maximum $\binom{n}{\left \lfloor \frac{n}{2} \right \rfloor}$ subsets of $A$ is the collection of all $\frac{n-1}{2}$-element subsets of $A$ and the collection of all $\frac{n+1}{2}$-element subsets of $A$.

We will not prove Corollary 1 but instead look at some examples.

Consider the set $A = \{w, x, y, z \}$. This set has $n = 4$ elements and so by Corollary 1 we have that the collection of all $\frac{n}{2} = 2$ subsets forms a maximal antichain with $\binom{4}{\left \lfloor \frac{4}{2} \right \rfloor} = \binom{4}{2} = \frac{4!}{2!2!} = 6$ subsets in this antichain and they are namely:

(6)
Now consider the set $A = \{v, w, x, y, z \}$. This set has $n = 5$ elements and so by Corollary 1 we have that the collection of all $\frac{n-1}{2} = 2$ subsets forms a maximal antichain with $\binom{5}{\left \lfloor \frac{5}{2} \right \rfloor} = \binom{5}{2} = \frac{5!}{2! \cdot 3!} = 10$ subsets of $A$ and they are namely:
Furthermore since $n = 5$ is odd, we have that the collection of all $\frac{n+1}{2} = 3$ subsets form a maximal antichain with $\binom{5}{\left \lfloor \frac{5}{2} \right \rfloor} = 10$ subsets of $A$ and they are namely: