Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 1 / 31K / a / iii

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 orthantcontaining all the chosen points must have $a_j\ge {\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, soThis is the VC dimension bound for lower orthants.