## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  741.52010
Autor:  Erdös, Paul; Makai, Endre; Pach, János; Spencer, Joel
Title:  Gaps in difference sets, and the graph of nearly equal distances. (In English)
Source:  Applied geometry and discrete mathematics, Festschr. 65th Birthday Victor Klee, DIMACS, Ser. Discret. Math. Theor. Comput. Sci. 4, 265-273 (1991).
Review:  [For the entire collection see Zbl 726.00015.]
Given n real numbers mutually differing by at least 1, let 1 \leq d1 \leq ... \leq dm, m = \binom{n}{2}, denote the increasing sequence of differences between them. The authors prove the asymptotically sharp bound

sumj = 1m-1(dj+1-dj)2 > c· log n,

and give sharp lower bounds for sumj = 1m-1\phi(dj+1-dj) for large class of monotone increasing convex functions \phi. They also show that for n points in the plane with minimal distance 1 and any real number t at most \lceil n2/4\rceil may have distances between t and t+1, and give an analogous result in terms of the diameter of the point set.