An Introduction to Ramsey Theory: Fast Functions, Infinity, and Metamathematics

“In any group of six people, there must exist three, any two of whom are acquainted, or three, any two of whom are not acquainted.” This old chestnut (easily proved as an application of the Pigeonhole Principle) appears as a worked-out example or exercise in many undergraduate combinatorics texts. Some, but not all, of these books point out that it is a special case of a more general combinatorial result proved by Frank Ramsey, and some of these books talk briefly about how this can be viewed as a very simple example of an area of mathematics known as Ramsey theory. Few undergraduate textbooks take matters much beyond this, however.

Thus, for example, although I had seen this result in various guises in textbooks over the years, I never knew before reading the book now under review that Ramsey theory had strong connections to mathematical logic. (Perhaps I should have known, or at least suspected, this, because Brualdi’s Introductory Combinatorics specifically refers to Ramsey as a logician, but I never pursued this connection.) The book by Katz and Reimann makes these connections quite clear, by providing a fascinating and very accessible first look at Ramsey theory and how it relates to such interesting topics as large cardinals and Gödel’s Incompleteness Theorem.

This little book is a gem. It is advertised as having minimal prerequisites. Such statements are often made but much less often accurate, but the claim seems entirely truthful here. The authors have taken pains to develop, as necessary, what background material is used in the book (no prior knowledge of logic is assumed, for example, and topics such as countable sets are discussed in detail), and have written this book in a clear, conversational tone that is certain to engage student interest.

There are four chapters. In the first, the authors look at several finite version of Ramsey’s theorem. To give an idea how this goes, consider the quoted problem that begins this review, now from a graph-theoretic standpoint. We can think of the six people as vertices, with an edge connecting any two of them, that edge being colored red if the people are acquaintances and blue if they are not. This configuration of six people and 15 edges forms what is known as the complete graph on six vertices, denoted K₆. So this simple problem can be viewed as saying that in any complete graph with six vertices where each edge is colored one of two colors, there is a monochromatic triangle (which we can think of as a K₃). More generally, suppose m and n are two positive integers; it turns out that there is a positive integer, and hence a smallest such positive integer N, such that any complete graph with N vertices, with the edges colored blue or red, contains an all-blue K_m or an all-red K_n. So, for example, with m = n = 3, we can take N = 6. The numbers for m = n get very large very fast, and explicit computation of them is an extremely challenging enterprise. This is in fact the subject of a famous quote by Paul Erdős​:

Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack.

The version of Ramsey’s theorem stated above is proved in this chapter (with all graph-theoretic material developed from scratch) and then promptly generalized to hypergraphs. (In a hypergraph, edges can contain more than two vertices; i.e., edges can now be arbitrary non-empty k-element subsets of the set of vertices instead of just two-element subsets.)

The next chapter looks at infinite Ramsey theory. The chapter begins with a statement and proof of a relatively elementary theorem on finite colorings of subsets of an infinite set and proceeds to more general results. The path to this point requires the introduction of a number of topics, all introduced ab initio: some basic topology (specifically, compactness), König’s lemma, cardinal and ordinal numbers, and the axiom of choice.

Chapter 3 begins with a statement and motivated proof of a wonderful Ramsey-like theorem of van der Waerden: if every positive integer is assigned one of a finite number of colors, then there are monochromatic arithmetic progressions of arbitrarily long finite length. This leads in short order to discussions of fast-growing functions and computability.

The fourth and final chapter of the book concerns a result called the Paris-Harrington theorem, which asserts that a certain variation of the finite Ramsey theorem, while true, is not provable in the first-order axiom system PA (Peano Arithmetic). Off the top of my head, I am not aware of any other undergraduate-level text that offers a statement and proof of this theorem. Here again, the relevant material is developed from scratch, so a good deal of this chapter talks about mathematical logic, Gödel’s Incompleteness Theorem, non-standard models of Peano Arithmetic, and other such topics. Indeed, even taken independently of the rest of the book, there is enough discussion of these topics here that a student who has heard of logic and models and Gödel’s work, and wants a quick summary of this material, could do far worse than skim this chapter.

This book has its origins in a course taught at the MASS (Mathematics Advanced Study Semester) program at Penn State University. (This program is described briefly in a forward to the text. A number of books originating from this program have appeared in the Student Mathematics Library series that includes this text, including, most recently, From Groups to Geometry and Back by Climenhaga and Katok, and Winding Around by Roe.) Being, first and foremost, a textbook, the book is designed to be read not by experts but by (good, well-motivated) undergraduate students. It has a number of exercises scattered throughout, and embedded in, the text. No solutions are provided, but some exercises are accompanied by hints as appropriate.

The upshot of all of this is a text that discusses some beautiful mathematics, not generally found in an undergraduate curriculum, and also has the added benefit of reminding students that mathematics is not always rigidly compartmentalized and that different areas of the subject may, on occasion, blend together in a mutually beneficial relationship. While the MASS program may be unique to Penn State, the book itself can certainly be used with profit in another university as a text for a senior seminar or capstone course. And faculty members who aren’t even teaching a course in the subject may enjoy flipping through it just for their own edification. I’m certainly glad that I own it.

Buy Now

Mark Hunacek (mhunacek@iastate.edu) teaches mathematics at Iowa State University.