= Solution
For each $d$-element coordinate set $J\subseteq\{1,\ldots,p\}$, let $\mathcal G_J$ contain the lower orthants whose finite thresholds occur precisely in the coordinates in $J$. Ignoring the remaining coordinates identifies $\mathcal G_J$ with the lower-orthant class in $\mathbb R^d$, so part (a) gives $\operatorname{VC}(\mathcal G_J)=d$. Moreover,
$$
\mathcal G=\bigcup_{|J|=d}\mathcal G_J
$$
is a union of $r=\binom pd$ such classes. Part (c) and $\binom pd\leq p^d$ give
$$
\begin{aligned}
\operatorname{VC}(\mathcal G)
&\leq4d\log_2(2d)+2\log_2\binom pd\\
&\leq4d\log_2(2d)+2d\log_2p\\
&=\boxed{2d\{2\log_2(2d)+\log_2p\}}.
\end{aligned}
$$
Back to article page
