OFFSET
1,3
COMMENTS
An upper bound is floor(k*n^(4/3)), A129011, if k is close enough to 1. See Spencer-Szemeredi-Trotter. Also a(27)>=81 (Hamming 3,3 graph). - Ed Pegg Jr, Feb 02 2018 [Corrected by Tim Huegerich, May 28 2026]
The best upper bound for a(27) was 90 according to the Alexeev, Mixon and Parshall paper (and its 2025 revision), which established stronger upper bounds for a(22..30) alongside exact values up to a(21). - Peter Munn, May 24 2026
REFERENCES
P. Brass, W. O. J. Moser, and J. Pach, Research Problems in Discrete Geometry, Springer (2005), p. 183.
J. Spencer, E. Szemeredi and W. T. Trotter, Unit distances in the Euclidean plane, Graph Theory and Combinatorics, B. Bollabas editor, London: Academic Press, 1984, pp. 293-308.
LINKS
Boris Alexeev, Dustin G. Mixon, and Hans Parshall, The Erdős unit distance problem for small point sets, arXiv:2412.11914 [math.CO], 2024. See pp. 1, 12.
Noga Alon, Thomas F. Bloom, W. T. Gowers, Daniel Litt, Will Sawin, Arul Shankar, Jacob Tsimerman, Victor Wang and Melanie Matchett Wood, Remarks on the disproof of the unit distance conjecture, arXiv 2605.20695 [math.CO], 2026.
Thomas Bloom, Problem 90, Erdős Problems.
Jean-Paul Delahaye, Les graphes-allumettes, (in French), Pour la Science no. 445 (November 2014) 108-113. (On page 112, for n=6, drawing 2, one segment is missing.)
Paul Erdős, On sets of distances of n points, Amer. Math. Monthly (1946) Vol. 53, 248-250.
Erdős problems database contributors, Erdős problem database, see no. 90.
Michael K.-H. Kiessling and David J. Wales, A note on the minimal pairwise distance in optimal Lennard-Jones N-body clusters, Molec. Phys. (2025). See p. 13. See also arXiv:2511.15008 [physics.atm-clus], 2025. See p. 14.
Sascha Kurz, Plane point sets with many squares or isosceles right triangles, arXiv:2112.12716 [math.CO], 2021.
Ed Pegg Jr, Maximally Dense Unit Distance Graphs.
Will Sawin, An Explicit Lower Bound for the Unit Distance Problem, May 2026.
Eric Weisstein's World of Mathematics, Erdos Unit Distance Problem.
Eric Weisstein's World of Mathematics, Maximally Dense Unit-Distance Graph.
EXAMPLE
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.
Comment from Allan C. Wechsler, Sep 17 2018: (Start)
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.
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)
CROSSREFS
KEYWORD
nonn,hard,more,nice,changed
AUTHOR
Michael Somos, Feb 25 2011
EXTENSIONS
Extended to a(21) using values from Version 2 of the Alexeev et al. arXiv manuscript. - N. J. A. Sloane, Jun 24 2025
STATUS
approved