Thue proved that the minimal such diameter is achieved (asymptotically) by the points in a triangular lattice intersected with a circle. In general Erd\H{o}s believed such a set must have very large intersection with the triangular lattice (perhaps as many as $(1-o(1))n$).

Erd\H{o}s \cite{Er94b} wrote 'I could not prove it but felt that it should not be hard. To my great surprise both B. H. Sendov and M. Simonovits doubted the truth of this conjecture.' In \cite{Er94b} he offers \$100 for a counterexample but only \$50 for a proof.

The stated problem is false for $n=4$, for example taking the points to be vertices of a square. The behaviour of such sets for small $n$ is explored by Bezdek and Fodor \cite{BeFo99}.

See also [103].


References


[BeFo99] Bezdek, Andr\'{a}s and Fodor, Ferenc, Minimal diameter of certain sets in the plane. J. Combin. Theory Ser. A (1999), 105-111.

[Er94b] Erd\H{o}s, Paul, Some problems in number theory, combinatorics and combinatorial geometry. Math. Pannon. (1994), 261-269.