Ramsey Theory on the Integers

Abstract

Ramsey Theory, a branch of Combinatorics, is the study of occurrence of monochro- matic 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 hete- rochromatic 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 ex- istence 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 The- ory. 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.