Math 2.0

Convex and discrete geometry Discrete and combinatorial geometry Problem

Unit distance problem

Builds on Euclidean planeEuclidean distanceBig O notationCrossing number inequality

Problem

Let n≥2n \ge 2, and let ∥p−q∥\norm{p - q} be the Euclidean distance in the Euclidean plane. Let u(n)u(n) be the largest number of pairs {p,q}\set{p, q} with ∥p−q∥=1\norm{p - q} = 1 in a set of nn points of the plane. Determine the order of growth of u(n)u(n) as n→∞n \to \infty.

Remarks

Paul Erdős posed the problem in 1946. In the same paper he showed u(n)=O(n3/2)u(n) = O(n^{3/2}), and, using a suitably scaled square grid, u(n)≥n1+c/log⁡log⁡nu(n) \ge n^{1 + c/\log \log n} for a constant c>0c > 0; here OO is big O notation. Joel Spencer, Endre Szemerédi and William Trotter proved u(n)=O(n4/3)u(n) = O(n^{4/3}) in 1984. A short proof of this bound by László Székely uses the crossing number inequality. The exact order of growth is still not known. The pairs at distance 11 form the edges of a unit distance graph on the nn points.

Reading path

To understand this page from the ground up, read these 15 pages in order. The foundations come first.

Show the path as a graph
Big O notation, definition, no evidence levelBig O notationdefinitionCrossing number, concept, no evidence levelCrossing numberconceptEuclidean distance, concept, no evidence levelEuclidean distanceconceptEuclidean plane, object, no evidence levelEuclidean planeobjectGraph, concept, no evidence levelGraphconceptGraph, definition, no evidence levelGraphdefinitionPlanar graph, definition, no evidence levelPlanar graphdefinitionProbabilistic method, concept, no evidence levelProbabilistic methodconceptWalk, definition, no evidence levelWalkdefinitionReachability, definition, no evidence levelReachabilitydefinitionConnected graph, definition, no evidence levelConnected graphdefinitionEuler's formula for planar graphs, statement, no evidence levelEuler's formula for p…statementEdge bound for planar graphs, statement, no evidence levelEdge bound for planar…statementCrossing number inequality, statement, no evidence levelCrossing number inequ…statementUnit distance problem, problem, no evidence levelUnit distance problemproblem
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Big O notation definition
  2. Crossing number concept
  3. Euclidean distance concept
  4. Euclidean plane object
  5. Graph concept
  6. Graph definition
  7. Planar graph definition
  8. Probabilistic method concept
  9. Walk definition
  10. Reachability definition
  11. Connected graph definition
  12. Euler's formula for planar graphs statement
  13. Edge bound for planar graphs statement
  14. Crossing number inequality statement
  15. Unit distance problem problem

Further reading

  1. Web https://en.wikipedia.org/wiki/Unit_distance_graph
About this page
TagEPWB2JEXPE
URIm2://EPWB2JEXPE
Kindproblem
WritingW0 stub
MSC52C10, 05C62
StatusThis copy of the site has no build data. Run m2 status EPWB2JEXPE.
AboutEuclidean plane
UsesEuclidean plane, Euclidean distance, Big O notation, Crossing number inequality

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.