Borsuk's conjecture: Difference between revisions

Content deleted Content added

Inline

Revision as of 10:20, 19 June 2018

An example of a hexagon cut into three pieces of smaller diameter.

The Borsuk problem in geometry, for historical reasons^{[note 1]} incorrectly called Borsuk's conjecture, is a question in discrete geometry.

Problem

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

This can be translated as:

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

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

Their result was improved in 2003 by Hinrichs and Richter, who constructed finite sets for d ≥ 298, which cannot be partitioned into d+11 parts of smaller diameter^[1].

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

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)\geq (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)\leq \left({\sqrt {3/2}}+\varepsilon \right)^{d}$ .^[14] The correct order of magnitude of α(d) is still unknown.^[15] However, it is conjectured that there is a constant c > 1 such that $\alpha (d)>c^{d}$ for all d ≥ 1.

Note

^ As Hinrichs and Richter say in the introduction to their work^[1], 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.

References

^ ^a ^b Hinrichs, Aicke; Richter, Christian (28 August 2003). "New sets with large Borsuk numbers". Discrete Mathematics. 270 (1–3). Elsevier: 137–147. doi:10.1016/S0012-365X(02)00833-6.
^ ^a ^b 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), 11, Kharkov State University (now National University of Kharkiv): 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:math/9307229, doi:10.1090/S0273-0979-1993-00398-7, MR 1193538
^ Bondarenko, Andriy V. (2013), On Borsuk’s conjecture for two-distance sets, arXiv:1305.2584, Bibcode:2013arXiv1305.2584B
^ 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
^ Jenrich, Thomas (2013), A 64-dimensional two-distance counterexample to Borsuk's conjecture, arXiv:1308.0206, Bibcode:2013arXiv1308.0206J
^ 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:math/0212390, Bibcode:2002math.....12390A

External links

Weisstein, Eric W. "Borsuk's Conjecture". MathWorld.

[WhyConjecture-2] As Hinrichs and Richter say in the introduction to their work^[1], 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.

[HinrRicht-1] Hinrichs, Aicke; Richter, Christian (28 August 2003). "New sets with large Borsuk numbers". Discrete Mathematics. 270 (1–3). Elsevier: 137–147. doi:10.1016/S0012-365X(02)00833-6.

[BorsukFM-3] Borsuk, Karol (1933), "Drei Sätze über die n-dimensionale euklidische Sphäre" (PDF), Fundamenta Mathematicae (in German), 20: 177–190

[4] Perkal, Julian (1947), "Sur la subdivision des ensembles en parties de diamètre inférieur", Colloquium Mathematicum, 2: 45

[5] 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

[6] Hadwiger, Hugo (1945), "Überdeckung einer Menge durch Mengen kleineren Durchmessers", Commentarii Mathematici Helvetici, 18 (1): 73–75, doi:10.1007/BF02568103, MR 0013901

[7] 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

[8] Riesling, A. S. (1971), "Borsuk's problem in three-dimensional spaces of constant curvature" (PDF), Ukr. Geom. Sbornik (in Russian), 11, Kharkov State University (now National University of Kharkiv): 78–83

[9] 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

[10] 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

[11] Bondarenko, Andriy V. (2013), On Borsuk’s conjecture for two-distance sets, arXiv:1305.2584, Bibcode:2013arXiv1305.2584B

[12] 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

[13] Jenrich, Thomas (2013), A 64-dimensional two-distance counterexample to Borsuk's conjecture, arXiv:1308.0206, Bibcode:2013arXiv1308.0206J

[14] Jenrich, Thomas; Brouwer, Andries E. (2014), "A 64-Dimensional Counterexample to Borsuk's Conjecture", Electronic Journal of Combinatorics, 21 (4): #P4.29, MR 3292266

[15] Schramm, Oded (1988), "Illuminating sets of constant width", Mathematika, 35 (2): 180–189, doi:10.1112/S0025579300015175, MR 0986627

[16] Alon, Noga (2002), "Discrete mathematics: methods and challenges", Proceedings of the International Congress of Mathematicians, Beijing, 1: 119–135, arXiv:math/0212390, Bibcode:2002math.....12390A

[note 1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[1]

[10]

[11]

[12]

[13]

[14]

[15]

@@ Line 90: / Line 90: @@
  | doi = 10.1090/S0273-0979-1993-00398-7}}</ref> Their construction shows that {{nobr|''d'' + 1}} pieces do not suffice for {{nobr|1=''d'' = 1,325}} and for each {{nobr|''d'' > 2,014}}.
+Their result was improved in 2003 by Hinrichs and Richter, who constructed finite sets for {{nobr|''d'' ≥ 298}}, which cannot be partitioned into {{nobr|''d''+11}} parts of smaller diameter<ref name=HinrRicht />.
-After Andriy V. Bondarenko had shown that Borsuk’s conjecture is false for all {{nobr|''d'' ≥ 65}},<ref>{{citation
+After Andriy V. Bondarenko had shown in 2013 that Borsuk’s conjecture is false for all {{nobr|''d'' ≥ 65}},<ref>{{citation
  | last = Bondarenko | first = Andriy V.
  | title = On Borsuk’s conjecture for two-distance sets