Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 595.52013
Autor: Erdös, Paul
Title: On some metric and combinatorial geometric problems. (In English)
Source: Discrete Math. 60, 147-153 (1986).
Review: Most of the problems surveyed are (for obvious reasons) almost as old as the author; almost all are metric and combinatorial, dealing with distances determined by a finite set of points. A sampling of the problems follows. Let S denote a set of n points in the plane, f(S) the number of different distances determined by the (pairs of) points of S, g(S) the number of times distance 1 is realized, f(n) the minimum of f(S) and g(n) the maximum of f(S) (max and min taken over all sets S of n points). Find f(n) and g(n) forsmall n; findbounds for large n. If S implements f(n) (i.e., f(S) = f(n)) mustS havelattice structure? Assuming f(S) = o(n), must there always be 4 points in S which determine at most 3 different distances? Suppose Scontains no isosceles triangles; how small can f(S) be? Assume S implements f(n); is it then true that, for every k, S contains a subset of k points which implements f(k)? In particular, must S contain an equilateral triangle? How many different sets of n points implement f(n)? (Two sets are different if they are not related by a similarity transformation.) Let this number be r(n). r(3) = r(5) = 1 while r(4) = 3. What about other values? Can one implement f(n) and g(n) simultaneously? Certainly yes for small n, but what about all n? If the points of S are the vertices of a convex n-gon, must one of the vertices be such that among the n-1 segments joining it to the others there are at least [n/2] distinct distances? There are many many more problems. Recent progress by Ajtai, Beck, Komlós, Spencer, Szemerédi and others is reported, conjectures are made, prizes are offered. This is another in a series of papers in which the author updates old problems, presents new ones, focuses on directions for new results and continues to influence this area of combinatorics with generosity and ingenuity.
Reviewer: W.Moser
Classif.: * 52A37 Other problems of combinatorial convexity
52A40 Geometric inequalities, etc. (convex geometry)
51D20 Combinatorial geometries
11B75 Combinatorial number theory
05A99 Classical combinatorial problems
05A20 Combinatorial inequalities
52A10 Convex sets in 2 dimensions (including convex curves)
00A07 Problem books
Keywords: combinatorial geometry; distances; survey; finite point sets in the; plane
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag