$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 1.8: Sperner's Theorem

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

The binomial coefficients count the subsets of a given set; the sets themselves are worth looking at. First some convenient notation:

Definition $$\PageIndex{1}$$

Let $$[n]=\{1,2,3,\ldots,n\}$$. Then $$\displaystyle 2^{[n]}$$ denotes the set of all subsets of $$[n]$$, and $$\left[\begin{array}{c}n\\k\end{array}\right]$$ denotes the set of subsets of $$[n]$$ of size $$k$$.

Example $$\PageIndex{1}$$

Let $$n=3$$. Then \eqalign{ \left[\begin{array}{c}n\\0\end{array}\right]&=\{\emptyset\}\cr \left[\begin{array}{c}n\\1\end{array}\right]&=\{\{1\},\{2\},\{3\}\}\cr \left[\begin{array}{c}n\\2\end{array}\right]&=\{\{1,2\},\{1,3\},\{2,3\}\}\cr \left[\begin{array}{c}n\\3\end{array}\right]&=\{\{1,2,3\}\}\cr }\nonumber

Definition $$\PageIndex{2}$$: Chain

A chain in $$\displaystyle 2^{[n]}$$ is a set of subsets of $$\displaystyle 2^{[n]}$$ that are linearly ordered by inclusion. An anti-chain in $$\displaystyle 2^{[n]}$$ is a set of subsets of $$\displaystyle 2^{[n]}$$ that are pairwise incomparable.

Example $$\PageIndex{2}$$

In $$\displaystyle 2^{}$$, $$\displaystyle \{ \emptyset,\{1\},\{1,2,3\} \}$$ is a chain, because $$\displaystyle \emptyset\subseteq \{1\}\subseteq \{1,2,3\}$$. Every $$\left[\begin{array}{c}n\\k\end{array}\right]$$ is an anti-chain, as is $$\displaystyle \{ \{1\},\{2,3\} \}$$. The set $$\displaystyle \{ \{1\},\{1,3\},\{2,3\} \}$$ is neither a chain nor an anti-chain.

Because of Theorem 1.4.3 we know that among all anti-chains of the form $$\left[\begin{array}{c}n\\k\end{array}\right]$$ the largest are the "middle'' ones, namely $$\left[\begin{array}{c}n\\ \lfloor n/2\rfloor\end{array}\right]$$ and $$\left[\begin{array}{c}n \\ \lceil n/2\rceil\end{array}\right]$$ (which are the same if $$n$$ is even). Remarkably, these are the largest of all anti-chains, that is, strictly larger than every other anti-chain. When $$n=3$$, the anti-chains $$\left[\begin{array}{c}3\\1\end{array}\right]$$ and $$\left[\begin{array}{c}3\\2\end{array}\right]$$ are the only anti-chains of size 3, and no anti-chain is larger, as you can verify by examining all possibilities.

Before we prove this, a bit of notation.

Definition $$\PageIndex{3}$$: Permutation

If $$\sigma\colon A\to A$$ is a bijection, then $$\sigma$$ is called a permutation.

This use of the word permutation is different than our previous usage, but the two are closely related. Consider such a function $$\sigma\colon [n]\to[n]$$. Since the set $$A$$ in this case is finite, we could in principle list every value of $$\sigma$$:

$\sigma(1),\sigma(2),\sigma(3),\ldots,\sigma(n).\nonumber$

This is a list of the numbers $$\{1,\ldots,n\}$$ in some order, namely, this is a permutation according to our previous usage. We can continue to use the same word for both ideas, relying on context or an explicit statement to indicate which we mean.

Theorem $$\PageIndex{1}$$: Sperner's Theorem

The only anti-chains of largest size are $$\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]$$ and $$\left[\begin{array}{c} n \\ \lceil n/2\rceil\end{array}\right]$$.

Proof

First we show that no anti-chain is larger than these two. We attempt to partition $$\displaystyle 2^{[n]}$$ into $$k={n\choose \lfloor n/2\rfloor}$$ chains, that is, to find chains \eqalign{ &A_{1,0}\subseteq A_{1,1}\subseteq A_{1,2}\subseteq\cdots\subseteq A_{1,m_1}\cr &A_{2,0}\subseteq A_{2,1}\subseteq A_{2,2}\subseteq\cdots\subseteq A_{2,m_2}\cr &\vdots\cr &A_{k,0}\subseteq A_{k,1}\subseteq A_{k,2}\subseteq\cdots\subseteq A_{k,m_k}\cr }\nonumber so that every subset of $$[n]$$ appears exactly once as one of the $$\displaystyle A_{i,j}$$. If we can find such a partition, then since no two elements of an anti-chain can be in the same chain, no anti-chain can have more than $$k$$ elements.

For small values of $$n$$ this can be done by hand; for $$n=3$$ we have \eqalign{ &\emptyset\subseteq\{1\}\subseteq\{1,2\}\subseteq\{1,2,3\}\cr &\{2\}\subseteq\{2,3\}\cr &\{3\}\subseteq\{1,3\}\cr }\nonumber

These small cases form the base of an induction. We will prove that any $$\displaystyle 2^{[n]}$$ can be partitioned into such chains with two additional properties:

1. Each set in a chain contains exactly one element more than the next smallest set in the chain.
2. The sum of the sizes of the smallest and largest element in the chain is $$n$$.

Note that the chains for the case $$n=3$$ have both of these properties. The two properties taken together imply that every chain "crosses the middle'', that is, every chain contains an element of $$\left[\begin{array}{c}n \\ n/2\end{array}\right]$$ if $$n$$ is even, and an element of both $$\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]$$ and $$\left[\begin{array}{c}n \\ \lceil n/2\rceil\end{array}\right]$$ if $$n$$ is odd. Thus, if we succeed in showing that such chain partitions exist, there will be exactly $$n\choose \lfloor n/2\rfloor$$ chains.

For the induction step, we assume that we have partitioned $$\displaystyle 2^{[n-1]}$$ into such chains, and construct chains for $$\displaystyle 2^{[n]}$$.

First, for each chain $$A_{i,0}\subseteq A_{i,1}\subseteq\cdots\subseteq A_{i,m_i}$$ we form a new chain $$A_{i,0}\subseteq A_{i,1}\subseteq\cdots\subseteq A_{i,m_i}\subseteq A_{i,m_i}\cup \{n\}$$. Since $$|A_{i,0}|+|A_{i,m_i}|=n-1$$, $$|A_{i,0}|+|A_{i,m_i}\cup \{n\}|=n$$, so this new chain satisfies properties (1) and (2).

In addition, if $$m_i>0$$, we form a new new chain $$A_{i,0}\cup \{n\}\subseteq A_{i,1}\cup \{n\}\subseteq\cdots\subseteq A_{i,m_i-1}\cup \{n\}$$. Now \eqalign{ |A_{i,0}\cup \{n\}|+|A_{i,m_i-1}\cup \{n\}|&= |A_{i,0}|+1+|A_{i,m_i-1}|+1\cr &=|A_{i,0}|+1+|A_{i,m_i}|-1 +1\cr &=n-1+1=n\cr }\nonumber so again properties (1) and (2) are satisfied.

Because of the first type of chain, all subsets of $$[n-1]$$ are contained exactly once in the new set of chains. Also, we have added the element $$n$$ exactly once to every subset of $$[n-1]$$, so we have included every subset of $$[n]$$ containing $$n$$ exactly once. Thus we have produced the desired partition of $$\displaystyle 2^{[n]}$$.

Now we need to show that the only largest anti-chains are $$\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]$$ and $$\left[\begin{array}{c}n \\ \lceil n/2\rceil\end{array}\right]$$.

Suppose that $$A_1,A_2,…,A_m$$ is an anti-chain; then $$A_1^c,A_2^c,…,A_m^c$$ is also an anti-chain, where $$A^c$$ denotes the complement of $$A$$. Thus, if there is an anti-chain that contains some $$A$$ with $$|A|>\lceil n/2\rceil$$, there is also one containing $$A^c$$, and $$|A^c|< \lfloor n/2\rfloor$$. Suppose that some anti-chain contains a set $$A$$ with $$|A|< \lfloor n/2\rfloor$$. We next prove that this anti-chain cannot be of maximum size.

Partition $$\displaystyle 2^{[n]}$$ as in the first part of the proof. Suppose that $$A$$ is a subset of the elements of a one or two element chain $$C$$, that is, a chain consisting solely of a set $$S_1$$ of size $$n/2$$, if $$n$$ is even, or of sets $$S_1$$ and $$S_2$$ of sizes $$\lfloor n/2\rfloor$$ and $$\lceil n/2\rceil$$, with $$A\subseteq S_1\subseteq S_2$$, if $$n$$ is odd. Then no member of $$C$$ is in the anti-chain. Thus, the largest possible size for an anti-chain containing $$A$$ is $${n\choose \lfloor n/2\rfloor}-1$$.

