Let u(n) be the maximal number of unit distances present in a planar graph with n vertices. Download the list of these bounds here. When looking at the text files, note that a 'unit distance' in my program is 75.
| u(n) lower bounds | Point set images | + lines | Download points |
|---|
This program runs a pair of algorithms that find dense unit distance graphs. One is a 'gravity simulation', moving points closer together if they are more than a unit distance apart, and further apart if not. With a very particular choice of gravity function, this process is stable, and by regularly perturbing the points this can find the small (n < 40) examples I gave by itself.
To go higher, we use an optimization which simply looks for points in our set that are not very rich with unit circles, and moves them to places that are. When n is larger, as the previous algorithm settles on a set that is very stable, there are always suboptimal placements. This second process fights that very well.
The values for n up to 30 were known previously, and the values 1-14 were proven to be optimal by Schade in '93. In this paper, the authors show values up to n=30, which my program matches. Additionally, in this paper about the chromatic number of the plane, the authors critically use the same graph I found for 49 vertices, without mentioning that it may be the extremal example. Very interesting! Maybe more values are known, but I couldn't find them.
It is notable that almost every set above 30 that I found was a subset of a particular grid-like thing.
I wrote another program to just extrapolate this family to get a better idea of the asymptotic growth, and sadly, the family appears to have linear growth! You can see that initially, the growth looks like a very promising upward curve, but it soon becomes linear. So at some point, the square grid for example will provide graphs that are more dense.
