Past exam of the computer science course of the University of Oxford / 2015 / Computational learning theory / 1 / d / ii / Solution

For $d\ge 1$, take the $d+1$ vertices $v_0,\dots ,v_d$ of a regular simplex in ${\mathbb{R}}^d$, centered at zero and scaled so that $\Vert v_j\Vert =1$. For example, realize them asin the $d$-dimensional vector subspace $\{z\in {\mathbb{R}}^{d+1}:{\sum }_j{z}_j=0\}$, identified isometrically with ${\mathbb{R}}^d$. These vertices are affinely independent.

Assign arbitrary desired signs $s_j\in \{-1,1\}$, positive for inclusion. Affine independence implies that there is an affine function $\ell (x)=a\cdot x+b$ with $\ell (v_j)=s_j$ for every $j$: the $d+1$ interpolation conditions form an invertible linear system. For a sufficiently small $\eta >0$, chooseAt every vertex,Thus the Euclidean ball contains exactly the positively labelled vertices, with none on its boundary. This construction also covers the all-positive and all-negative labellings. Therefore