 Sauer–Shelah lemma

If $VC(H)=D<\infty$, then $s(H,n)\le {\sum }_{j=0}^D\left(\genfrac{}{}{0ex}{}{n}{j}\right)$.

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.