= Solution
A sample $x_{1:n}=(x_1,\ldots,x_n)$ is shattered by $\mathcal F$ when every binary labeling is realized:
$$
\{(f(x_1),\ldots,f(x_n)):f\in\mathcal F\}=\{0,1\}^n.
$$
The <shattering coefficient> and <VC dimension> are
$$
s(\mathcal F,n)
=\sup_{x_{1:n}\in\mathcal X^n}
\left|\{(f(x_1),\ldots,f(x_n)):f\in\mathcal F\}\right|,
$$
$$
\operatorname{VC}(\mathcal F)
=\sup\{n:s(\mathcal F,n)=2^n\}.
$$
For the lower orthants in $\mathbb R^d$, the $d$ points $e_1,\ldots,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
$$
\boxed{\operatorname{VC}(\mathcal F)=d}.
$$
Back to article page
