 Sauer–Shelah lemma

If a binary hypothesis class $\mathcal{H}$ has finite VC dimension $D$, then its shattering coefficient satisfiesThe binomial coefficients bound how many different label patterns the class can realize. For fixed $D$, their sum grows polynomially in $n$, although the number of unrestricted binary patterns is $2^n$.

Here is an inductive counting proof on a fixed sample. Partition the realized patterns according to their last label, and let $F_0,F_1$ be the corresponding sets of patterns on the first $n-1$ points. Put $P=F_0\cup F_1$ and $Q=F_0\cap F_1$. The original number of patterns is $|P|+|Q|$.

The class $P$ has VC dimension at most $D$. The class $Q$ has VC dimension at most $D-1$: if $Q$ shattered $D$ earlier points, both last labels would extend every pattern there, so the original class would have a shattered set of $D+1$ points. Applying mathematical induction and Pascal's identity gives the displayed sum. The base cases are $n=0$, with at most one empty pattern, and $D=0$, with at most one realized pattern.

The Sauer–Shelah lemma is a result in combinatorics and model theory that provides a bound on the size of a family of finite sets that can be shattered by a given number of points. It is named after Sigmund Sauer and Saharon Shelah, who independently discovered it.