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.
Reviewer: C.Schulz (Wiesbaden)
Classif.: * 52A37 Other problems of combinatorial convexity
05B10 Difference sets
52C10 Erdoes problems and related topics of discrete geometry
Keywords: difference set; distance set
Citations: Zbl 726.00015
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag