Máximamente densa Unidad de Distancia Gráficos

Question

En la Unidad de distancia gráfico: Paul Erdős (1946) plantea el problema de la estimación de cuántos pares de puntos en un conjunto de n puntos podría ser en la unidad de distancia el uno del otro. En el gráfico teórico términos, cómo densa puede una unidad de distancia del gráfico?

$e = \left \lfloor{v^{4/3}}\right \rfloor$ es el de Spencer-Szemerédi-Trotter límite superior. El Hamming 3,3 gráfico, con 27 vértices y 81 de la unidad de los bordes, se reúne esta obligado. Me acabo de dar cuenta que este gráfico no es rígido, así que aquí está otra de incrustación:

Jugando con el infinito incrustaciones, he encontrado esta convergencia. Con 21 vértices y 57 bordes, también cumple con el límite superior.

Hay otra unidad de distancia gráficos que coincide con el límite superior? De acuerdo a A186705, hay máxima gráficos 9, 12, 13, y 14 de vértices (18, 27, 30, 33 de los bordes).

EDIT: he Aquí 16 vértices con 41 bordes. A partir de este, (13,14,15 y 16)->(30,33,37,41) puede ser derivada. Observe que el conjunto de vértices (1,2,11,15,12,16,6) hace un Moser husillo.

También tenga en cuenta que $16^{4/3}=40.3175$, lo que supera la de Spencer-Szemerédi-Trotter límite superior. Estaba leyendo anoche que el obligado se había probado en 6 formas diferentes. No me rompe?

Answer 1

Usted puede ser malentendido, el límite superior. Es más como el límite superior es $O(n^{4/3})$. El actual límite superior es $cn^{4/3}$ para algunas constantes $c$. El papel de establecer el límite superior puede ser encontrado aquí.