Here’s the plan for Tuesday, June 16, for the Blue group:
- Everyone:
* Re-read the proof of Theorem 1.16 — the basic proof strategy will re-appear in later proofs of more expansive Ramsey-type theorems. It will be very helpful to start the proof by taking (with hindsight) \(N=2^{2k}\); that way, once you have (once) verified that \(\lceil (2^m-1)/2 \rceil = 2^{m-1}\) for any natural number \(m\), you get to avoid all the messy algebra at the end of the proof.
* Do exercise 1.18 (which is essentially the Bolzano-Weierstrass theorem for finite sequences).
* Think about the following much harder variant of exercise 1.18: part of that exercise asks you to show that there is a sequence of reals of length \(k^2\) that has neither an increasing nor a decreasing subsequence of length \(k+1\). Show that this is best possible, that is, show that every sequence of reals of length \(k^2+1\) has either an increasing or a decreasing subsequence of length \(k+1\).
* Study the proof of Theorem 1.19 (Ramsey’s theorem for colouring pairs, with many colors).
* Read Section 1.4, through at least to the proof of Theorem 1.24. - Individual assignments:
* For both parts of exercise 1.18, and the harder variant, I’ll throw it open to anyone who wants to volunteer ideas.
* Proof of Theorem 1.19 (Ramsey’s theorem about finding a monochromatic \(k\)-clique, when colouring with \(r\) colours): Sean.
* Exercise 1.20 (Schur’s theorem, a cute application of Ramsey’s theorem): Nick.
* Theorem 1.23 (another proof of Ramsey’s theorem, that uses “off-diagonal” Ramsey numbers): Henry.
* Theorem 1.24 (getting better upper bounds for Ramsey numbers, using the result of Theorem 1.23): Alex. (We may not get to this on Tuesday).