Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 2 / 30J / a / Solution

A sample $x_{1:n}=(x_1,\dots ,x_n)$ is shattered by $\mathcal{F}$ when every binary labeling is realized:The shattering coefficient and VC dimension are

For the lower orthants in ${\mathbb{R}}^d$, the $d$ points $e_1,\dots ,e_d$ are shattered: to realize a subset $I$, choose $a_j=1$ for $j\in I$ and $a_j=1/2$ otherwise. Conversely, among any $d+1$ points choose, for each coordinate, one point attaining the maximum in that coordinate. At most $d$ points have been chosen, so there is an unchosen point $x$. Any lower orthant containing every chosen coordinate maximizer must contain every sample point, including $x$. It cannot realize the labeling that includes all chosen points and excludes $x$. This proves