Borsuk's conjecture

Last updated
An example of a hexagon cut into three pieces of smaller diameter. Borsuk Hexagon.svg
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. It is named after Karol Borsuk.

Contents

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

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

Note

  1. 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.

Related Research Articles

<span class="mw-page-title-main">Hugo Hadwiger</span> Swiss mathematician (1908–1981)

Hugo Hadwiger was a Swiss mathematician, known for his work in geometry, combinatorics, and cryptography.

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

<span class="mw-page-title-main">Hadwiger conjecture (graph theory)</span> Unproven generalization of the four-color theorem

In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.

<span class="mw-page-title-main">Hadwiger–Nelson problem</span> Mathematical problem

In geometric graph theory, the Hadwiger–Nelson problem, named after Hugo Hadwiger and Edward Nelson, asks for the minimum number of colors required to color the plane such that no two points at distance 1 from each other have the same color. The answer is unknown, but has been narrowed down to one of the numbers 5, 6 or 7. The correct value may depend on the choice of axioms for set theory.

A thrackle is an embedding of a graph in the plane in which each edge is a Jordan arc and every pair of edges meet exactly once. Edges may either meet at a common endpoint, or, if they have no endpoints in common, at a point in their interiors. In the latter case, they must cross at their intersection point: the intersection must be transverse.

<span class="mw-page-title-main">Hirsch conjecture</span> On lengths of shortest paths in convex polytopes

In mathematical programming and polyhedral combinatorics, the Hirsch conjecture is the statement that the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n − d. That is, any two vertices of the polytope must be connected to each other by a path of length at most n − d. The conjecture was first put forth in a letter by Warren M. Hirsch to George B. Dantzig in 1957 and was motivated by the analysis of the simplex method in linear programming, as the diameter of a polytope provides a lower bound on the number of steps needed by the simplex method. The conjecture is now known to be false in general.

Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.

<span class="mw-page-title-main">Gil Kalai</span> Israeli mathematician and computer scientist

Gil Kalai is an Israeli mathematician and computer scientist. He is the Henry and Manya Noskwith Professor Emeritus of Mathematics at the Hebrew University of Jerusalem, Israel, Professor of Computer Science at the Interdisciplinary Center, Herzliya, and adjunct Professor of mathematics and of computer science at Yale University, United States.

<i>Discrete & Computational Geometry</i> Academic journal

Discrete & Computational Geometry is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational geometry.

<span class="mw-page-title-main">Hadwiger conjecture (combinatorial geometry)</span>

In combinatorial geometry, the Hadwiger conjecture states that any convex body in n-dimensional Euclidean space can be covered by 2n or fewer smaller bodies homothetic with the original body, and that furthermore, the upper bound of 2n is necessary if and only if the body is a parallelepiped. There also exists an equivalent formulation in terms of the number of floodlights needed to illuminate the body.

<span class="mw-page-title-main">Albertson conjecture</span> Relation between graph coloring and crossings

In combinatorial mathematics, the Albertson conjecture is an unproven relationship between the crossing number and the chromatic number of a graph. It is named after Michael O. Albertson, a professor at Smith College, who stated it as a conjecture in 2007; it is one of his many conjectures in graph coloring theory. The conjecture states that, among all graphs requiring colors, the complete graph is the one with the smallest crossing number. Equivalently, if a graph can be drawn with fewer crossings than , then, according to the conjecture, it may be colored with fewer than colors.

<span class="mw-page-title-main">Jeff Kahn</span> American mathematician

Jeffry Ned Kahn is a professor of mathematics at Rutgers University notable for his work in combinatorics.

<span class="mw-page-title-main">Apex graph</span> Graph which can be made planar by removing a single node

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.

<span class="mw-page-title-main">Károly Bezdek</span> Hungarian-Canadian mathematician

Károly Bezdek is a Hungarian-Canadian mathematician. He is a professor as well as a Canada Research Chair of mathematics and the director of the Centre for Computational and Discrete Geometry at the University of Calgary in Calgary, Alberta, Canada. Also he is a professor of mathematics at the University of Pannonia in Veszprém, Hungary. His main research interests are in geometry in particular, in combinatorial, computational, convex, and discrete geometry. He has authored 3 books and more than 130 research papers. He is a founding Editor-in-Chief of the e-journal Contributions to Discrete Mathematics (CDM).

<span class="mw-page-title-main">Keller's conjecture</span> Geometry problem on tiling by hypercubes

In geometry, Keller's conjecture is the conjecture that in any tiling of n-dimensional Euclidean space by identical hypercubes, there are two hypercubes that share an entire (n − 1)-dimensional face with each other. For instance, in any tiling of the plane by identical squares, some two squares must share an entire edge, as they do in the illustration.

In geometry, Kalai's 3d conjecture is a conjecture on the polyhedral combinatorics of centrally symmetric polytopes, made by Gil Kalai in 1989. It states that every d-dimensional centrally symmetric polytope has at least 3d nonempty faces.

<span class="mw-page-title-main">Quadrisecant</span> Line through four points of a curve

In geometry, a quadrisecant or quadrisecant line of a space curve is a line that passes through four points of the curve. This is the largest possible number of intersections that a generic space curve can have with a line, and for such curves the quadrisecants form a discrete set of lines. Quadrisecants have been studied for curves of several types:

In geometry, the distance set of a collection of points is the set of distances between distinct pairs of points. Thus, it can be seen as the generalization of a difference set, the set of distances in collections of numbers.

References

  1. 1 2 Hinrichs, Aicke; Richter, Christian (28 August 2003). "New sets with large Borsuk numbers". Discrete Mathematics . Elsevier. 270 (1–3): 137–147. doi: 10.1016/S0012-365X(02)00833-6 .
  2. 1 2 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
  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), Kharkov State University (now National University of Kharkiv), 11: 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) [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
  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

Further reading