In 1932 Karol Borsuk showed that an ordinary 3-dimensional ball in Euclidean space can be easily dissected into 4 solids, each of which has a smaller diameter than the ball, and generally d-dimensional ball can be covered with d + 1 compact sets of diameters smaller than the ball. At the same time he proved that d subsets are not enough in general. The proof is based on the Borsuk–Ulam theorem. That led Borsuk to a general question:
- Die folgende Frage bleibt offen: Lässt sich jede beschränkte Teilmenge E des Raumes in (n + 1) Mengen zerlegen, von denen jede einen kleineren Durchmesser als E hat?
This can be translated as:
- The following question remains open: Can every bounded subset E of the space be partitioned into (n + 1) sets, each of which has a smaller diameter than E?
The question got a positive answer in the following cases:
- d = 2 — which is the original result by Karol Borsuk (1932).
- d = 3 — shown by Julian Perkal (1947), and independently, 8 years later, by H. G. Eggleston (1955). A simple proof was found later by Branko Grünbaum and Aladár Heppes.
- For all d for the smooth convex bodies — shown by Hugo Hadwiger (1946).
- For all d for centrally-symmetric bodies — shown by A.S. Riesling (1971).
- For all d for bodies of revolution — shown by Boris Dekster (1995).
The problem was finally solved in 1993 by Jeff Kahn and Gil Kalai, who showed that the general answer to Borsuk's question is no. Their construction shows that d + 1 pieces do not suffice for d = 1,325 and for each d > 2,014.
Apart from finding the minimum number d of dimensions such that the number of pieces mathematicians are interested in finding the general behavior of the function . Kahn and Kalai show that in general (that is for d big enough), one needs number of pieces. They also quote the upper bound by Oded Schramm, who showed that for every ε, if d is sufficiently large, . The correct order of magnitude of α(d) is still unknown. However, it is conjectured that there is a constant c > 1 such that for all d ≥ 1.
- Hadwiger's conjecture on covering convex bodies with smaller copies of themselves
- As Hinrichs and Richter say in the introduction to their work, the “Borsuk's conjecture [was] believed by many to be true for some decades” (hence commonly called 'a conjecture') so “it came as a surprise when Kahn and Kalai constructed finite sets showing the contrary”. It's worth noting, however, that Karol Borsuk has formulated the problem just as a question, not suggesting the expected answer would be positive.
- Hinrichs, Aicke; Richter, Christian (28 August 2003). "New sets with large Borsuk numbers". Discrete Mathematics. Elsevier. 270 (1–3): 137–147. doi:10.1016/S0012-365X(02)00833-6.
- Borsuk, Karol (1933), "Drei Sätze über die n-dimensionale euklidische Sphäre" (PDF), Fundamenta Mathematicae (in German), 20: 177–190
- Perkal, Julian (1947), "Sur la subdivision des ensembles en parties de diamètre inférieur", Colloquium Mathematicum, 2: 45
- Eggleston, H. G. (1955), "Covering a three-dimensional set with sets of smaller diameter", Journal of the London Mathematical Society, 30: 11–24, doi:10.1112/jlms/s1-30.1.11, MR 0067473
- Hadwiger, Hugo (1945), "Überdeckung einer Menge durch Mengen kleineren Durchmessers", Commentarii Mathematici Helvetici, 18 (1): 73–75, doi:10.1007/BF02568103, MR 0013901
- Hadwiger, Hugo (1946), "Mitteilung betreffend meine Note: Überdeckung einer Menge durch Mengen kleineren Durchmessers", Commentarii Mathematici Helvetici, 19 (1): 72–73, doi:10.1007/BF02565947, MR 0017515
- Riesling, A. S. (1971), "Borsuk's problem in three-dimensional spaces of constant curvature" (PDF), Ukr. Geom. Sbornik (in Russian), Kharkov State University (now National University of Kharkiv), 11: 78–83
- Dekster, Boris (1995), "The Borsuk conjecture holds for bodies of revolution", Journal of Geometry, 52 (1-2): 64–73, doi:10.1007/BF01406827, MR 1317256
- Kahn, Jeff; Kalai, Gil (1993), "A counterexample to Borsuk's conjecture", Bulletin of the American Mathematical Society, 29 (1): 60–62, arXiv: , doi:10.1090/S0273-0979-1993-00398-7, MR 1193538
- Bondarenko, Andriy V. (2013), On Borsuk’s conjecture for two-distance sets, arXiv:
- Bondarenko, Andriy (2014), "On Borsuk's Conjecture for Two-Distance Sets", Discrete & Computational Geometry, 51 (3): 509–515, doi:10.1007/s00454-014-9579-4, MR 3201240
- Jenrich, Thomas (2013), A 64-dimensional two-distance counterexample to Borsuk's conjecture, arXiv:
- Jenrich, Thomas; Brouwer, Andries E. (2014), "A 64-Dimensional Counterexample to Borsuk's Conjecture", Electronic Journal of Combinatorics, 21 (4): #P4.29, MR 3292266
- Schramm, Oded (1988), "Illuminating sets of constant width", Mathematika, 35 (2): 180–189, doi:10.1112/S0025579300015175, MR 0986627
- Alon, Noga (2002), "Discrete mathematics: methods and challenges", Proceedings of the International Congress of Mathematicians, Beijing, 1: 119–135, arXiv:
- Oleg Pikhurko, Algebraic Methods in Combinatorics, course notes.
- Andrei M. Raigorodskii, The Borsuk partition problem: the seventieth anniversary, Mathematical Intelligencer 26 (2004), no. 3, 4–12.
- Raigorodskii, Andreii M. (2008). "Three lectures on the Borsuk partition problem". In Young, Nicholas; Choi, Yemon. Surveys in contemporary mathematics. London Mathematical Society Lecture Note Series. 347. Cambridge University Press. pp. 202–247. ISBN 978-0-521-70564-6. Zbl 1144.52005.