= Solution
The <Sauer-Shelah lemma> says that a <hypothesis class> of finite <VC dimension> $d$ satisfies
$$
\boxed{\Pi_H(m)\leq\sum_{j=0}^{\min(d,m)}\binom mj.}
$$
In particular, for $m\geq d\geq1$,
$$
\Pi_H(m)\leq\left(\frac{em}{d}\right)^d.
$$
Here the <binomial coefficients> count small subsets. One way to obtain the last inequality is to set $t=d/m\leq1$: since $t^j\geq t^d$ for $j\leq d$,
$$
t^d\sum_{j=0}^d\binom mj\leq\sum_{j=0}^d\binom mjt^j\leq(1+t)^m\leq e^{mt}=e^d.
$$
Thus finite <VC dimension> replaces the unrestricted exponential number of labellings by a polynomial bound in the sample size.
Back to article page
