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 $\mathcal{ F}$, where $[1,n]=\{ 1,2,3,\ldots,n\}$ and $\mathcal{ F}$ is a certain family of subsets of $\mathbb{ Z}^+$. When $\mathcal{ 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 $\mathcal{ F}$ to be the set of semi-progressions of scope $m$. A semi-progression of scope $m\in \mathbb{ Z}^+$ is a set of integers $\{ x_1,x_2,\ldots,x_k\}$ such that for some $d\in\mathbb{ Z}^+$, $x_{ i}-x_{ i-1}\in\{ d,2d,\ldots,md\}$ for all $i\in\{ 2,3,\ldots,k\}$. The exact values of Ramsey-type functions corresponding to semi-progressions are not known. We use $SP_m(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 $Q_1(k)$. When $\mathcal{ F}$ is chosen to be quasi-progressions of diameter $n$, the corresponding Ramsey-type numbers obtained are denoted as $Q_n(k)$. The last chapter gives an exposition of advanced probabilistic techniques, in particular concentration inequalities and how to apply them.
Categories: math.CO