1.8: Sperner's Theorem

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^{[3]}\), \(\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.