Sauer–Shelah lemma

Remarks

A stronger statement holds: every family $\mathcal{F}$ shatters at least $|\mathcal{F}|$ subsets of $X$, where the empty set counts and is shattered by every nonempty family. It is proved by induction on $n$, splitting $\mathcal{F}$ according to a fixed element $x$. If the VC dimension is at most $d$, all shattered sets have at most $d$ elements, which gives the lemma.

The bound is sharp: for $d \le n$, the family of all subsets of $X$ with at most $d$ elements has VC dimension $d$ and exactly $\sum_{i \le d} \binom{n}{i}$ members. For fixed $d$ the bound is a polynomial of degree $d$ in $n$, while $X$ has $2^n$ subsets.

Going deeper

For a student

In learning theory, the lemma bounds the number of ways a class of classifiers with finite VC dimension can label $n$ points. This polynomial growth is the key step in the proof that such classes are learnable from a number of samples that depends on the dimension. In combinatorial geometry it bounds the complexity of set systems such as half-planes, which leads to the existence of small $\varepsilon$-nets.