Sperner’s Theorem

Section 2.1 Sperner’s Theorem

We begin with a basic definition coming from the fact that \(\subseteq\) is a partial order.

“Boolean lattice.”

Definition 2.1.1.

A collection \(\mathcal{A}\subseteq 2^{[n]}\) is an antichain if there does not exist \(A,B\in\mathcal{A}\) such that \(A\subsetneq B\text{.}\) (More generally, an antichain is a set of pairwise incomparable elements in a partially ordered set).

Note that some people (especially matroid theorists) use the word clutter instead of antichain.

Example 2.1.2.

An example of an antichain in \(2^{[5]}\) is

\begin{equation*} \mathcal{F} = \{\{1\},\{2,3\},\{2,4\},\{3,4,5\}\}\text{.} \end{equation*}

As you can check, there does not exist two distinct sets \(A,B\in\mathcal{F}\) such that \(A\subseteq B\text{.}\)

Our goal is to determine the cardinality of the largest antichain in \(2^{[n]}\text{.}\) Let us start with a simple example.

Figure 2.1.3. The collection \(\{\{1,2,4\},\{2,3,5,6\},\{5,6,7\}\}\) on the left is an antichain in \(2^{[7]}\) because no set in the collection is contained in another set in the collection. The collection \(\{\{1,2,3,4,5\},\{3,5,6,7\},\{3,6,7\}\}\) on the right is not an antichain in \(2^{[7]}\) because \(\{3,6,7\}\subseteq\{3,5,6,7\}\text{.}\)

Example 2.1.4.

If \(A\) and \(B\) are sets of the same cardinality, then it cannot hold that \(A\subsetneq B\text{.}\) Consequently, \(\binom{[n]}{k}\) is an antichain in \(2^{[n]}\) for every \(0\leq k\leq n\text{.}\)

So, for every \(0\leq k\leq n\text{,}\) there exists an antichain in \(2^{[n]}\) of cardinality \(\binom{n}{k}\text{.}\) The largest possible antichain of this particular type is achieved when \(k=\lfloor n/2\rfloor\) or, equivalently, when \(k=\lceil n/2\rceil\text{.}\)

Observation 2.1.5.

There exists an antichain \(\mathcal{A}\subseteq 2^{[n]}\) such that \(|\mathcal{A}|=\binom{n}{\lfloor n/2\rfloor}\text{.}\)

The following theorem, known as Sperner’s Theorem, asserts that the construction in Example 2.1.4 with \(k=\lfloor n/2\rfloor\) or \(k=\lceil n/2\rceil\) is, in fact, the largest possible in \(2^{[n]}\text{.}\) We state the theorem now and prove it later in this section.

Theorem 2.1.6. Sperner’s Theorem.

If \(\mathcal{A}\subseteq 2^{[n]}\) is an antichain, then

\begin{equation*} |\mathcal{A}|\leq \binom{n}{\lfloor n/2\rfloor}\text{.} \end{equation*}

Remark 2.1.7.

Antichains in \(2^{[n]}\) are often called Sperner families or Sperner systems in honour of Sperner’s Theorem [36] p. 10.

There are many different proofs of Sperner’s Theorem. Here, we provide an another proof which involves recursively constructing a so called “symmetric chain decomposition.” Another proof involving analyzing a random chain will be presented later in this chapter. A third approach is to use Hall’s Theorem on systems of distinct representatives (or, equivalently, matchings in bipartite graphs), which is not covered in this course.

Definition 2.1.8.

Say that a collection \(\mathcal{C}\subseteq 2^{[n]}\) is a chain if either \(A\subseteq B\) or \(B\subseteq A\) for every pair \(A,B\in \mathcal{C}\text{.}\) (More generally, a chain is a set of pairwise comparable elements in a partially ordered set).

As the names would suggest, an antichain is the “antithesis” of an chain.

However, note that the statement “\(\mathcal{F}\) is a an antichain” is not equivalent to the statement “\(\mathcal{F}\) is not a chain.” There are many set systems which are neither chains nor antichains. Also, if \(|\mathcal{F}|\leq 1\text{,}\) then \(\mathcal{F}\) is both a chain and an antichain.

Example 2.1.9.

Let \(n=5\) and consider the collection

\begin{equation*} \mathcal{F}=\{\emptyset, \{1\}, \{1,4\}, \{1,2,4,5\}\}\text{.} \end{equation*}

It is easy to check that \(\mathcal{F}\) is a chain in \(2^{[5]}\text{.}\)

Figure 2.1.10. The chain in Example 2.1.9 (the empty set is depicted in red in the picture on the left).

Observation 2.1.11.

If \(\mathcal{A},\mathcal{C}\subseteq 2^{[n]}\) such that \(\mathcal{A}\) is an antichain and \(\mathcal{C}\) is a chain, then \(|\mathcal{A}\cap \mathcal{C}|\leq 1\text{.}\)

Proof.

Suppose that \(A\) and \(B\) are distinct elements of \(\mathcal{A}\cap \mathcal{C}\text{.}\) Since they are both in \(\mathcal{C}\text{,}\) we have either \(A\subseteq B\) or \(B\subseteq A\text{.}\) However, this contradicts the fact that they are both in \(\mathcal{A}\text{.}\)

Definition 2.1.12.

