cp's OEIS Frontend

A186705 The Erdős unit distance problem: the maximum number of occurrences of the same distance among n points in the plane.

%I A186705 #68 Sep 04 2025 10:53:37
%S A186705 0,1,3,5,7,9,12,14,18,20,23,27,30,33,37,41,43,46,50,54,57
%N A186705 The Erdős unit distance problem: the maximum number of occurrences of the same distance among n points in the plane.
%C A186705 An upper bound is floor(k*n^(4/3)), A129011, if k is close enough to 1. Also a(27)=81 (Hamming 3,3 graph). - _Ed Pegg Jr_, Feb 02 2018
%D A186705 P. Brass, W. O. J. Moser, J. Pach, Research Problems in Discrete Geometry, Springer (2005), p. 183
%H A186705 Boris Alexeev, Dustin G. Mixon, and Hans Parshall, <a href="https://arxiv.org/abs/2412.11914">The Erdős unit distance problem for small point sets</a>, arXiv:2412.11914 [math.CO], 2024. See pp. 1, 12.
%H A186705 Thomas Bloom, <a href="https://www.erdosproblems.com/90">Does every set of n distinct points in R^2 contain at most n^(1+O(1/log log n)) many pairs which are distince 1 apart?</a>, Erdős Problems.
%H A186705 Jean-Paul Delahaye, <a href="http://www.pourlascience.fr/ewb_pages/a/article-les-graphes-allumettes-33448.php">Les graphes-allumettes</a>, (in French), Pour la Science no. 445, November 2014, pages 108-113. (On page 112, for n=6, drawing 2, one segment is missing.)
%H A186705 Paul Erdős, <a href="http://www.renyi.hu/~p_erdos/1946-03.pdf">On sets of distances of n points</a>, American Mathematical Monthly 53, pp. 248-250 (1946).
%H A186705 Sascha Kurz, <a href="http://arxiv.org/abs/2112.12716">Plane point sets with many squares or isosceles right triangles</a>, arXiv:2112.12716 [math.CO], 2021.
%H A186705 Ed Pegg Jr, <a href="https://math.stackexchange.com/questions/2575268/maximally-dense-unit-distance-graphs">Maximally Dense Unit Distance Graphs</a>
%H A186705 Terence Tao, <a href="https://github.com/teorth/erdosproblems/blob/main/README.md#table">Erdős problem database</a>, see no. 90.
%H A186705 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ErdosUnitDistanceProblem.html">Erdos Unit Distance Problem</a>.
%H A186705 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MaximallyDenseUnit-DistanceGraph.html">Maximally Dense Unit-Distance Graph</a>.
%e A186705 a(4) = 5 because there is a unit distance graph with 4 vertices of an equilateral rhombus such that all but one of the six pairs of vertices are unit distance apart.
%e A186705 Comment from _Allan C. Wechsler_, Sep 17 2018: (Start)
%e A186705 Construction for a(9)=18: Take a convex, equilateral hexagon ABCDEF. Make the angles vary a bit, though, to avoid the hexagon being regular. Now, on each of the six sides, construct an equilateral triangle pointing into the hexagon. In general, the triangles will overlap here and there; this is OK because we aren't going to care about edges crossing each other. So we have triangles ABU, BCV, CDW, DEX, EFY, and FAZ: a total of twelve points with 18 unit distances among them.
%e A186705 Now adjust the hexagon to make some pairs of the internal points coincide. We want to make U=X, V=Y, and W=Z. The resulting linkage still has one degree of freedom, so we can arrange it so that none of the edges coincide (they can and must cross, though). The adjusted hexagon will only have two different angles: ABC = CDE = EFA, and BCD = DEF = FAB. The whole thing will have triangular (D_6) symmetry. It will have nine vertices (after merging three pairs from the original 12) but it will still have 18 unit edges. (End)
%Y A186705 Cf. A047932, A051602, A063545, A129011, A186926, A293956.
%Y A186705 Cf. A385657 (number of nonisomorphic maximally dense unit-distance graphs).
%K A186705 nonn,hard,more,nice,changed
%O A186705 1,3
%A A186705 _Michael Somos_, Feb 25 2011
%E A186705 Extended to a(21) using values from Version 2 of the Alexeev et al. arXiv manuscript. - _N. J. A. Sloane_, Jun 24 2025