Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 568.51011
Autor: Erdös, Paul
Title: Problems and results in combinatorial geometry. (In English)
Source: Discrete geometry and convexity, Proc. Conf., New York 1982, Ann. N.Y. Acad. Sci. 440, 1-11 (1985).
Review: [For the entire collection see Zbl 564.00011.]
This paper contains a large number of results and conjectures, and the author offers monetary rewards for proofs or disproofs of some of the conjectures. We list here the simplest problems in each of the first five sections of the paper.
(1) For any set of n points in a Euclidean plane, what is the minimum number of distances between the points, and what is the maximum number of pairs of points at unit distance apart?
(2) Given n points in a plane, not all collinear, a line joining two of them is an ordinary line if it contains no more than two of the points. What is the minimum number of ordinary lines? What are the possible values for the number of joining lines?
(3) Let Gk be a graph whose vertices are the points of k-dimensional Euclidean space Ek. Two points are joined if their distance is 1. Determine or estimate the chromatic number of Gk.
(4) Let z1,...,zn be n points within the unit circle. Let A3(z1,...,zn) denote the smallest area of all triangles formed by three of the points, and let g3(n) = maxz1,...,znA3(z1,...,zn). The latest result is g3(n) > (c log n)/n2.
(5) A finite subset C of Ek is called r-Ramsey for Ek if for every partition of Ek into r sets Si, \cupri = 1Si = Ek, some Si alwayscontains a subset that is congruent to C. Is it true that every non-equilateral triangle is 2-Ramsey in the plane?
Section 6 contains miscellaneous problems in nine separate groups. We quote from the final paragraphs: "Do there exist two point sets in the plane such that no matter how they are placed in the plane, their intersection contains exactly one point? I proved the existence of two such sets by transfinite induction.
"Does there exist a point set (in the plane) such that no matter how it is placed on the plane, it covers exactly one lattice point? I found this old problem of Steinhaus very challenging and got nowhere with it."
Reviewer: J.F.Rigby
Classif.: * 51D20 Combinatorial geometries
52A37 Other problems of combinatorial convexity
52A40 Geometric inequalities, etc. (convex geometry)
05A99 Classical combinatorial problems
00A07 Problem books
Keywords: combinatorial geometry; Ramsey problems; point set
Citations: Zbl 564.00011
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag