Radon's theorem

It may form a triple and a singleton, where the convex hull of the triple (a triangle) contains the singleton; alternatively, it may form two pairs of points that form the endpoints of two intersecting line segments.

Then there exists a set of multipliers a1, ..., ad + 2, not all of which are zero, solving the system of linear equations because there are d + 2 unknowns (the multipliers) but only d + 1 equations that they must satisfy (one for each coordinate of the points, together with a final equation requiring the sum of the multipliers to be zero).

form the required partition of the points into two subsets with intersecting convex hulls.

must intersect, because they both contain the point where The left hand side of the formula for

, and the right hand side expresses it as a convex combination of the points in

belongs to both convex hulls, completing the proof.

This proof method allows for the efficient construction of a Radon point, in an amount of time that is polynomial in the dimension, by using Gaussian elimination or other efficient algorithms to solve the system of equations for the multipliers.

An equivalent formulation of Radon's theorem is:If ƒ is any affine function from a (d + 1)-dimensional simplex Δd+1 to Rd, then there are two disjoint faces of Δd+1 whose images under ƒ intersect.They are equivalent because any affine function on a simplex is uniquely determined by the images of its vertices.

can be partitioned into two disjoint subsets, e.g. (xi)i in I and (xj)j in J, with overlapping convex hull.

Because f is affine, the convex hull of (xi)i in I is the image of the face spanned by the vertices (vi)i in I, and similarly the convex hull of (xj)j in J is the image of the face spanned by the vertices (vj)j in j.

These two faces are disjoint, and their images under f intersect - as claimed by the new formulation.

The topological Radon theorem generalizes this formluation.

It allows f to be any continuous function - not necessarily affine:[2]If ƒ is any continuous function from a (d + 1)-dimensional simplex Δd+1 to Rd, then there are two disjoint faces of Δd+1 whose images under ƒ intersect.More generally, if K is any (d + 1)-dimensional compact convex set, and ƒ is any continuous function from K to d-dimensional space, then there exists a linear function g such that some point where g achieves its maximum value and some other point where g achieves its minimum value are mapped by ƒ to the same point.

In the case where K is a simplex, the two simplex faces formed by the maximum and minimum points of g must then be two disjoint faces whose images have a nonempty intersection.

This same general statement, when applied to a hypersphere instead of a simplex, gives the Borsuk–Ulam theorem, that ƒ must map two opposite points of the sphere to the same point.

[2] The topological Radon theorem was originally proved by Ervin Bajmóczy and Imre Bárány[2] in the following way: Another proof was given by László Lovász and Alexander Schrijver.

[5][6] Radon's theorem forms a key step of a standard proof of Helly's theorem on intersections of convex sets;[7] this proof was the motivation for Radon's original discovery of Radon's theorem.

Radon's theorem can also be used to calculate the VC dimension of d-dimensional points with respect to linear separations.

There exist sets of d + 1 points (for instance, the points of a regular simplex) such that every two nonempty subsets can be separated from each other by a hyperplane.

However, no matter which set of d + 2 points is given, the two subsets of a Radon partition cannot be linearly separated.

One proof of Carathéodory's theorem uses a technique of examining solutions to systems of linear equations, similar to the proof of Radon's theorem, to eliminate one point at a time until at most d + 1 remain.

In this more general context, the convex hull of a set S is the intersection of the family members that contain S, and the Radon number of a space is the smallest r such that any r points have two subsets whose convex hulls intersect.

With this definition, every set of ω + 1 vertices in the graph can be partitioned into two subsets whose convex hulls intersect, and ω + 1 is the minimum number for which this is possible, where ω is the clique number of the given graph.