12.3 Open Problems in Discrete Geometry

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 unit distance problem to the chromatic number of the plane, 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

• Erdős-Szekeres conjecture 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 convex polygon
  • Applies to sets of points where no three points are collinear
  • Current best known bounds: $2^{n-2}+1 \leq ES(n) \leq {2n-5 \choose n-2}+1$
  • Remains unproven for n > 6
• Hadwiger conjecture 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

• Kneser conjecture relates to the chromatic number of Kneser graphs
  • States that the chromatic number of the Kneser graph KG(n,k) is equal to n - 2k + 2
  • Proven by László Lovász in 1978 using topological methods
  • Led to the development of topological combinatorics
• McMullen's g-conjecture concerns the face numbers of simplicial polytopes
  • 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 Erdős distinct distances problem
• 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
  • Hadwiger-Nelson problem, named after Hugo Hadwiger and Edward Nelson
  • Connects to graph theory and geometric coloring problems

Szemerédi-Trotter Theorem and Applications

• Szemerédi-Trotter theorem provides an upper bound on the number of incidences 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

• Happy ending problem 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 Ramsey theory
  • 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