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)

\begin{align} \quad \{ w, x \} \quad , \quad \{w, y \} \quad , \quad \{w, z\} \quad , \quad \{x, y \} \quad , \quad \{ x, z \}, \quad , \quad \{y, z \} \end{align}

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)

\begin{align} \quad \{v, w \} \quad , \quad \{v, x \} \quad , \quad \{v, y \} \quad , \quad \{v, z \} \quad , \quad \{w, x \} \\ \quad \{ w, y \} \quad , \quad \{w, z \} \quad , \quad \{ x, y \} \quad , \quad \{x, z \} \quad , \quad \{y, z \} \end{align}

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)

\begin{align} \quad \{v, w, x \} \quad , \quad \{ v, w, y \} \quad , \quad \{ v, w, z \} \quad , \quad \{v, x, y \} \quad , \quad \{v, x, z \} \\ \quad \{v, x, z \} \quad , \quad \{ w, x, y \} \quad , \quad \{w, x, z \} \quad , \quad \{w, y, z \} \quad , \quad \{x, y, z \} \end{align}