Edition:

2

Publisher:

John Wiley

Number of Pages:

208

Price:

185.00

ISBN:

0471500461

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 *c*_{1} *x*_{1} + *c*_{2} *x*_{2} + … + *c _{n} x_{n}* = 0 is regular if and only if some nonempty subset of the coefficients

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

Date Received:

Saturday, July 22, 2006

Reviewable:

Yes

Publication Date:

1990

Format:

Hardcover

Audience:

Category:

Textbook

Donald L. Vestal

12/17/2006

Sets.

Progressions.

Equations.

Numbers.

Particulars.

Beyond Combinatorics.

References.

Index.

Publish Book:

Modify Date:

Tuesday, February 17, 2009

- Log in to post comments