A symmetric chain is a chain \(\mathcal{C}\subseteq 2^{[n]}\) such that \(\mathcal{C}\) contains a set of every cardinality \(i\in \{k,k+1,\dots,n-k-1,n-k\}\) for some \(0\leq k\leq n/2\text{.}\)

In other words, a symmetric chain is a collection \(\mathcal{C}=\{X_k,X_{k+1},\dots, X_{n-k}\}\) of subsets of \([n]\) such that \(|X_k|=k\) and, for each \(k+1\leq i\leq n-k\text{,}\) the set \(X_i\) has the form \(X_{i-1}\cup \{x\}\) where \(x\) is an element of \([n]\setminus X_{i-1}\text{.}\)

Example 2.1.13.

The family in Example 2.1.9 is not a symmetric chain in \(2^{[5]}\) as it contains the empty set, which has cardinality zero, but it does not contain a set of cardinality three or five. The following is an example of a symmetric chain, when viewed in \(2^{[5]}\text{:}\)

\begin{equation*} \{\{2\},\{2,5\},\{1,2,5\},\{1,2,4,5\}\}\text{.} \end{equation*}

Figure 2.1.14. The symmetric chain in Example 2.1.13.

Definition 2.1.15.

A symmetric chain decomposition of \(2^{[n]}\) is a partition of \(2^{[n]}\) into symmetric chains.

Figure 2.1.16. An “artist’s rendition” of a symmetric chain decomposition. The (roughly) diamond-shaped blob is meant to represent \(2^{[n]}\) and each of the dark green wiggly lines is a symmetric chain. Some of the symmetric chains have only one element and are drawn as single points.

Sperner’s Theorem will follow, almost immediately, from the following lemma.

Lemma 2.1.17.

\(2^{[n]}\) has a symmetric chain decomposition.

Proof.

We proceed by induction on \(n\text{.}\) In the base case \(n=1\text{,}\) \(2^{[n]}\) itself is a symmetric chain.

Now, suppose that \(n\geq2\) and, using the inductive hypothesis, let \(\mathcal{C}_1,\mathcal{C}_2,\dots,\mathcal{C}_N\) be a collection of symmetric chains in \(2^{[n-1]}\) which partition it. For each \(m\) such that \(1\leq m\leq N\text{,}\) let

\begin{equation*} k_m:=\min\{|A|: A\in \mathcal{C}_m\} \end{equation*}

and write \(\mathcal{C}_m=\{X_{m}^i: k_m\leq i\leq n-1-k_m\}\) where

\begin{equation*} X_{m}^{k_m}\subseteq X_{m}^{k_m+1}\subseteq\cdots\subseteq X_{m}^{n-1-k_m} \end{equation*}

and

\begin{equation*} |X_{m}^i|=i\text{.} \end{equation*}

For each \(1\leq m\leq N\text{,}\) define

\begin{equation*} \mathcal{C}_m':=\{X_{m}^{k_m},X_{m}^{k_m+1},\dots,X_{m}^{n-1-k_m},X_{m}^{n-1-k_m}\cup\{n\}\}\text{ and } \end{equation*}

\begin{equation*} \mathcal{C}_m'':=\{X_{m}^{k_m}\cup\{n\},X_{m}^{k_m+1}\cup\{n\},\dots,X_{m}^{n-2-k_m}\cup\{n\}\}\text{.} \end{equation*}

Each of the collections \(\mathcal{C}_m'\) and \(\mathcal{C}_m''\) is a symmetric chain in \(2^{[n]}\) and every element of \(2^{[n]}\) is contained in exactly one of \(\mathcal{C}_1',\dots,\mathcal{C}_N',\mathcal{C}_1'',\dots,\mathcal{C}_N''\) (see Exercise 2). This completes the proof.

We now present a proof of Sperner’s Theorem (Theorem 2.1.6).

Proof of Theorem 2.1.6.

Using Lemma 2.1.17, we let \(\mathcal{C}_1,\dots,\mathcal{C}_N\) be a symmetric chain decomposition of \(2^{[n]}\text{.}\)

By definition of symmetric chain, each collection \(\mathcal{C}_m\) for \(1\leq m\leq N\) must contain an element of \(\binom{[n]}{\lfloor n/2\rfloor}\text{.}\) By Observation 2.1.11 and the fact that \(\binom{[n]}{\lfloor n/2\rfloor}\) is an antichain, it can contain at most one such set. Therefore, it contains exactly one. Since \(\mathcal{C}_1,\dots,\mathcal{C}_N\) is a partitioning of \(2^{[n]}\) in which every such set contains a unique element of \(\binom{[n]}{\lfloor n/2\rfloor}\text{,}\) it must hold that

\begin{equation*} N = \binom{n}{\lfloor n/2\rfloor}\text{.} \end{equation*}

Now, letting \(\mathcal{A}\) be any antichain in \(2^{[n]}\text{,}\) since \(\mathcal{C}_1,\dots,\mathcal{C}_N\) partitions \(2^{[n]}\text{,}\) we have

\begin{equation*} |\mathcal{A}|= \sum_{m=1}^N|\mathcal{A}\cap \mathcal{C}_m|\text{.} \end{equation*}

By Observation 2.1.11, each of the summands on the right side of this equation is at most one, and so \(|\mathcal{A}|\leq N = \binom{n}{\lfloor n/2\rfloor}\text{,}\) as desired.

Here are a couple of YouTube videos related to Sperner’s Theorem:

Prev Top Next