Rudiments of Ramsey Theory

Ramsey theory is part of combinatorics and is named after the British mathematician Frank Plumpton Ramsey (1903–1930). It doesn’t have a precise definition, but deals with problems of this general form: If a set has a structural property, and the set is then divided into finitely many parts, then at least one of the parts also has the property. A famous example is van der Waerden’s 1927 theorem on arithmetic progressions: We already know that the positive integers contain arbitrarily long arithmetic progressions, and the conclusion is that if the positive integers are partitioned into finitely many subsets, then at least one subset contains arbitrarily long arithmetic progressions. Most of the problems in Ramsey theory also have a finite version with an extremal-combinatorics flavor. For example, the van der Waerden problem can be restated as: for each number of partitions \(r\) and desired progression length \(k\), we seek the minimum number \(W(r,k)\) such that any such partition of the first \(W(r,k)\) positive integers into \(r\) parts will have a progression of length \(k\). In fact, a lot of work in Ramsey theory is in developing bounds in the finite versions.

This is a very erudite book that packs a lot of useful information into a small space. It succeeds in several goals: stating the major results carefully, giving useful applications, explaining the useful techniques, and describing a large number of unsolved problems and conjectures. It’s primarily a survey and not a proofs book, and in most cases only sketches of proofs are given. The writing is very clear, and there a few jokes scattered through the footnotes. There are lots of good exercises.

The present book is a revision of the 1981 first edition. It overlaps the much more extensive text Ramsey Theory by Graham, Rothschild, and Spencer. The present book is not a drastic revision, but has been updated with the latest results and so is in some ways more up-to-date than the larger text.

Buy Now

Allen Stenger is a math hobbyist and retired software developer. He is an editor of the Missouri Journal of Mathematical Sciences. His mathematical interests are number theory and classical analysis.