Borsuk's conjecture

From Wikipedia, the free encyclopedia
Jump to: navigation, search
An example of a hexagon cut into three pieces of smaller diameter.

The Borsuk problem in geometry, for historical reasons incorrectly called Borsuk's conjecture, is a question in discrete geometry.


In 1932 Karol Borsuk showed[1] 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 \Bbb R^n in (n + 1) Mengen zerlegen, von denen jede einen kleineren Durchmesser als E hat?[1]

This can be translated as:

The following question remains open: Can every bounded subset E of the space \Bbb R^n 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),[2] and independently, 8 years later, by H. G. Eggleston (1955).[3] 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).[4][5]
  • For all d for centrally-symmetric bodies — shown by A.S. Riesling (1971).[6]
  • For all d for bodies of revolution — shown by Boris Dekster (1995).[7]

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.[8] Their construction shows that d + 1 pieces do not suffice for d = 1,325 and for each d > 2,014.

After Andriy V. Bondarenko had shown that Borsuk’s conjecture is false for all d ≥ 65,[9] the current best bound, due to Thomas Jenrich, is 64.[10][11]

Apart from finding the minimum number d of dimensions such that the number of pieces \alpha(d) > d+1 mathematicians are interested in finding the general behavior of the function \alpha(d). Kahn and Kalai show that in general (that is for d big enough), one needs \alpha(d) \ge (1.2)^\sqrt{d} number of pieces. They also quote the upper bound by Oded Schramm, who showed that for every ε, if d is sufficiently large, \alpha(d) \le \left(\sqrt{3/2} + \varepsilon\right)^d.[12] The correct order of magnitude of α(d) is still unknown.[13] However, it is conjectured that there is a constant c > 1 such that \alpha(d) > c^d for all d ≥ 1.

See also[edit]


  1. ^ a b Borsuk, Karol (1933), "Drei Sätze über die n-dimensionale euklidische Sphäre" (PDF), Fundamenta Mathematicae 20: 177–190 
  2. ^ Perkal, Julian (1947), "Sur la subdivision des ensembles en parties de diamètre inférieur", Colloqium Mathematicum 2: 45 
  3. ^ 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 
  4. ^ Hadwiger, Hugo (1945), "Überdeckung einer Menge durch Mengen kleineren Durchmessers", Commentarii Mathematici Helvetici 18 (1): 73–75, doi:10.1007/BF02568103, MR 0013901 
  5. ^ 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 
  6. ^ Riesling, A. S. (1971), "Borsuk's problem in three-dimensional spaces of constant curvature", Ukr. Geom. Sbornik 11: 78–83 
  7. ^ 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 
  8. ^ Kahn, Jeff; Kalai, Gil (1993), "A counterexample to Borsuk's conjecture", Bulletin of the American Mathematical Society 29 (1): 60–62, arXiv:math/9307229, doi:10.1090/S0273-0979-1993-00398-7, MR 1193538 
  9. ^ Bondarenko, Andriy (2014), "On Borsuk’s Conjecture for Two-Distance Sets", Discrete & Computational Geometry 51 (3): 509–515, arXiv:1305.2584, doi:10.1007/s00454-014-9579-4, MR 3201240 
  10. ^ Jenrich, Thomas (2013), A 64-dimensional two-distance counterexample to Borsuk's conjecture, arXiv:1308.0206 
  11. ^ Jenrich, Thomas; Brouwer, Andries E. (2014), "A 64-Dimensional Counterexample to Borsuk's Conjecture", Electronic Journal of Combinatorics 21 (4): #P4.29, MR 3292266 
  12. ^ Schramm, Oded (1988), "Illuminating sets of constant width", Mathematika 35 (2): 180–189, doi:10.1112/S0025579300015175, MR 0986627 
  13. ^ Alon, Noga (2002), "Discrete mathematics: methods and challenges", Proceedings of the International Congress of Mathematicians, Beijing 1: 119–135, arXiv:math/0212390 

Further reading[edit]

External links[edit]