##
**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