Sperner families:

Let \(\mathcal{F}\) be a collection of subsets of \([1,n] \subset \mathbb{N}\). We call \(\mathcal{F}\) a Sperner family if there is no set in \(\mathcal{F}\) that is contained in another one:

\begin{equation} \forall A,B \in \mathcal{F}, \lvert A \cap B \rvert < \min(\lvert A \rvert, \lvert B \rvert) \end{equation}

Naturally, we may ask what is the largest Sperner family as a function of \(n\).

Theorem on Sperner families:

For any Sperner family \(\mathcal{F}\) of \([1,n]\),

\begin{equation} \sum_{A \in \mathcal{F}} {n \choose \lvert A \rvert}^{-1} \leq 1 \end{equation}

Proof:

Each subset \(A \in \mathcal{F}\) has probability:

\begin{equation} P_A = \frac{1}{{n \choose \lvert A \rvert}} \end{equation}

since each \(\lvert A \rvert\)-element subset has the same chance of occurring.

However, no two subsets can appear in the same chain so the events are disjoint and therefore:

\begin{equation} \sum_{A \in \mathcal{F}} P_A = \sum_{A \in \mathcal{F}} {n \choose \lvert A \rvert}^{-1} \leq 1 \end{equation}

Sperner’s theorem as a corollary:

Since we have:

\begin{equation} \log |F| \leq \max_{A \in \mathcal{F}} - \log P_A \end{equation}

\begin{equation} \forall A \in \mathcal{F}, P_A \geq {n \choose \lfloor n/2 \rfloor}^{-1} \end{equation}

we may conclude that:

\begin{equation} \lvert F \rvert \leq {n \choose \lfloor n/2 \rfloor} \end{equation}

References:

  1. Alon, Noga; Spencer, Joel H. (2000). The probabilistic method (2ed). New York: Wiley-Interscience. ISBN 0-471-37046-0.
  2. Yufei Zhao. Probabilistic Methods in Combinatorics. MIT. 2020.