Radon’s theorem is a neat result in discrete geometry which makes use of elementary linear algebra to find disjoint subsets $R$ and $B$ of a sufficiently large set $S\subset\mathbb{R}^{d}$ such that the convex hulls of $R$ and $B$ have nonempty intersection. If $S$ is a set with at least $d+2$ points, then we can label some of the points red (those that belong to the set $R$) and some of the points blue (those that belong to the set $B$) such that there exists a point in $\mathbb{R}^{d}$ which can be written as a convex combination of red points and also as a convex combination of blue points.

Before we get to the details, some quick remarks on notation. I will use the notation $\text{co}(x_{1},\cdots,x_{n})$ or $\text{co} E$ to denote the convex hull of points $x_{1},\cdots,x_{n}$ or a set $E$. Also, if $a,b$ are points in an affine space, we denote the line segment between $a$ and $b$ by $[a,b]$.

Theorem (Radon) Let $S\subset\mathbb{R}^{d}$ be a subset containing at least $d+2$ elements. Then there exist disjoint subsets $R\subset S$ and $B\subset S$ such that

$\displaystyle\text{co}(R)\cap\text{co}(B)\neq\emptyset$

Proof. Let $x_{1},\cdots,x_{m}$ be distinct points in $S$, where $m\geq d+2$. We introduce real variables $\gamma_{1},\cdots,\gamma_{m}$, regard $v_{1},\cdots,v_{m}$ as column vectors, and consider the matrix equation

$\displaystyle\begin{bmatrix}v_{1,1}&\cdots&v_{1,m}\\ \vdots&\cdots&\vdots\\v_{d,1}&\cdots&v_{d,m}\\1&\cdots&1\end{bmatrix}\displaystyle\begin{bmatrix}\gamma_{1}\\\vdots\\\gamma_{m}\end{bmatrix}=$ $\displaystyle\begin{bmatrix}0 \\ \vdots\\ 0\end{bmatrix}$

Since $m>d+1$, there does not exist an injection of $\mathbb{R}^{m}$ into $\mathbb{R}^{d}$, which implies that there exists a nontrivial solution to the matrix equation. We abuse notation and denote this solution by the coordinates $\gamma_{1},\cdots,\gamma_{m}$. Define disjoint subsets $R$ and $S$

$\displaystyle R:=\left\{v_{i}:\gamma_{i}>0\right\},\indent B:=\left\{v_{i}:\gamma_{i}<0\right\}$

I claim that $\text{co}(R)\cap\text{co}(B)\neq\emptyset$. Since $\gamma_{1}+\cdots+\gamma_{m}=0$ and all the $\gamma_{i}$ are zero, we see that $\beta:=\sum_{i:\gamma_{i}>0}\gamma_{i}>0$ and $-\beta=\sum_{i:\gamma_{i}<0}\gamma_{i}$. Since $\sum_{i=1}^{m}\gamma_{i}v_{i}=0$, we see that

$\displaystyle\sum_{i:\gamma_{i}>0}\gamma_{i}v_{i}=-\sum_{i:\gamma_{i}<0}\gamma_{i}v_{i}\Longrightarrow v:=\sum_{i:\gamma_{i}>0}\frac{\gamma_{i}}{\beta}v_{i}=\sum_{i:\gamma_{i}<0}\frac{\gamma_{i}}{-\beta}v_{i}$

But we have shown that $v$ can be written as a convex combination of points in $R$ and also as a convex combination of points in $B$, and therefore $v\in\text{co}(R)\cap\text{co}(B)$. $\Box$

I claim that the constant $d+2$ cannot be improved to $d+1$ in Radon’s theorem. Fix $d$, and consider the set $S$ consisting of the origin and the standard basis elements $e_{1},\cdots,e_{d}$ of $\mathbb{R}^{d}$. $S$ has $d+1$ points. Suppose $R$ and $B$ are disjoint nonempty subsets of $S$ with intersecting convex hulls. Since $\left\{j: e_{j}\in R\right\}\cap\left\{j:e_{j}\in B\right\}=\emptyset$, we see that

$\displaystyle(x_{1},\cdots,x_{d})\in\text{co}(R)\Longleftrightarrow x_{i}=0, e_{i}\in B$ and $\displaystyle(x_{1},\cdots,x_{d})\in\text{co}(B)\Longleftrightarrow x_{i}=0,e_{i}\in R$,

which implies that $\text{co}(R)\cap\text{co}(B)=\emptyset$.

To add some concreteness to our discussion of Radon’s theorem, we consider the case $d=2$. Suppose we have a set $S$ consisting of 4 points $x_{1},x_{2},x_{3},x_{4}$ in the plane. Radon’s theorem tells us that there exist nonempty disjoint subsets $R$ and $B$ such that $\text{co}(R)\cap\text{co}(B)$. If $R$ consists of a single point (w.l.o.g.) $x_{1}$. Then $x_{1}$ lies in the interior of the triangle formed by $\text{co}(x_{2},x_{3},x_{4})$. If $R$ consists of two points (w.l.o.g.) $x_{1},x_{2}$, then we have that the line segments $[x_{1},x_{2}]$ and $[x_{3},x_{4}]$ intersect at precisely one point.

This entry was posted in math.CO and tagged , , . Bookmark the permalink.