# Radon's theorem

I came across Radon's theorem the other day, and found this proof. It must have been discovered before.

Radon's theorem: Any \(d+2\) points in \(R^d\) can be partition into two disjoint sets whose convex hulls intersect.

Proof:

Let these points be \(A=\{a_1,a_2,\ldots,a_{d+2}\}\). Consider the point \(x=\frac{1}{d+2}\sum_{i=1}^{d+2}a_i\). By definition \(x\) is in convex hull of \(A\).

By Caratheodory's theorem, \(x\) can be represented as convex combination of at most \(d+1\) points in \(A\). We then have an equation whose left hand side and right hand side do not cancel each other because one side has \(d+2\) non-zero terms and the other has no more than \(d+1\). Moreover after rearrangement we get a point in \(R^d\) which is the convex combination of two disjoint sets of \(A\).

Q.E.D.

Radon's theorem: Any \(d+2\) points in \(R^d\) can be partition into two disjoint sets whose convex hulls intersect.

Proof:

Let these points be \(A=\{a_1,a_2,\ldots,a_{d+2}\}\). Consider the point \(x=\frac{1}{d+2}\sum_{i=1}^{d+2}a_i\). By definition \(x\) is in convex hull of \(A\).

By Caratheodory's theorem, \(x\) can be represented as convex combination of at most \(d+1\) points in \(A\). We then have an equation whose left hand side and right hand side do not cancel each other because one side has \(d+2\) non-zero terms and the other has no more than \(d+1\). Moreover after rearrangement we get a point in \(R^d\) which is the convex combination of two disjoint sets of \(A\).

Q.E.D.

post by Shen-Fu Tsai