## 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}

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.