Sperner's Theorem and the Maximum Size of an Antichain

This article provides a complete breakdown of Sperner's theorem, a foundational result in extremal combinatorics discovered by Emanuel Sperner in 1928. It begins by defining the essential concepts of power sets and antichains, followed by the exact mathematical statement of the theorem. Furthermore, this guide walks through a concrete numerical example to illustrate how the theorem works in practice and concludes with a brief explanation of the LYM inequality, which is the standard method used to prove the theorem.

Essential Definitions: Power Sets and Antichains

To understand Sperner's theorem, you first need to understand the environment in which it operates:

  • Finite Set: A set with a countable number of elements. We usually denote the number of elements as \(n\). For example, the set \(S = \{1, 2, 3\}\) has \(n = 3\) elements.
  • Power Set: The collection of all possible subsets of a set, including the empty set and the set itself. A set with \(n\) elements has a power set containing \(2^n\) subsets.
  • Antichain (or Sperner Family): A specific collection of subsets taken from the power set where no subset in the collection is entirely contained within another subset in the same collection.

If you are asked to pick as many subsets as possible from a power set without ever picking two subsets where one fits inside the other, you are looking for the maximum size of an antichain.

The Statement of Sperner's Theorem

Sperner's theorem gives the exact maximum number of subsets you can include in an antichain.

For a finite set with \(n\) elements, the size of the largest possible antichain is:

\[\binom{n}{\lfloor n/2 \rfloor}\]

In plain English, this notation reads as "\(n\) choose the floor of \(n\) divided by 2." The floor function \(\lfloor n/2 \rfloor\) simply means you divide \(n\) by 2 and round down to the nearest whole number if \(n\) is odd.

The theorem also states that the easiest way to build an antichain of this maximum size is to simply take all subsets that have the exact same size of \(\lfloor n/2 \rfloor\) (or \(\lceil n/2 \rceil\), which is \(n/2\) rounded up). Because all these subsets have the exact same number of elements, it is impossible for one to be contained inside another.

A Concrete Example

Let us apply Sperner's theorem to a set of 4 elements: \(S = \{A, B, C, D\}\). Here, \(n = 4\).

  1. Find the target subset size: Divide \(n\) by 2. Since \(4 / 2 = 2\), we are looking at subsets of size 2.
  2. Calculate the maximum size: We calculate "4 choose 2" using the binomial coefficient formula: \(\frac{4!}{2!(4-2)!} = \frac{24}{2 \times 2} = 6\).

According to Sperner's theorem, the largest antichain you can make from a 4-element set contains 6 subsets. We can easily find this maximum antichain by listing all subsets that contain exactly 2 elements:

\(\{A, B\}, \{A, C\}, \{A, D\}, \{B, C\}, \{B, D\}, \{C, D\}\)

None of these 6 subsets fits inside another. If you try to add any 7th subset from the power set—such as \(\{A\}\) or \(\{A, B, C\}\)—you will break the antichain rule, because \(\{A\}\) fits inside \(\{A, B\}\), and \(\{A, B\}\) fits inside \(\{A, B, C\}\).

How It Is Proven: The LYM Inequality

While Sperner's original 1928 proof involved complex counting arguments, modern mathematics proves the theorem quickly using the Lubell–Yamamoto–Meshalkin (LYM) inequality.

The proof relies on the concept of a "maximal chain," which is a sequence of subsets that grows by one element at a time, starting from the empty set and ending at the full set (for example: \(\emptyset \subset \{A\} \subset \{A, B\} \subset \{A, B, C\}\)).

There are \(n!\) (n factorial) possible maximal chains in an \(n\)-element set. Because a chain consists of subsets that are all contained within one another, an antichain and a maximal chain can share at most one subset.

By counting the fraction of chains that pass through the subsets of an antichain, the LYM inequality proves that the sum of the reciprocals of the binomial coefficients of the subset sizes in an antichain cannot exceed 1. Since the largest binomial coefficient is always in the middle—at \(\binom{n}{\lfloor n/2 \rfloor}\)—making all your subsets this exact middle size maximizes the total number of subsets you can have without exceeding the limit of 1.