= Solution
Take any $p+1$ points $z_1,ldots,z_{p+1}\in\mathbb R^p$. For each coordinate $j$, choose a point attaining the largest $j$th coordinate. At most $p$ points are chosen, so some point $z_k$ is not among them.
Consider the labeling that assigns $1$ to every chosen coordinate maximizer and $0$ to $z_k$. Any lower orthant
$$
\prod_{j=1}^p(-\infty,a_j]
$$
containing all the chosen points must have $a_j\geq\max_i(z_i)_j$ for every $j$, and hence contains $z_k$ as well. This labeling is impossible. No $p+1$ points are shattered, so
$$
\boxed{VC(H)\leq p.}
$$
This is the <VC dimension bound for lower orthants>.
Back to article page
