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:

{{quote|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.{{r|watson}}}}

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.{{r|shimrat|webster}}

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,{{r|diss}} and published it in 1903 in Mathematische Annalen,{{r|kirchberger}} 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.{{r|steffens}}

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,{{r|radsch}} based on Carathéodory's theorem on membership in convex hulls,{{r|shimrat}} or based on principles related to Radon's theorem on intersections of convex hulls.{{r|webster}} 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.{{r|watson}} The theorem also holds if the red points and blue points form compact sets that are not necessarily finite.{{r|webster}}

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.{{r|lay}}

References

{{reflist|refs=

{{citation

| last = Kirchberger | first = Paul

| doi = 10.1007/BF01445182

| issue = 4

| journal = Mathematische Annalen

| mr = 1511222

| pages = 509–540

| title = Über Tchebychefsche Annäherungsmethoden

| volume = 57

| year = 1903| s2cid = 120774553

| url = https://zenodo.org/record/2083608

}}

{{citation

| last = Lay | first = S. R.

| doi = 10.2307/2316320

| journal = American Mathematical Monthly

| mr = 300201

| pages = 1112–1113

| title = On separation by spherical surfaces

| volume = 78

| year = 1971| issue = 10

| jstor = 2316320

}}

{{citation

| last1 = Rademacher | first1 = Hans | author1-link = Hans Rademacher

| last2 = Schoenberg | first2 = I. J. | author2-link = Isaac Jacob Schoenberg

| doi = 10.4153/cjm-1950-022-8

| journal = Canadian Journal of Mathematics

| mr = 35044

| pages = 245–256

| title = Helly's theorems on convex domains and Tchebycheff's approximation problem

| volume = 2

| year = 1950| doi-access = free

}}

{{citation

| last = Shimrat | first = Moshe

| journal = Pacific Journal of Mathematics

| mr = 71796

| pages = 361–362

| title = Simple proof of a theorem of P. Kirchberger

| url = https://projecteuclid.org/euclid.pjm/1103044459

| volume = 5

| year = 1955| issue = 3

| doi = 10.2140/pjm.1955.5.361

| doi-access = free

}}

{{citation

| last = Steffens | first = Karl-Georg

| contribution = 4.3 Kirchberger's Thesis

| doi = 10.1007/0-8176-4475-x_4

| location = Boston

| mr = 2190312

| pages = 135–137

| publisher = Birkhäuser

| title = The History of Approximation Theory: From Euler to Bernstein}}

{{citation

| last = Watson | first = Donald

| doi = 10.1017/S1446788700012957

| journal = Australian Mathematical Society

| mr = 0333980

| pages = 190–192

| title = A refinement of theorems of Kirchberger and Carathéodory

| volume = 15

| year = 1973| issue = 2

| doi-access = free

}}

{{citation

| last = Webster | first = R. J.

| doi = 10.1016/0022-247X(83)90286-X

| issue = 1

| journal = Journal of Mathematical Analysis and Applications

| mr = 694178

| pages = 299–300

| title = Another simple proof of Kirchberger's theorem

| volume = 92

| year = 1983| doi-access = free

}}

Kirchberger's theorem

History and proofs

See also

References

Further reading