# 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)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:

- 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:

- 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:

- The denominator of the sum on the lefthand side is not affected by the variable $k$ and so:

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:

(7)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:

(8)