Introduction to Ramsey Theory: Students' Projects

Subsection 14.6.1 William Gasarch's favourite proof

Dr. Gasarch sent us a pdf file with proofs of two theorems: van der Waerden's theorem, [14.6.3.4] , and the polynomial van der Waerden theorem, [14.6.3.5]. The pdf file with Dr. Gasarch's proofs is available HERE.

Gasarch appreciates the original proof by van der Waerden for several reasons:

I like the original proof by van der Waerden, even though the proof by Shelah gives better bounds. Why do I like it?

1. It has the it is easier proof a harder theorem vibe in that it is easier to prove it for all \((k,c)\) rather than (say) proving that: For all \(k\in \mathbb{N}\) there exists \(W\) such that, for all \(2\)–colourings \(\chi: [W]\to [2]\text{,}\) there exist \(a,d\n\mathbb{N}\) such that \(\chi(a)=\chi(a+d)=\cdots =\chi(a+(k-1)d)\text{.}\)

2. The proof is elementary, and can be taught to high school students.

3. It serves as an example of proof by induction on an ordering other than natural numbers, specifically the \(\omega^2\) ordering.

4. The bounds are enormous. This is a good way to introduce the notions of primitive recursion and Ackerman's function to people. (Though be careful to say that this is the BOUND FROM THE PROOF and is not the real bound since Shelah and later Gowers got prim rec bounds.)

5. That the bounds (and even those of Shelah and Gowers) seem very far from the few actual numbers that are known is a humbling lesson on how in math we don?t know everything. [14.6.3.3]

In Professor Gasarch's words

I like the purely combinatorial proof by Walters even though (again!) the proof by Shelah gives better bounds. Why do I like it?

1. It has the it is easier proof a harder theorem vibe as well.

2. The proof is elementary, and can be taught to high school students. (Thought harder than vdW.)

3. It is a good example of proof by induction on an ordering other than natural numbers. It is on the \(\omega^\omega\) ordering.

4. The bounds are enormous, though this is not as impressive having seen vdW. The bounds are not that much bigger than vdW.

5. That the bounds (and even those of Shelah and Gowers) seem very far from the few actual numbers that are known is a humbling lesson on how in math we don?t know everything.

6. (Personal) The existence of an elementary proof of the Poly VDW theorem does not seem to be well known, so I've gotten a kick out of telling Ramsey Theorists who are much smarter than me of its existence. [14.6.3.3]

Subsection 14.6.2 Reflection

We are both impressed and touched by Professor Gasarch's willingness to share his knowledge with us. The way how he has reflected about the two proofs made us appreciate even more what we have learned in our math classes.