For the Erdos Unit Distance Problem, it's stated that the upper bound on unit lengths on $n$ points is $n^{4/3}$.

What unit-distance graphs come closest to this bound?

The Hamming $H_{3,3}$ graph exactly meets this bound of 4/3, with 81 edges and 27 vertices.


The best on a triangular grid seems to be 55 vertices and 192 unit edges, for a bound of 1.31197.

unit distance graph on 55 points

Twelve layers of 30-gons leads to with 391 vertices with 2190 unit edges. log(2190)/log(391) = 1.28899.

unit distance graph on 391 points

In three dimensions, the maximal log(unit edges)/log(points) seems to be 1.43392 with 14 points producing 44 unit edges. The points are {{0,0,0}, {3,0,3}, {3,3,0}, {3,-3,0}, {3,0,-3},{0,3,-3}, {6,0,0}, {2,-1,1}, {-1,2,1}, {-1,-1,-2}, {-1,-1,4}, {-1,-4,1},{-4,-1,1}, {2,-4,4}}/(3 sqrt(2)). They look like the following:

enter image description here

What are the other unit-distance graphs that come closest to the upper bounds?

  • $\begingroup$ The upper bound also has a constant factor, so this question doesn't make that much sense. Densest known UDG is the grid (with a suitable side length). $\endgroup$ – domotorp May 11 at 4:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.