12.3 Open Problems in Discrete Geometry
3 min read•august 12, 2024
Open problems in discrete geometry push the boundaries of our understanding. These unsolved puzzles, like the Erdős-Szekeres and Hadwiger conjectures, challenge mathematicians to think creatively about shapes, colors, and patterns in space.
From the to the , these open questions connect different areas of math. They show how geometry intersects with graph theory, combinatorics, and even computer science, highlighting the field's broad impact.
Conjectures in Discrete Geometry
Erdős-Szekeres and Hadwiger Conjectures
Top images from around the web for Erdős-Szekeres and Hadwiger Conjectures
Erdős–Faber–Lovász conjecture - Wikipedia View original
Is this image relevant?
On the ErdÖs Distance Conjecture in Geometry View original
Is this image relevant?
Hadwiger's theorem - Wikipedia, the free encyclopedia View original
Is this image relevant?
Erdős–Faber–Lovász conjecture - Wikipedia View original
Is this image relevant?
On the ErdÖs Distance Conjecture in Geometry View original
Is this image relevant?
1 of 3
Top images from around the web for Erdős-Szekeres and Hadwiger Conjectures
Erdős–Faber–Lovász conjecture - Wikipedia View original
Is this image relevant?
On the ErdÖs Distance Conjecture in Geometry View original
Is this image relevant?
Hadwiger's theorem - Wikipedia, the free encyclopedia View original
Is this image relevant?
Erdős–Faber–Lovász conjecture - Wikipedia View original
Is this image relevant?
On the ErdÖs Distance Conjecture in Geometry View original
Is this image relevant?
1 of 3
- posits that for every integer n ≥ 3, there exists a smallest integer ES(n) such that any set of at least ES(n) points in general position in the plane contains n points that form a
- Applies to sets of points where no three points are collinear
- Current best known bounds:
- Remains unproven for n > 6
- states that every k-chromatic graph contains a subdivision of the complete graph on k vertices as a subgraph
- Generalizes the Four Color Theorem
- Proven for k ≤ 6, remains open for k > 6
- Implies that every k-chromatic graph has a clique minor of size k
Kneser and McMullen's Conjectures
- relates to the of Kneser graphs
- States that the chromatic number of the Kneser graph KG(n,k) is equal to n - 2k + 2
- Proven by in 1978 using topological methods
- Led to the development of
- concerns the face numbers of
- Describes the possible f-vectors of simplicial d-polytopes
- Proven for 3-dimensional polytopes
- Remains open for dimensions 4 and higher
- Connects algebraic and geometric properties of polytopes
Problems and Theorems
Unit Distance Problem and Chromatic Number of the Plane
- Unit distance problem asks for the maximum number of unit distances determined by n points in the plane
- Upper bound: O(n^(4/3))
- Lower bound: n^(1+c/log log n) for some constant c > 0
- Relates to the
- Chromatic number of the plane problem asks for the minimum number of colors needed to color all points of the plane such that no two points at unit distance apart have the same color
- Known bounds: 4 ≤ χ(R^2) ≤ 7
- , named after Hugo Hadwiger and Edward Nelson
- Connects to graph theory and geometric coloring problems
Szemerédi-Trotter Theorem and Applications
- provides an upper bound on the number of between a finite set of points and a finite set of lines in the plane
- States that for m points and n lines, the number of incidences is at most O(m^(2/3)n^(2/3) + m + n)
- Proved by Endre Szemerédi and William T. Trotter Jr. in 1983
- Generalizes to higher dimensions and curved objects
- Applications of Szemerédi-Trotter theorem
- Solves the distinct distances problem in the plane
- Improves bounds for sum-product estimates
- Used in harmonic analysis and additive combinatorics
Happy Ending Problem and Ramsey Theory
- asks for the minimum number of points in general position that guarantees the existence of a convex n-gon
- Solved for n = 3, 4, 5
- Remains open for n > 5
- Related to the Erdős-Szekeres theorem
- Connections to
- Generalizes to higher dimensions and abstract settings
- Leads to questions about geometric Ramsey numbers
- Explores structural properties of large sets of points in various geometric configurations
Key Terms to Review (17)
Chromatic Number: The chromatic number of a graph is the smallest number of colors needed to color the vertices of the graph so that no two adjacent vertices share the same color. This concept is essential in understanding how to efficiently organize and represent information, and it connects deeply with concepts like graph theory and coloring problems in discrete geometry, particularly in analyzing geometric structures and their properties.
Chromatic Number of the Plane: The chromatic number of the plane refers to the minimum number of colors needed to color the points of the plane such that no two points at a unit distance apart share the same color. This concept is significant in discrete geometry as it relates to various problems involving graph theory and spatial arrangements, sparking curiosity and open questions in the field.
Convex polygon: A convex polygon is a simple polygon in which all interior angles are less than 180 degrees, and no line segment between any two points on the boundary ever goes outside the polygon. This property ensures that if you pick any two points inside the polygon, the line connecting them will also lie entirely within the polygon. Convex polygons play a key role in various geometric algorithms, such as those used for calculating convex hulls, triangulating shapes for computational efficiency, and are often at the center of ongoing research in discrete geometry.
Erdős Distinct Distances Problem: The Erdős Distinct Distances Problem is a famous question in combinatorial geometry that asks for the minimum number of distinct distances that can be formed by a finite set of points in the plane. The conjecture, proposed by mathematician Paul Erdős in 1946, suggests that any set of $n$ points in general position in the plane will determine at least $ rac{n}{ ext{c}}$ distinct distances, where $ ext{c}$ is some constant. This problem connects to various concepts in geometry, such as duality and incidences between points and hyperplanes, as well as representing a significant open problem in the study of discrete geometry.
Erdős-Szekeres Conjecture: The Erdős-Szekeres Conjecture is a fundamental idea in combinatorial geometry that states that any set of at least $$n$$ points in general position in the plane contains a subset of $$k$$ points that form the vertices of a convex polygon, for sufficiently large values of $$n$$ and $$k$$. This conjecture highlights the relationship between the number of points and the possibility of forming convex shapes, providing insight into the structure of point sets in Euclidean space.
Hadwiger Conjecture: The Hadwiger Conjecture is a fundamental statement in graph theory that proposes that every graph that cannot be colored with fewer than $k$ colors must contain a complete graph on $k$ vertices as a minor. This conjecture is closely linked to the study of graph colorings and structural properties, making it an important topic in discrete geometry and combinatorial optimization.
Hadwiger-Nelson Problem: The Hadwiger-Nelson Problem is a question in discrete geometry that asks for the minimum number of colors needed to color the points of the plane so that no two points at a unit distance from each other share the same color. This problem connects to various concepts in graph theory and combinatorics, highlighting the interplay between geometry and coloring principles.
Happy Ending Problem: The Happy Ending Problem is a classic question in combinatorial geometry that asks whether a set of points in the plane, no three of which are collinear, contains a subset of points that forms the vertices of a convex polygon, specifically a convex quadrilateral. This problem emphasizes the relationship between geometric configurations and combinatorial properties, showcasing how certain arrangements of points lead to guaranteed outcomes regarding convex shapes.
Incidences: Incidences refer to the relationships or intersections between geometric objects, such as points, lines, and planes, indicating how they interact within a geometric configuration. This concept is fundamental in discrete geometry as it helps describe how various geometric entities coexist and the nature of their connections, such as whether a point lies on a line or how many lines pass through a given point.
Kneser Conjecture: The Kneser Conjecture proposes that for any two non-negative integers $n$ and $k$ with $n \geq 2k$, the chromatic number of the Kneser graph $K(n, k)$ is equal to $n - 2k + 2$. This conjecture connects various areas of discrete mathematics, such as graph theory and combinatorics, emphasizing the interplay between combinatorial structures and coloring problems.
László Lovász: László Lovász is a prominent Hungarian mathematician known for his significant contributions to various fields, including combinatorics, graph theory, and discrete geometry. He has played a vital role in advancing the understanding of fundamental problems in discrete mathematics and is recognized for his work on algorithmic aspects of these topics, particularly related to open problems in discrete geometry.
McMullen's g-conjecture: McMullen's g-conjecture is a statement in discrete geometry that relates to the face numbers of convex polytopes and their projections into lower dimensions. Specifically, it asserts that for any convex polytope, the number of faces of a certain dimension, when viewed through the lens of its geometric properties, can be predicted based on the relationship with the faces of higher dimensions. This conjecture is part of broader open problems in the field, highlighting the intricate connections between topology, combinatorics, and geometry.
Ramsey Theory: Ramsey theory is a branch of combinatorial mathematics that focuses on finding guaranteed patterns within large structures or sets. It essentially states that given a sufficiently large amount of data, a certain level of order or structure must emerge, regardless of how disordered the data appears. This concept is crucial in various applications, such as graph theory and discrete geometry, where it can help in understanding how shapes and configurations can be formed or predicted under certain conditions.
Simplicial Polytopes: Simplicial polytopes are geometric objects formed by the convex hull of a finite set of points in a Euclidean space, where every face is a simplex. This means that they can be visualized as higher-dimensional analogs of triangles and tetrahedra, providing a rich structure for combinatorial and geometric analysis. Their properties and relationships connect deeply with arrangements of geometric objects and open questions in discrete geometry.
Szemerédi-Trotter Theorem: The Szemerédi-Trotter Theorem is a fundamental result in combinatorial geometry that provides a bound on the number of incidences between points and lines in the plane. Specifically, it states that the number of incidences between a set of n points and a set of m lines is at most proportional to $$n^{2/3} m^{2/3} + n + m$$. This theorem has profound implications in various areas, especially in understanding point-hyperplane incidences and exploring open problems in discrete geometry.
Topological Combinatorics: Topological combinatorics is a branch of mathematics that combines concepts from topology and combinatorial geometry, focusing on the relationships and properties of combinatorial structures in topological spaces. It investigates how combinatorial structures behave under continuous transformations and how these behaviors can reveal underlying geometric or topological features. This area often addresses open problems by exploring the interplay between combinatorial configurations and topological properties.
Unit distance problem: The unit distance problem is a question in discrete geometry that asks whether it is possible to arrange points in a space such that the distance between any two points is exactly one unit. This problem explores the limits of point distribution and has implications for understanding geometric structures and configurations.