##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 276.05001

**Autor: ** Erdös, Paul; Graham, Ronald L.; Montgomery, P.; Rothschild, B.L.; Spencer, Joel; Straus, E.C.

**Title: ** Euclidean Ramsey theorems. I. (In English)

**Source: ** J. Comb. Theory, Ser. A 14, 341-363 (1973).

**Review: ** The abstract states: ``The general Ramsey problem can be described as follows: Let A and B be two sets, and R a subset of A × B. For a in A denote by R(a) the set **{**b in B | (a,b) in R **}**. R is called r-Ramsey if for any r-part partition of B there is some a in A with R(a) is one part. We investigate questions of whether or not certain R are r-Ramsey where B is a Euclidean space and R is defined geometrically.'' – Let K be a set of k points in Euclidean m-space E^{m}. Let R(Kn,n,r) denote the property: For any r-coloring of E^{n} there is a monochromatic set K' congruent to K. (More generally, K' is the image of K under some element of a group H of transformations on E^{n}.) For example, (the authors prove that) if P is a pair of points distance d apart then R(P,2,7) is false [see *L. Moser* and *W.Moser*, Can. Math. Bull. 4, 187-189 (1961)] while R(P,2,3) is true. [See *H. Hadwiger* and *H. Debrunner*, Combinatorial Geometry in the Plane (German original 1960; Zbl 089.17302; English transl. with *Klee*, 1964)]. If S_{3} is an equilateral triangle of side 1 then R(S_{3},3,2) is true; if C_{2} is a unit square, then R(C_{2},6,2) is true; if T is any set of three points, then R(T,3,2) is true; if T is a 30^{\circ}--60^{\circ} right triangle then R(T,2,2) is true; if L = **{**(-1,0),(0,0),(1,1) **}** then R(L,3,2) is true, if L_{k} denotes the configuration of k collinear points separated by unit distance, then R(L_{3},n,4), R(L_{4},n,3), R(L_{5},n,2) are false for all n. – A configuration (set) K is said to be Ramsey if for each r there is an n for which R(K,n,r) is true. K is spherical in E_{m} if it is embeddable in the surface of a (hyper)sphere. Theorem. If K is not spherical then K is not Ramsey. The proof depends on the lemma: Let c_{1},c_{2}, ... ,c_{k},b be real numbers, b \ne 0. Then there exists an integer r, and some r-coloring of the real numbers, such that the equation **sum** ^{k}_{i = 1}c_{i}(x_{i}-x_{0}) = b has no solution x_{0},x_{1}, ... ,x_{k} where all the x_{i} have the same color. This lemma extends the fundamental work of *R. Rado* [Proc. London Math. Soc. 2nd Ser. 48, 122-160 (1943)]. Also proved is: if Q (the rationals) is colored with k colors then the equation (x_{1}-y_{1})(x_{2}-y_{2}) = 1 always has solutions with color x_{i} = color y_{i}, i = 1,2. The set of vertices of a rectangular parallelepiped in E^{n} is called a brick. ``Every brick is Ramsey'' is a corollary of: If K_{1} (\subseteq E^{n}) and K_{2}(\subseteq E^{m}) are both Ramsey then so is K_{1} × K_{2}(\subseteq E^{n+m}). – The paper combines the best features of exposition, survey, research, and questions for further investigation. It will be read with pleasure by combinatorists, geometers, researchers and students.

**Reviewer: ** W.Moser

**Classif.: ** * 05A05 Combinatorial choice problems

05A17 Partitions of integres (combinatorics)

05B30 Other designs, configurations

05-02 Research monographs (combinatorics)

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag