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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page