Past exam of the computer science course of the University of Oxford / 2015 / Computational learning theory / 1 / a / iii

The shattering coefficient, also called the growth function of a hypothesis class, counts the largest number of labellings obtainable on $m$ inputs: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)\le 2^m$, with equality exactly when some $m$-point set is shattered.