Misplaced Pages

Borsuk's conjecture

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Can every bounded subset of Rn be partitioned into (n+1) smaller diameter sets?
An example of a hexagon cut into three pieces of smaller diameter.
Unsolved problem in mathematics: What is the lowest n such that not every bounded subset E of the space R n {\displaystyle \mathbb {R} ^{n}} can be partitioned into (n + 1) sets, each of which has a smaller diameter than E? (more unsolved problems in mathematics)

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

Problem

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 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:

Die folgende Frage bleibt offen: Lässt sich jede beschränkte Teilmenge E des Raumes R n {\displaystyle \mathbb {R} ^{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 R n {\displaystyle \mathbb {R} ^{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), 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 n for smooth convex fields — shown by Hugo Hadwiger (1946).
  • For all n for centrally-symmetric fields — shown by A.S. Riesling (1971).
  • For all n for fields 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. 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, 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).

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.

In 2013, Andriy V. Bondarenko had shown that Borsuk's conjecture is false for all n ≥ 65. Shortly after, Thomas Jenrich derived a 64-dimensional counterexample from Bondarenko's construction, giving the best bound up to now.

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 α ( n ) ≥ ( 1.2 ) n {\textstyle \alpha (n)\geq (1.2)^{\sqrt {n}}} many pieces. They also quote the upper bound by Oded Schramm, who showed that for every ε, if n is sufficiently large, α ( n ) ≤ ( 3 / 2 + ε ) n {\textstyle \alpha (n)\leq \left({\sqrt {3/2}}+\varepsilon \right)^{n}} . The correct order of magnitude of α(n) is still unknown. However, it is conjectured that there is a constant c > 1 such that α(n) > c for all n ≥ 1.

Oded Schramm also worked in a related question, a body K {\displaystyle K} of constant width is said to have effective radius r {\displaystyle r} if Vol ( K ) = r n Vol ( B n ) {\displaystyle {\text{Vol}}(K)=r^{n}{\text{Vol}}(\mathbb {B} ^{n})} , where B n {\displaystyle \mathbb {B} ^{n}} is the unit ball in R n {\displaystyle \mathbb {R} ^{n}} , he proved the lower bound 3 + 2 / ( n + 1 ) − 1 ≤ r n {\displaystyle {\sqrt {3+2/(n+1)}}-1\leq r_{n}} , where r n {\displaystyle r_{n}} is the smallest effective radius of a body of constant width 2 in R n {\displaystyle \mathbb {R} ^{n}} and asked if there exists ϵ > 0 {\displaystyle \epsilon >0} such that r n ≤ 1 − ϵ {\displaystyle r_{n}\leq 1-\epsilon } for all n ≥ 2 {\displaystyle n\geq 2} , that is if the gap between the volumes of the smallest and largest constant-width bodies grows exponentially. In 2024 a preprint by Arman, Bondarenko, Nazarov, Prymak, Radchenko reported to have answered this question in the affirmative giving a construction that satisfies Vol ( K ) ≤ ( 0.9 ) n Vol ( B n ) {\displaystyle {\text{Vol}}(K)\leq (0.9)^{n}{\text{Vol}}(\mathbb {B} ^{n})} .

See also

Note

  1. As Hinrichs and Richter say in the introduction to their work, the "Borsuk's conjecture 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". However, Karol Borsuk has formulated the problem just as a question, not suggesting the expected answer would be positive.

References

  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.
  2. ^ Borsuk, Karol (1933), "Drei Sätze über die n-dimensionale euklidische Sphäre" [Three theorems about the n-dimensional Euclidean sphere] (PDF), Fundamenta Mathematicae (in German), 20: 177–190, doi:10.4064/fm-20-1-177-190
  3. Perkal, Julian (1947), "Sur la subdivision des ensembles en parties de diamètre inférieur", Colloquium Mathematicum (in French), 2: 45
  4. 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
  5. 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
  6. 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
  7. 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
  8. Dekster, Boris (1995), "The Borsuk conjecture holds for fields of revolution", Journal of Geometry, 52 (1–2): 64–73, doi:10.1007/BF01406827, MR 1317256, S2CID 121586146
  9. 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
  10. Weißbach, Bernulf (2000), "Sets with Large Borsuk Number" (PDF), Beiträge zur Algebra und Geometrie (in German), 41 (2): 417–423
  11. Jenrich, Thomas (2018), On the counterexamples to Borsuk's conjecture by Kahn and Kalai, arXiv:1809.09612v4
  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, doi:10.37236/4069, 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
  17. Schramm, Oded (June 1988). "On the volume of sets having constant width". Israel Journal of Mathematics. 63 (2): 178–182. doi:10.1007/BF02765037. ISSN 0021-2172.
  18. Kalai, Gil (2015-05-19). "Some old and new problems in combinatorial geometry I: Around Borsuk's problem". arXiv:1505.04952 .
  19. Arman, Andrii; Bondarenko, Andriy; Nazarov, Fedor; Prymak, Andriy; Radchenko, Danylo (2024-05-28). "Small volume bodies of constant width". arXiv:2405.18501 .
  20. Kalai, Gil (2024-05-31). "Andrii Arman, Andriy Bondarenko, Fedor Nazarov, Andriy Prymak, and Danylo Radchenko Constructed Small Volume Bodies of Constant Width". Combinatorics and more. Retrieved 2024-09-28.
  21. Barber, Gregory (2024-09-20). "Mathematicians Discover New Shapes to Solve Decades-Old Geometry Problem". Quanta Magazine. Retrieved 2024-09-28.

Further reading

External links

Categories:
Borsuk's conjecture Add topic