Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  798.52017
Autor:  Erdös, Paul; Makai, Endre; Pach, János
Title:  Nearly equal distances in the plane. (In English)
Source:  Comb. Probab. Comput. 2, No.4, 401-408 (1993).
Review:  The authors prove that for every positive integer k and for every \epsilon > 0 there exist numbers n0 > 0 and c > 0 such that every set of n > n0 points in the Euclidean plane in pairwise distances at least 1 has the following property: for arbitrary reals t1,..., tk, the number of pairs of points whose distance belongs to the set \bigcupi = 1k [ti, ti+c\sqrt{n}] is at most (n2/2) (1- 1/(k+1)+\epsilon). This bound is asymptotically best possible. The proof generalizes the considerations of the authors and J. Spencer [DIMACS, Ser. Discret. Math. Theor. Comput. Sci. 4, 265-273 (1992; Zbl 741.52010)].
Reviewer:  M.Lassak (Bydgoszcz)
Classif.:  * 52C10 Erdoes problems and related topics of discrete geometry
Keywords:  distance; graph; subgraph; points; Euclidean plane
Citations:  Zbl 741.52010

© 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