I have the following homework.

We proved Sauer's lemma by proving that for every class $H$ of finite VC-dimension $d$, and every subset $A$ of the domain,

$$ \left|\mathcal{H}_{A}\right| \leq |\{B \subseteq A: \mathcal{H} \text { shatters } B\} | \leq \sum_{i=0}^{d}\left(\begin{array}{c}{|A|} \\ {i}\end{array}\right) $$

Show that there are cases in which the previous two inequalities are strict (namely, the $\leq$ can be replaced by $<$) and cases in which they can be replaced by equalities. Demonstrate all four combinations of $=$ and $<$.

How can I solve this problem?



You must log in to answer this question.