Borsuk's conjecture: Difference between revisions
display="inline" for inline <math> to make line-height fit better; {{blockquote}} instead of colon-indented blockquote (by SublimeText.Mediawiker) |
{{mvar}}/{{math}} for inline math expressions, for consistency with equations in paragraphs (by SublimeText.Mediawiker) |
||
Line 15: | Line 15: | ||
| url = http://matwbn.icm.edu.pl/ksiazki/fm/fm20/fm20117.pdf| doi = 10.4064/fm-20-1-177-190 |
| url = http://matwbn.icm.edu.pl/ksiazki/fm/fm20/fm20117.pdf| doi = 10.4064/fm-20-1-177-190 |
||
| doi-access = free |
| doi-access = free |
||
}}</ref> that an ordinary 3-dimensional [[ball (mathematics)|ball]] in [[Euclidean space]] can be easily dissected into 4 solids, each of which has a smaller [[diameter]] than the ball, and generally |
}}</ref> that an ordinary 3-dimensional [[ball (mathematics)|ball]] in [[Euclidean space]] can be easily dissected into 4 solids, each of which has a smaller [[diameter]] than the ball, and generally {{mvar|n}}-dimensional ball can be covered with {{math|''n'' + 1}} [[Compact space|compact]] [[Set (mathematics)|sets]] of diameters smaller than the ball. At the same time he proved that {{mvar|n}} [[subset]]s are not enough in general. The proof is based on the [[Borsuk–Ulam theorem]]. That led Borsuk to a general question:<ref name="BorsukFM" /> |
||
{{blockquote |text= |
{{blockquote |text= |
||
{{lang|de|text= Die folgende Frage bleibt offen: Lässt sich jede beschränkte Teilmenge E des Raumes {{math|ℝ<sup>n</sup>}} in (n |
''{{lang|de|text= Die folgende Frage bleibt offen: Lässt sich jede beschränkte Teilmenge {{mvar|E}} des Raumes {{math|ℝ<sup>n</sup>}} in ({{math|n + 1}}) Mengen zerlegen, von denen jede einen kleineren Durchmesser als {{mvar|E}} hat? |italic= unset}}'' |
||
The following question remains open: Can every [[bounded set|bounded]] subset |
The following question remains open: Can every [[bounded set|bounded]] subset {{mvar|E}} of the space {{math|ℝ<sup>''n''</sup>}} be [[partition of a set|partitioned]] into ({{math|''n'' + 1}}) sets, each of which has a smaller diameter than {{mvar|E}}? |
||
|multiline= yes |
|multiline= yes |
||
|source= {{lang|de|Drei Sätze über die n-dimensionale euklidische Sphäre}} |
|source= {{lang|de|Drei Sätze über die n-dimensionale euklidische Sphäre}} |
||
Line 26: | Line 26: | ||
The question was answered in the positive in the following cases: |
The question was answered in the positive in the following cases: |
||
* ''n'' = 2 — which is the original result by Karol Borsuk (1932). |
* {{math|1= ''n'' = 2}} — which is the original result by Karol Borsuk (1932). |
||
* ''n'' = 3 — shown by Julian Perkal (1947),<ref>{{citation |
* {{math|1= ''n'' = 3}} — shown by Julian Perkal (1947),<ref>{{citation |
||
| last = Perkal | first = Julian |
| last = Perkal | first = Julian |
||
| journal = Colloquium Mathematicum |
| journal = Colloquium Mathematicum |
||
Line 33: | Line 33: | ||
| title = Sur la subdivision des ensembles en parties de diamètre inférieur |
| title = Sur la subdivision des ensembles en parties de diamètre inférieur |
||
| volume = 2 |
| volume = 2 |
||
| year = 1947}}</ref> and independently, 8 years later, by H. G. Eggleston (1955).<ref>{{citation |
| year = 1947 |
||
| lang = fr}}</ref> and independently, 8 years later, by H. G. Eggleston (1955).<ref>{{citation |
|||
| last = Eggleston | first = H. G. |
| last = Eggleston | first = H. G. |
||
| mr = 0067473 |
| mr = 0067473 |
||
Line 42: | Line 43: | ||
| year = 1955 |
| year = 1955 |
||
| doi = 10.1112/jlms/s1-30.1.11}}</ref> A simple proof was found later by [[Branko Grünbaum]] and Aladár Heppes. |
| doi = 10.1112/jlms/s1-30.1.11}}</ref> A simple proof was found later by [[Branko Grünbaum]] and Aladár Heppes. |
||
* For all |
* For all {{mvar|n}} for [[Smooth manifold|smooth]] convex bodies — shown by [[Hugo Hadwiger]] (1946).<ref>{{citation |
||
| last = Hadwiger | first = Hugo | authorlink = Hugo Hadwiger |
| last = Hadwiger | first = Hugo | authorlink = Hugo Hadwiger |
||
| mr = 0013901 |
| mr = 0013901 |
||
Line 51: | Line 52: | ||
| issue = 1 |
| issue = 1 |
||
| year = 1945 |
| year = 1945 |
||
| lang = de |
|||
| doi = 10.1007/BF02568103| s2cid = 122199549 }}</ref><ref>{{citation |
| doi = 10.1007/BF02568103| s2cid = 122199549 }}</ref><ref>{{citation |
||
| last = Hadwiger | first = Hugo | authorlink = Hugo Hadwiger |
| last = Hadwiger | first = Hugo | authorlink = Hugo Hadwiger |
||
Line 60: | Line 62: | ||
| issue = 1 |
| issue = 1 |
||
| year = 1946 |
| year = 1946 |
||
| lang = de |
|||
| doi = 10.1007/BF02565947| s2cid = 121053805 }}</ref> |
| doi = 10.1007/BF02565947| s2cid = 121053805 }}</ref> |
||
* For all |
* For all {{mvar|n}} for [[Central symmetry|centrally-symmetric]] bodies — shown by A.S. Riesling (1971).<ref>{{citation |
||
| url = http://geometry.karazin.ua/resources/articles/594b744b34d8b035cdea7128bbae7d64.pdf |
| url = http://geometry.karazin.ua/resources/articles/594b744b34d8b035cdea7128bbae7d64.pdf |
||
| language = ru |
| language = ru |
||
Line 72: | Line 75: | ||
| volume = 11 |
| volume = 11 |
||
| year = 1971}}</ref> |
| year = 1971}}</ref> |
||
* For all |
* For all {{mvar|n}} for [[Solid of revolution|bodies of revolution]] — shown by Boris Dekster (1995).<ref>{{citation |
||
| last = Dekster | first = Boris |
| last = Dekster | first = Boris |
||
| mr = 1317256 |
| mr = 1317256 |
||
Line 95: | Line 98: | ||
| year = 1993 |
| year = 1993 |
||
| arxiv = math/9307229 |
| arxiv = math/9307229 |
||
| doi = 10.1090/S0273-0979-1993-00398-7| s2cid = 119647518 }}</ref> They claim that their construction shows that {{ |
| doi = 10.1090/S0273-0979-1993-00398-7| s2cid = 119647518 }}</ref> They claim that their construction shows that {{math|''n'' + 1}} pieces do not suffice for {{math|1=''n'' = 1325}} and for each {{math|''n'' > 2014}}. However, as pointed out by Bernulf Weißbach,<ref>{{citation |
||
| url = https://www.emis.de/journals/BAG/vol.41/no.2/b41h2wb1.pdf |
| url = https://www.emis.de/journals/BAG/vol.41/no.2/b41h2wb1.pdf |
||
| last1 = Weißbach | first1 = Bernulf |
| last1 = Weißbach | first1 = Bernulf |
||
Line 103: | Line 106: | ||
| volume = 41 |
| volume = 41 |
||
| issue = 2 |
| issue = 2 |
||
| year = 2000 |
|||
| |
| lang = de}}</ref> the first part of this claim is in fact false. But after improving a suboptimal conclusion within the corresponding derivation, one can indeed verify one of the constructed point sets as a counterexample for {{math|1=''n'' = 1325}} (as well as all higher dimensions up to 1560).<ref>{{citation |
||
| last1 = Jenrich | first1 = Thomas |
| last1 = Jenrich | first1 = Thomas |
||
| title = On the counterexamples to Borsuk's conjecture by Kahn and Kalai |
| title = On the counterexamples to Borsuk's conjecture by Kahn and Kalai |
||
Line 109: | Line 113: | ||
| arxiv = 1809.09612v4}}</ref> |
| arxiv = 1809.09612v4}}</ref> |
||
Their result was improved in 2003 by Hinrichs and Richter, who constructed finite sets for {{ |
Their result was improved in 2003 by Hinrichs and Richter, who constructed finite sets for {{math|''n'' ≥ 298}}, which cannot be partitioned into {{math|''n'' + 11}} parts of smaller diameter.<ref name=HinrRicht /> |
||
In 2013, Andriy V. Bondarenko had shown that Borsuk’s conjecture is false for all {{ |
In 2013, Andriy V. Bondarenko had shown that Borsuk’s conjecture is false for all {{math|''n'' ≥ 65}}.<ref> |
||
{{citation |
{{citation |
||
| last = Bondarenko | first = Andriy |
| last = Bondarenko | first = Andriy |
||
Line 141: | Line 145: | ||
}}</ref> |
}}</ref> |
||
Apart from finding the minimum number |
Apart from finding the minimum number {{mvar|n}} of dimensions such that the number of pieces {{math|''α''(''n'') > ''n'' + 1}}, mathematicians are interested in finding the general behavior of the function {{math|''α''(''n'')}}. Kahn and Kalai show that in general (that is, for {{mvar|n}} sufficiently large), one needs <math display="inline">\alpha(n) \ge (1.2)^\sqrt{n}</math> many pieces. They also quote the upper bound by [[Oded Schramm]], who showed that for every {{mvar|ε}}, if {{mvar|n}} is sufficiently large, <math display="inline">\alpha(n) \le \left(\sqrt{3/2} + \varepsilon\right)^n</math>.<ref>{{citation |
||
| last = Schramm | first = Oded | authorlink1 = Oded Schramm |
| last = Schramm | first = Oded | authorlink1 = Oded Schramm |
||
| mr = 0986627 |
| mr = 0986627 |
||
Line 150: | Line 154: | ||
| issue = 2 |
| issue = 2 |
||
| year = 1988 |
| year = 1988 |
||
| doi = 10.1112/S0025579300015175}}</ref> The correct order of magnitude of ''α''(''n'') is still unknown.<ref>{{citation |
| doi = 10.1112/S0025579300015175}}</ref> The correct order of magnitude of {{math|''α''(''n'')}} is still unknown.<ref>{{citation |
||
| last = Alon | first = Noga | authorlink1 = Noga Alon |
| last = Alon | first = Noga | authorlink1 = Noga Alon |
||
| journal = Proceedings of the International Congress of Mathematicians, Beijing |
| journal = Proceedings of the International Congress of Mathematicians, Beijing |
||
Line 157: | Line 161: | ||
| volume = 1 |
| volume = 1 |
||
| year = 2002 |
| year = 2002 |
||
| arxiv = math/0212390| bibcode = 2002math.....12390A}}</ref> However, it is conjectured that there is a constant {{ |
| arxiv = math/0212390| bibcode = 2002math.....12390A}}</ref> However, it is conjectured that there is a constant {{math|''c'' > 1}} such that {{math|''α''(''n'') > ''c<sup>n</sup>''}} for all {{math|''n'' ≥ 1}}. |
||
==See also== |
==See also== |
Revision as of 18:53, 4 July 2023
The Borsuk problem in geometry, for historical reasons[note 1] incorrectly called Borsuk's conjecture, is a question in discrete geometry. It is named after Karol Borsuk.
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 n-dimensional ball can be covered with n + 1 compact sets of diameters smaller than the ball. At the same time he proved that n subsets are not enough in general. The proof is based on the Borsuk–Ulam theorem. That led Borsuk to a general question:[2]
Die folgende Frage bleibt offen: Lässt sich jede beschränkte Teilmenge E des Raumes ℝn in (n + 1) Mengen zerlegen, von denen jede einen kleineren Durchmesser als E hat?
The following question remains open: Can every bounded subset E of the space ℝn be partitioned into (n + 1) sets, each of which has a smaller diameter than E?
— Drei Sätze über die n-dimensionale euklidische Sphäre
The question was answered in the positive in the following cases:
- n = 2 — which is the original result by Karol Borsuk (1932).
- n = 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 n for smooth convex bodies — shown by Hugo Hadwiger (1946).[5][6]
- For all n for centrally-symmetric bodies — shown by A.S. Riesling (1971).[7]
- For all n 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] They claim that their construction shows that n + 1 pieces do not suffice for n = 1325 and for each n > 2014. However, as pointed out by Bernulf Weißbach,[10] the first part of this claim is in fact false. But after improving a suboptimal conclusion within the corresponding derivation, one can indeed verify one of the constructed point sets as a counterexample for n = 1325 (as well as all higher dimensions up to 1560).[11]
Their result was improved in 2003 by Hinrichs and Richter, who constructed finite sets for n ≥ 298, which cannot be partitioned into n + 11 parts of smaller diameter.[1]
In 2013, Andriy V. Bondarenko had shown that Borsuk’s conjecture is false for all n ≥ 65.[12] Shortly after, Thomas Jenrich derived a 64-dimensional counterexample from Bondarenko's construction, giving the best bound up to now.[13][14]
Apart from finding the minimum number n of dimensions such that the number of pieces α(n) > n + 1, mathematicians are interested in finding the general behavior of the function α(n). Kahn and Kalai show that in general (that is, for n sufficiently large), one needs many pieces. They also quote the upper bound by Oded Schramm, who showed that for every ε, if n is sufficiently large, .[15] The correct order of magnitude of α(n) is still unknown.[16] However, it is conjectured that there is a constant c > 1 such that α(n) > cn for all n ≥ 1.
See also
- Hadwiger's conjecture on covering convex bodies with smaller copies of themselves
- Kahn–Kalai conjecture
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, doi:10.4064/fm-20-1-177-190
- ^ Perkal, Julian (1947), "Sur la subdivision des ensembles en parties de diamètre inférieur", Colloquium Mathematicum (in French), 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 (in German), 18 (1): 73–75, doi:10.1007/BF02568103, MR 0013901, S2CID 122199549
- ^ Hadwiger, Hugo (1946), "Mitteilung betreffend meine Note: Überdeckung einer Menge durch Mengen kleineren Durchmessers", Commentarii Mathematici Helvetici (in German), 19 (1): 72–73, doi:10.1007/BF02565947, MR 0017515, S2CID 121053805
- ^ 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, S2CID 121586146
- ^ 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, S2CID 119647518
- ^ Weißbach, Bernulf (2000), "Sets with Large Borsuk Number" (PDF), Beiträge zur Algebra und Geometrie (in German), 41 (2): 417–423
- ^ Jenrich, Thomas (2018), On the counterexamples to Borsuk's conjecture by Kahn and Kalai, arXiv:1809.09612v4
- ^ Bondarenko, Andriy (2014) [2013], "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, doi:10.37236/4069, 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
Further reading
- 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 (eds.). Surveys in contemporary mathematics. London Mathematical Society Lecture Note Series. Vol. 347. Cambridge University Press. pp. 202–247. ISBN 978-0-521-70564-6. Zbl 1144.52005.