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:
If sheep and goats are grazing in a field and for every four animals there exists a line separating the sheep from the goats then there exists such a line for all the animals.[1]
More generally, for finitely many red and blue points in -dimensional Euclidean space, if the red and blue points in every subset of 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 points for which the convex hulls of the red and blue points in the subsets also intersect.[2][3]
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,[4] and published it in 1903 in Mathematische Annalen,[5] 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.[6]
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,[7] based on Carathéodory's theorem on membership in convex hulls,[2] or based on principles related to Radon's theorem on intersections of convex hulls.[3] 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 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.[1] The theorem also holds if the red points and blue points form compact sets that are not necessarily finite.[3]
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 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.[8]
See also
- Hyperplane separation theorem, the theorem that disjoint compact convex sets are linearly separable
References
- ^ a b Watson, Donald (1973), "A refinement of theorems of Kirchberger and Carathéodory", Australian Mathematical Society, 15 (2): 190–192, doi:10.1017/S1446788700012957, MR 0333980
- ^ a b Shimrat, Moshe (1955), "Simple proof of a theorem of P. Kirchberger", Pacific Journal of Mathematics, 5 (3): 361–362, doi:10.2140/pjm.1955.5.361, MR 0071796
- ^ a b c Webster, R. J. (1983), "Another simple proof of Kirchberger's theorem", Journal of Mathematical Analysis and Applications, 92 (1): 299–300, doi:10.1016/0022-247X(83)90286-X, MR 0694178
- ^ Paul Kirchberger at the Mathematics Genealogy Project
- ^ Kirchberger, Paul (1903), "Über Tchebychefsche Annäherungsmethoden", Mathematische Annalen, 57 (4): 509–540, doi:10.1007/BF01445182, MR 1511222, S2CID 120774553
- ^ Steffens, Karl-Georg, "4.3 Kirchberger's Thesis", The History of Approximation Theory: From Euler to Bernstein, Boston: Birkhäuser, pp. 135–137, doi:10.1007/0-8176-4475-x_4, MR 2190312
- ^ Rademacher, Hans; Schoenberg, I. J. (1950), "Helly's theorems on convex domains and Tchebycheff's approximation problem", Canadian Journal of Mathematics, 2: 245–256, doi:10.4153/cjm-1950-022-8, MR 0035044
- ^ Lay, S. R. (1971), "On separation by spherical surfaces", American Mathematical Monthly, 78 (10): 1112–1113, doi:10.2307/2316320, JSTOR 2316320, MR 0300201
Further reading
- Bergold, Helena; Felsner, Stefan; Scheucher, Manfred; Schröder, Felix; Steiner, Raphael (2020), "Topological drawings meet classical theorems from convex geometry", Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization, arXiv:2005.12568
- Houle, Michael E. (1991), "Theorems on the existence of separating surfaces", Discrete & Computational Geometry, 6 (1): 49–56, doi:10.1007/BF02574673, MR 1073072, S2CID 1992810
- Lángi, Zsolt; Naszódi, Márton (2008), "Kirchberger-type theorems for separation by convex domains", Periodica Mathematica Hungarica, 57 (2): 185–196, doi:10.1007/s10998-008-8185-6, MR 2469604, S2CID 15506550
- Netrebin, A. G.; Shashkin, Yu. A. (1985), "Theorems of Kirchberger and Carathéodory type in generalized convexity spaces", Doklady Akademii Nauk SSSR, 283 (5): 1085–1088, MR 0802134
- Rennie, B. C. (1970), "A theorem like Kirchberger's", Journal of the London Mathematical Society, Second Series, 2: 40–44, doi:10.1112/jlms/s2-2.1.40, MR 0250192