Ramsey Theory on the Integers

Abstract

Ramsey Theory, a branch of Combinatorics, is the study of occurrence of monochromatic subobjects in a given objects. Rainbow Ramsey Theory is another face of this die of Combinatorics where instead of looking at monochromatic subobjects, we look for heterochromatic subobjects. In an abstract non mathematics way, one may call it, the study of order in chaos, the unavoidable consistent occurrence in something completely ran dom. In Ramsey Theory, van der Waerden’s Theorem proves the existence of unavoidable monochromatic arithmetic progressions of finite length within randomly colored larger yet still finite arithmetic progressions, where the length of the larger arithmetic progressions are called van der Waerden numbers. Similar to Ramsey Theory, Rainbow Ramsey Theory has anti-van der Waerden numbers which are the minimum number of colors to ensure existence of a heterochromatic arithmetic progression of finite terms within a possibly larger yet finite randomly colored arithmetic progression. Anti-van der Waerden numbers can be thought of as the counter part of van der Waerden numbers in Rainbow Ramsey Theory. The thesis starts with the very basics of Ramsey Theory, builds up to Rainbow Ramsey Theory, anti-van der Waerden numbers and ends with a new bound on anti-van der Waerden numbers for arithmetic progression of k terms.