If $$A$$ is not a subset of the elements of such a short chain, we now prove that there is another chain partition of $$\displaystyle 2^{[n]}$$ that does have this property. Note that in the original chain partition there must be a chain of length 1 or 2, $$C_1$$, consisting of $$S_1$$ and possibly $$S_2$$; if not, every chain would contain a set of size $$\lfloor n/2\rfloor -1$$, but there are not enough such sets to go around. Suppose then that $$A=\{x_1,\ldots,x_k\}$$ and the set $$S_1$$ in $$C_1$$ is $$S_1=\{x_1,\ldots,x_q,y_{q+1},\ldots y_l\}$$, where $$0\le q< k$$ and $$l>k$$.

Let $$\sigma$$ be the permutation of $$[n]$$ such that $$\sigma(x_{q+i})=y_{q+i}$$ and $$\sigma(y_{q+i})=x_{q+i}$$, for $$1\le i\le k-q$$, and $$\sigma$$ fixes all other elements. Now for $$U\subseteq [n]$$, let $$\overline U=\sigma(U)$$, and note that $$U\subseteq V$$ if and only if $$\overline U\subseteq\overline V$$. Thus every chain in the original chain partition maps to a chain. Since $$\sigma$$ is a bijection, these new chains also form a partition of $$\displaystyle 2^{[n]}$$, with the additional properties (1) and (2). By the definition of $$\sigma$$, $$A\subseteq\overline S_1$$, and $$\{\overline S_1,\overline S_2\}$$ is a chain, say $$\overline C_1$$. Thus, this new chain partition has the desired property: $$A$$ is a subset of every element of the 1 or 2 element chain $$\overline C_1$$, so $$A$$ is not in an anti-chain of maximum size.

Finally, we need to show that if $$n$$ is odd, no anti-chain of maximum size contains sets in both $$\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]$$ and $$\left[\begin{array}{c}n\\ \lceil n/2\rceil\end{array}\right]$$. Suppose there is such an anti-chain, consisting of sets $$A_{k+1},\ldots,A_l$$ in $$\left[\begin{array}{c}n \\ \lceil n/2\rceil\end{array}\right]$$, where $$l={n\choose \lceil n/2\rceil}$$, and $$B_1,\ldots,B_k$$ in $$\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]$$. The remaining sets in $$\left[\begin{array}{c}n\\ \lceil n/2\rceil\end{array}\right]$$ are $$A_1,\ldots,A_k$$, and the remaining sets in $$\left[\begin{array}{c}n\\ \lfloor n/2\rfloor\end{array}\right]$$ are $$B_{k+1},\ldots,B_l$$.

Each set $$B_i$$, $$1\le i\le k$$, is contained in exactly $$\lceil n/2\rceil$$ sets in $$\left[\begin{array}{c}n \\ \lceil n/2\rceil\end{array}\right]$$, and all must be among $$A_1,\ldots,A_k$$. On average, then, each $$A_i$$, $$1\le i\le k$$, contains $$\lceil n/2\rceil$$ sets among $$B_1,\ldots,B_k$$. But each set $$A_i$$, $$1\le i\le k$$, contains exactly $$\lceil n/2\rceil$$ sets in $$\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]$$, and so each must contain exactly $$\lceil n/2\rceil$$ of the sets $$B_1,\ldots,B_k$$ and none of the sets $$B_{k+1},\ldots,B_l$$.

Let $$A_1=A_{j_1}=\{x_1,\ldots,x_r\}$$ and $$B_{k+1}=\{x_1,\ldots,x_s,y_{s+1},\ldots,y_{r-1}\}$$. Let $$B_{i_m}=A_{j_m}\backslash\{x_{s+m}\}$$ and $$A_{j_{m+1}}=B_{i_m}\cup\{y_{s+m}\}$$, for $$1\le m\le r-s-1$$. Note that by the preceding discussion, $$1\le i_m\le k$$ and $$1\le j_m\le k$$. Then $$A_{j_{r-s}}=\{x_1,\ldots,x_s,y_{s+1},\ldots,y_{r-1},x_r\}$$, so $$A_{j_{r-s}}\supseteq B_{k+1}$$, a contradiction. Hence there is no such anti-chain.