Solution
= Solution
The <shattering coefficient>, also called the <growth function of a hypothesis class>, counts the largest number of labellings obtainable on $m$ inputs:
$$
\boxed{\Pi_H(m)=\sup_{x_1,\ldots,x_m\in X}\left|\{(h(x_1),\ldots,h(x_m)):h\in H\}\right|.}
$$
When $X$ has at least $m$ points, the same value is obtained by maximizing $|\{h|_S:h\in H\}|$ over $m$-point <sets> $S$. Always $\Pi_H(m)\leq2^m$, with equality exactly when some $m$-point <set> is shattered.