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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Jeffry Ned Kahn is a professor of mathematics at Rutgers University notable for his work in combinatorics.
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.
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).
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.
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.