SUMS: Menzies -- Van der Waerden’s theorem on monochromatic arithmetic progressions

Speaker: Max Menzies (Cambridge undergrad)

Abstract:
Suppose you have the counting numbers 1,2,3,... and you colour each
number (a point on the number line) red or blue. There are many weird
and wonderful colourings that exist, but one aim of combinatorics (in
particular Ramsey Theory) is to find method within the madness.

So one question that can be asked is: can you always necessarily find
an infinite monochromatic arithmetic progression? That is too much to
ask for, as there is not always an infinite mono AP.

Van der Waerden’s theorem asserts the next best thing: that there are
always arbitrarily long finite monochromatic APs, no matter the
colouring. So I’ll talk about this theorem, since it is pretty and the
proof is very clever, using essentially just the pigeonhole principle
in smart ways. Also, upper bounds that come from the theorem are some
of the most ridiculously fast growing functions in all of maths. By
the end of this talk, functions like n! or n^n will seem tiny.