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 Em. Let R(Kn,n,r) denote the property: For any r-coloring of En 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 En.) 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 S3 is an equilateral triangle of side 1 then R(S3,3,2) is true; if C2 is a unit square, then R(C2,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 Lk denotes the configuration of k collinear points separated by unit distance, then R(L3,n,4), R(L4,n,3), R(L5,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 Em 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 c1,c2, ... ,ck,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 ki = 1ci(xi-x0) = b has no solution x0,x1, ... ,xk where all the xi 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 (x1-y1)(x2-y2) = 1 always has solutions with color xi = color yi, i = 1,2. The set of vertices of a rectangular parallelepiped in En is called a brick. ``Every brick is Ramsey'' is a corollary of: If K1 (\subseteq En) and K2(\subseteq Em) are both Ramsey then so is K1 × K2(\subseteq En+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