Radon's theorem

Remarks

Proof idea: take $d + 2$ points $x_1, \dots, x_{d+2}$ of $X$. The $d + 2$ vectors $(x_i, 1) \in \R^{d+1}$ are linearly dependent, so there are reals $\lambda_i$, not all $0$, with $\sum \lambda_i x_i = 0$ and $\sum \lambda_i = 0$. Let $A$ hold the points with $\lambda_i > 0$ and let $B$ hold the rest, and put $s = \sum_{\lambda_i > 0} \lambda_i > 0$. Then $\sum_{\lambda_i > 0} (\lambda_i / s) x_i = \sum_{\lambda_i \le 0} (-\lambda_i / s) x_i$ is a point of both hulls; the remaining points of $X$ can be added to either part.

Example: take four points in the plane. If one of them lies in the convex hull of the other three, that point against the other three is a Radon partition. Otherwise they are the vertices of a convex quadrilateral, and its two diagonals cross.

The number $d + 2$ is sharp: the $d + 1$ vertices of a simplex in $\R^d$ are affinely independent, and no partition of them has intersecting hulls.

Going deeper

For a student

Radon's theorem is the key step in a short proof of Helly's theorem. It also shows that half-spaces in $\R^d$ have VC dimension at most $d + 1$ in learning theory, since no set of $d + 2$ points can be shattered. Its generalisation to partitions into more than two parts is Tverberg's theorem, and a topological version replaces convex hulls by images of faces of a simplex under continuous maps.