Borsuk's conjecture

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

Problem

In 1932 Karol Borsuk has shownK. Borsuk, "Drei Sätze über die n-dimensionale euklidische Sphäre", "Fundamenta Mathematicae", 20 (1933). 177-190] 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:

: "Can every convex body in $Bbb\; R^d$ be cut into $(d+1)$ pieces of smaller diameter?"

The question got a positive answer in the following cases:
* "d=2" – the original result by Borsuk (1932).
* "d=3" – the result of H. G. Eggleston (1955). 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).
* For all "d" for centrally-symmetric bodies (A.S. Riesling, 1971).
* For all "d" for bodies of revolution – the result of Dexter (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. The current best bound, due to Aicke Hinrichs and Christian Richter, shows that the answer is negative for all "d" ≥ 298. The proof by Kahn and Kalai implies that for large enough "d", one needs $alpha(d)\; >\; c^sqrt\{d\}$ number of pieces. It is conjectured that (see e.g. Alon's article) that $alpha(d)\; >\; c^d$ for some "c" >1.

Conjecture status

For many years most of mathematicians expected the general answer to the Borsuk's question would eventually turn out to be "yes", so they called the problem a conjecture and expressed it in a proposition form:

: "Every convex body in $Bbb\; R^d$ can be cut into $(d+1)$ pieces of smaller diameter."

Borsuk himself, however, was not so sure about it and never expressed the problem in that form. He had enough intuition to leave it just in the question form:

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

: "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 having a smaller diameter than E?"

Notes

References

* [http://matwbn.icm.edu.pl/ksiazki/fm/fm20/fm20117.pdf "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 [http://matwbn.icm.edu.pl/index.php?jez=en Polish Virtual Library of Science]

* Jeff Kahn and Gil Kalai, [http://arxiv.org/abs/math.MG/9307229 A counterexample to Borsuk's conjecture] , "Bulletin of the American Mathematical Society" 29 (1993), 60-62.
* Noga Alon, [http://arxiv.org/abs/math.CO/0212390 Discrete mathematics: methods and challenges] , "Proceedings of the International Congress of Mathematicians, Beijing 2002", vol. 1, 119-135.
* Aicke Hinrichs and Christian Richter, [http://www.minet.uni-jena.de/~hinrichs/paper/18/borsuk.pdf 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.
* Oleg Pikhurko, " [http://www.math.cmu.edu/~pikhurko/LectureNotes.ps Algebraic Methods in Combinatorics] ", course notes.

External links

* [http://mathworld.wolfram.com/BorsuksConjecture.html Borsuk's Conjecture] , from MathWorld.