# Maximally dense Unit Distance Graphs

At Unit distance graph: Paul Erdős (1946) posed the problem of estimating how many pairs of points in a set of n points could be at unit distance from each other. In graph theoretic terms, how dense can a unit distance graph be?

$e = \left \lfloor{v^{4/3}}\right \rfloor$ is the Spencer-Szemerédi-Trotter upper bound. The Hamming 3,3 graph, with 27 vertices and 81 unit edges, meets this bound. I just noticed that this graph is non-rigid, so here's another embedding: Playing around with the infinite embeddings, I found this convergence. With 21 vertices and 57 edges, it also meets the upper bound. Are there other unit distance graphs that match the upper bound? According to A186705, there are maximal graphs for 9, 12, 13, and 14 vertices (18, 27, 30, 33 edges).

EDIT: Here's 16 vertices with 41 edges. From this, (13,14,15,16)->(30,33,37,41) can easily be derived. Notice that vertex set (1,2,11,15,12,16,6) makes a Moser spindle. Also note that $16^{4/3}=40.3175$, so this exceeds the Spencer-Szemerédi-Trotter upper bound. I was just reading last night that the bound had been proven in 6 different ways. Did I break it?

## 1 Answer

You might be misunderstanding the upper bound. It's more like the upper bound is $$O(n^{4/3})$$. The actual upper bound is $$cn^{4/3}$$ where $$c = 8$$. The paper establishing the upper bound can be found here. Thank you @domotorp for your comment which provided this paper which sets constant $$c = 8$$.