1989/08/01 by Paul Erdös, P. Erdös, Dean Hickerson +1 · 2 citations
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Computational Geometry and Mesh Generation #Advanced Graph Theory Research
paper · doi:10.1080/00029890.1989.11972243
We disprove a conjecture of Leo Moser by showing that (i) for every natural number n and 0 < α < 2 there is a system of n points on the unit sphere S2 such that the number of pairs at distance α from each other is at least const · n log* n (where log* stands for the iterated logarithm function) (ii) for every n there is a system of n points on S2 such that the number of pairs at distance √2 from each other is at least const - n4/3. We also construct a set of n points in the plane in general position (no 3 on a line, no 4 on a circle) such that they determine fewer than const · nlog3/log2 distinct distances, which settles a problem of Erdös.