We’ve now seen Ramsey’s theorem, which concerns finding monochromatic cliques in graphs, and a generalization to hypergraphs (\(p\)-tuples). Now we move on Van der Waerden’s theorem, a somewhat more difficult result concerning finding monochromatic arithmetic progressions in colorings of the natural numbers. This is Chapter 3 of Reimann and Katz; we’ll go back to Chapter 2, on infinite Ramsey’s theorem, later.
The text doesn’t give a complete, formal proof of finite Van der Waerden. Instead, it discusses a few instances of showing the existence of some small finite Van der Waerden numbers, in a way that (hopefully) gives a good intuition for how a full proof should go.
- Everyone should read Chapter 3, through at least to the middle of page 94 (ignore the occasional reference back to Chapter 2).
- Everyone should think about Exercise 3.2 (construction of a 2-coloring of \({\mathbb N}\) that fails to have an infinite monochromatic arithmetic progression). Greyson and Joe can tell us about this.
- Here’s another exercise that everyone can think about, and I’ll throw it open to the group to discuss: is there a “soft” way to prove the existence of a 2-coloring of \({\mathbb N}\) that fails to have an infinite monochromatic arithmetic progression, without actually explicitly exhibiting such a coloring? Hint: how does the number of infinite arithmetic progression compare to the number of natural numbers?
- Ted and Anthony can go over the explanation of why the existence of \(W(k,2)\) for every \(k\) implies the existence of \(W(k,r)\) for every \(k\) and \(r\) (observation 3.1)
- Luca and Ryan can take us through a proof that \(W(3,2)\leq 325\). (Reimann and Katz go through this quite slowly and discursively; Luca and Ryan, in presenting this bound you can assume that we have all read the long discussion, and so you can be more concise. Start with the hypothesis that \(325\) works, and go through the four steps outlined on page 93, to verify that hypothesis. Pictures will help!)