 Solution

For a binary function class $\mathcal{F}$, the shattering coefficient isIts VC dimension is the largest $n$ for which $s(\mathcal{F},n)=2^n$, with value infinity if there is no largest such $n$. The Sauer-Shelah lemma states that, when $\mathrm{VC}(\mathcal{F})=d<\infty$,