Borsuk's conjecture: Difference between revisions

Content deleted Content added

Inline

Revision as of 19:26, 30 May 2013

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

Problem

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

Translation:

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 — the original result by Borsuk (1932).
d = 3 — the result of Julian Perkal (1947),^[2] and independently, 8 years later, 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 — the result of Hugo Hadwiger (1946).^[4]
For all d for centrally-symmetric bodies (A.S. Riesling, 1971).
For all d for bodies of revolution — the result of Boris Dekster (1995).

The problem was finally solved in 1993 by Jeff Kahn and Gil Kalai, who showed the general answer to the 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.

The current best bound, due to Andriy V. Bondarenko, shows that Borsuk’s conjecture is false for all d ≥ 65^[5].

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 $\alpha (d)$ function. 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}$ . The correct order of magnitude of α(d) is still unknown (see e.g. Alon's article), however it is conjectured that there is a constant c > 1 such that $\alpha (d)>c^{d}$ for all d ≥ 1.

Notes

^ ^a ^b K. Borsuk, Drei Sätze über die n-dimensionale euklidische Sphäre, "Fundamenta Mathematicae", 20 (1933). 177–190
^ J. Perkal, Sur la subdivision des ensembles en parties de diamètre inférieur, Colloq. Math. 2 (1947), 45.
^ H. G. Eggleston, Covering a three-dimensional set with sets of smaller diameter, J. Lond. Math. Soc. 30 (1955), 11–24.
^ Hadwiger H, Überdeckung einer Menge durch Mengen kleineren Durchmessers, Comment. Math. Helv., 18 (1945/46), 73–75;
Mitteilung betreffend meine Note: Überdeckung einer Menge durch Mengen kleineren Durchmessers, 19 (1946/47), 72–73
^ Andriy V. Bondarenko, On Borsuk's conjecture for two-distance sets.

References

Drei Sätze über die n-dimensionale euklidische Sphäre (German 'Three statements of n-dimensional Euclidean sphere') – original Borsuk's article in Fundamenta Mathematicae, made available by Polish Virtual Library of Science
Jeff Kahn and Gil Kalai, A counterexample to Borsuk's conjecture, Bulletin of the American Mathematical Society 29 (1993), 60–62.
Noga Alon, Discrete mathematics: methods and challenges, Proceedings of the International Congress of Mathematicians, Beijing 2002, vol. 1, 119–135.
Aicke Hinrichs and Christian Richter, New sets with large Borsuk numbers, Discrete Math. 270 (2003), 137–147
Andrei M. Raigorodskii, The Borsuk partition problem: the seventieth anniversary, Mathematical Intelligencer 26 (2004), no. 3, 4–12.
Oded Schramm, Illuminating sets of constant width, Mathematika 35 (1988), 180–199.

External links

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

[BorsukFM-1] K. Borsuk, Drei Sätze über die n-dimensionale euklidische Sphäre, "Fundamenta Mathematicae", 20 (1933). 177–190

[2] J. Perkal, Sur la subdivision des ensembles en parties de diamètre inférieur, Colloq. Math. 2 (1947), 45.

[3] H. G. Eggleston, Covering a three-dimensional set with sets of smaller diameter, J. Lond. Math. Soc. 30 (1955), 11–24.

[4] Hadwiger H, Überdeckung einer Menge durch Mengen kleineren Durchmessers, Comment. Math. Helv., 18 (1945/46), 73–75;
Mitteilung betreffend meine Note: Überdeckung einer Menge durch Mengen kleineren Durchmessers, 19 (1946/47), 72–73

[5] Andriy V. Bondarenko, On Borsuk's conjecture for two-distance sets.

[1]

[2]

[3]

[4]

[5]

@@ Line 21: / Line 21: @@
 The problem was finally solved in 1993 by [[Jeff Kahn]] and [[Gil Kalai]], who showed the general answer to the Borsuk's question is ''no''. Their construction shows that {{nobr|''d'' + 1}} pieces do not suffice for {{nobr|1=''d'' = 1,325}} and for each {{nobr|''d'' > 2,014}}.
-The current best bound, due to Aicke Hinrichs and Christian Richter, shows that the answer is negative for all {{nobr|''d'' ≥ 298}}.
+The current best bound, due to Andriy V. Bondarenko, shows that Borsuk’s conjecture is false for all {{nobr|''d'' ≥ 65}}<ref>Andriy V. Bondarenko, [http://arxiv.org/abs/1305.2584 On Borsuk's conjecture for two-distance sets].</ref>.
 Apart from finding the minimum number ''d'' of dimensions such that the number of pieces <math>\alpha(d) > d+1</math> mathematicians are interested in finding the general behavior of <math>\alpha(d)</math> function. Kahn and Kalai show that in general (that is for ''d'' big enough), one needs <math>\alpha(d) \ge (1.2)^\sqrt{d}</math> number of pieces. They also quote the upper bound by [[Oded Schramm]], who showed that for every ''ε'', if ''d'' is sufficiently large, <math>\alpha(d) \le \left(\sqrt{3/2} + \varepsilon\right)^d</math>. The correct order of magnitude of ''α''(''d'') is still unknown (see e.g. Alon's article), however it is conjectured that there is a constant {{nobr|''c'' > 1}} such that <math>\alpha(d) > c^d</math> for all {{nobr|''d'' ≥ 1}}.