11
$\begingroup$

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:

Hamming 3,3

Playing around with the infinite embeddings, I found this convergence. With 21 vertices and 57 edges, it also meets the upper bound.

maximal 21

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.

Maximum Unit-distance graph on 16 vertices

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?

$\endgroup$
6
$\begingroup$

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$.

$\endgroup$
1

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.