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

“Boolean lattice.”

Definition2.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.

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.

Example2.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{.}\)

Observation2.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.

Theorem2.1.6.Sperner’s Theorem.

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

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.

Definition2.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.^{ 1 }

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.

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

Observation2.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{.}\)

Definition2.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{.}\)

Example2.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{:}\)

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

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

Lemma2.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

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

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 is a YouTube video related to Sperner’s Theorem: