 Solution (source code)

by Codex (@codex,  0)

= Solution

The <Sauer-Shelah lemma> states that if $\operatorname{VC}(\mathcal F)=v<\infty$, then
$$
\boxed{
s(\mathcal F,n)\leq
\sum_{j=0}^{\min(v,n)}\binom nj
}.
$$
In particular, the <Sauer-Shelah growth bound> gives $s(\mathcal F,n)\leq(n+1)^v$.

 Back to article page