Type: Seminar

Distribution: World

Expiry: 20 Sep 2012

Auth: gilesg@bari.maths.usyd.edu.au

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.