You are here

Ramsey Theory

Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer
Publisher: 
John Wiley
Publication Date: 
1990
Number of Pages: 
208
Format: 
Hardcover
Edition: 
2
Price: 
185.00
ISBN: 
0471500461
Category: 
Textbook
BLL Rating: 

The Basic Library List Committee strongly recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Donald L. Vestal
, on
12/17/2006
]

Ramsey Theory is (very loosely) the study of conditions under which a certain amount of order can be forced in some situation (how’s that for vague?), similar to what the pigeonhole principle does. Here are some precise examples of Ramsey theory results, which the authors refer to as the Super Six.

Ramsey’s Theorem. For all positive integers l, r, and k there exists N such that for any n greater than or equal to N, if the set of k-tuples of elements chosen from {1, 2, …, n} are colored using r colors, then there is a subset of k-tuples of l elements which are colored the same.

Van der Waerden’s Theorem. For all positive integers l, r, and k there exists N such that for any n greater than or equal to N, if the integers in the set {1, 2, …, n} are colored using r colors, then there is a subset of l elements, all of which have the same color, and which form an arithmetic progression.

Schur’s Theorem. For any positive integer r, there exists N such that for any n greater than or equal to N, if the integers in the set {1, 2, …, n} are colored using r colors, then there exist x, y, and z in this set which all have the same color and also satisfy the equation x + y = z.

Rado’s Theorem. The equation c1 x1 + c2 x2 + … + cn xn = 0 is regular if and only if some nonempty subset of the coefficients ci sums to zero. (Regular means that, for any positive integer r, there exists N such that for any n greater than or equal to N, if the integers in the set {1, 2, …, n} are colored using r colors, then there exist a solution to the given equation for which all of the xi have the same color.)

Hales-Jewett Theorem. For all positive integers r and k, there exists N such that for any n greater than or equal to N, if the points in the n-dimensional cube {0,1,…,k – 1}n are colored using r colors, then there exists a “line” on which all of the points have the same color.

Graham-Leeb-Rothschild Theorem. Let F be a finite field. For all positive integers k, l, and r there exists N such that the following holds for any n greater than or equal to N: Let V be an n-dimensional vector space over V. Color the k-dimensional subspaces of V with r colors. Then there exists an l-dimensional subspace of V all of whose k-dimensional subspaces have the same color.

This text provides a lot of the historical development of Ramsey theory, along with some related topics (such as Roth’s theorem and Szemerédi’s Theorem). And, as many of the proofs involve upper bounds of some type or another, the authors delve into the world of rapidly(!) growing functions.

This book does a great job at providing an overview of the different aspects and contexts of Ramsey theory. (Although, for the portion of Ramsey theory which involves the integers — Van der Waerden’s Theorem, Schur’s Theorem, and Rado’s Theorem — the best text is Landman and Robertson’s Ramsey Theory on the Integers.) Anyone interested in getting an introduction to Ramsey theory will find this book illuminating, provided they have a firm mathematical background. This is certainly not some light reading! While some of Ramsey theory is very ripe for undergraduate and graduate research, beginners may find Landman and Robertson’s text a kindler, gentler intro.


Donald L. Vestal is Assistant Professor of Mathematics at South Dakota State University. His interests include number theory, combinatorics, spending time with his family, and working on his hot sauce collection. He can be reached at Donald.Vestal(AT)sdstate.edu

Sets.

Progressions.

Equations.

Numbers.

Particulars.

Beyond Combinatorics.

References.

Index.