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

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

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]$$,

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

## Proof:

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

$$P_A = \frac{1}{{n \choose \lvert A \rvert}}$$

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:

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

## Sperner’s theorem as a corollary:

Since we have:

$$\log |F| \leq \max_{A \in \mathcal{F}} - \log P_A$$

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

we may conclude that:

$$\lvert F \rvert \leq {n \choose \lfloor n/2 \rfloor}$$

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