Erdos Unit Distance Problem -- Maximal graphs

783 Views Asked by At

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.

Hamming_{3,3}

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?