2014/04/29 by Mano Vikash Janardhanan, Janardhanan, Mano Vikash
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1404.7348
56 pages, MS thesis (completed in 2014), Supervisor: S. Vijay
arxiv created 2014/04/29 · arxiv updated 2014/04/30
Ramsey theory is the study of conditions under which mathematical objects show order when partitioned. Ramsey theory on the integers concerns itself with partitions of [1,n] into r subsets and asks the question whether one (or more) of these r subsets contains a k-term member of F, where [1,n]=\1,2,3,…,n\ and F is a certain family of subsets of ℤ+. When F is fixed to be the set of arithmetic progressions, the corresponding Ramsey-type numbers are called the van der Waerden numbers. I started the project choosing F to be the set of semi-progressions of scope m. A semi-progression of scope m∈ ℤ+ is a set of integers \x1,x2,…,xk\ such that for some d∈ℤ+, xi-xi-1∈\d,2d,…,md\ for all i∈\2,3,…,k\. The exact values of Ramsey-type functions corresponding to semi-progressions are not known. We use SPm(k) to denote these numbers as a Ramsey-type function of k for a fixed scope m. During this project, I used the probabilistic method to get an exponential lower bound for any fixed m. The first chapter starts with a brief introduction to Ramsey theory and then explains the problem considered. In the second chapter, I give the results obtained on semi-progressions. In the third chapter, I will discuss the lower bound obtained on Q1(k). When F is chosen to be quasi-progressions of diameter n, the corresponding Ramsey-type numbers obtained are denoted as Qn(k). The last chapter gives an exposition of advanced probabilistic techniques, in particular concentration inequalities and how to apply them.