{
  "id": "1404.7348",
  "version": "v1",
  "published": "2014-04-29T13:13:03.000Z",
  "updated": "2014-04-29T13:13:03.000Z",
  "title": "Topics in Ramsey Theory",
  "authors": [
    "Mano Vikash Janardhanan"
  ],
  "comment": "56 pages, MS thesis (completed in 2014), Supervisor: S. Vijay",
  "categories": [
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-04-29T13:13:03.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "ramsey theory",
      "corresponding ramsey-type numbers",
      "semi-progression",
      "ramsey-type function",
      "van der waerden numbers"
    ],
    "tags": [
      "dissertation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 56,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1404.7348V"
    }
  }
}