Kirchberger's Theorem

Kirchberger's theorem is a theorem in discrete geometry, on linear separability. The two-dimensional version of the theorem states that, if a finite set of red and blue points in the Euclidean plane has the property that, for every four points, there exists a line separating the red and blue points within those four, then there exists a single line separating all the red points from all the blue points. Donald Watson phrases this result more colorfully, with a farmyard analogy:

More generally, for finitely many red and blue points in $d$-dimensional Euclidean space, if the red and blue points in every subset of $d+2$ of the points are linearly separable, then all the red points and all the blue points are linearly separable. Another equivalent way of stating the result is that, if the convex hulls of finitely many red and blue points have a nonempty intersection, then there exists a subset of $d+2$ points for which the convex hulls of the red and blue points in the subsets also intersect.

History and proofs

The theorem is named after German mathematician Paul Kirchberger, a student of David Hilbert at the University of Göttingen who proved it in his 1902 dissertation, and published it in 1903 in ''Mathematische Annalen'', as an auxiliary theorem used in his analysis of Chebyshev approximation. A report of Hilbert on the dissertation states that some of Kirchberger's auxiliary theorems in this part of his dissertation were known to Hermann Minkowski but unpublished; it is not clear whether this statement applies to the result now known as Kirchberger's theorem.

Since Kirchberger's work, other proofs of Kirchberger's theorem have been published, including simple proofs based on Helly's theorem on intersections of convex sets, based on Carathéodory's theorem on membership in convex hulls, or based on principles related to Radon's theorem on intersections of convex hulls. However, Helly's theorem, Carathéodory's theorem, and Radon's theorem all postdate Kirchberger's theorem.

Generalizations and related results

A strengthened version of Kirchberger's theorem fixes one of the given points, and only considers subsets of $d+2$ points that include the fixed point. If the red and blue points in each of these subsets are linearly separable, then all the red points and all the blue points are linearly separable. The theorem also holds if the red points and blue points form compact sets that are not necessarily finite.

By using stereographic projection, Kirchberger's theorem can be used to prove a similar result for circular or spherical separability: if every five points of finitely many red and blue points in the plane can have their red and blue points separated by a circle, or every $d+3$ points in higher dimensions can have their red and blue points separated by a hypersphere, then all the red and blue points can be separated in the same way.

See also

*Hyperplane separation theorem, the theorem that disjoint compact convex sets are linearly separable

References

Further reading

*
*
*
*
*
*{{citation
, last = Rennie , first = B. C.
, doi = 10.1112/jlms/s2-2.1.40
, journal = Journal of the London Mathematical Society
, mr = 250192
, pages = 40–44
, series = Second Series
, title = A theorem like Kirchberger's
, volume = 2
, year = 1970

Theorems in convex geometry
Theorems in discrete geometry