Radon’s Theorem

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.

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

3 Responses to Radon’s Theorem

  1. Pingback: Colorful Caratheodory Theorem | Math by Matt

  2. Pingback: Tverberg’s Theorem (and a Bit of Tensor Products) | Math by Matt

  3. Pingback: Helly’s Theorem and Applications | Math by Matt

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s