# Ramsey’s theorem

Ramsey’s theorem states that a particular arrows relation,

 $\omega\rightarrow(\omega)^{n}_{k}$

holds for any integers $n$ and $k$.

In words, if $f$ is a function on sets of integers of size $n$ whose range is finite then there is some infinite $X\subseteq\omega$ such that $f$ is constant on the subsets of $X$ of size $n$.

As an example, consider the case where $n=k=2$, and $f\colon[\omega]^{2}\rightarrow\{0,1\}$ is defined by:

 $f(\{x,y\})=\left\{\begin{array}[]{ll}1&\text{ if ~{}}x=y^{2}\text{ or ~{}}y=x^% {2}\\ 0&\text{otherwise}\end{array}\right.$

Then let $X\subseteq\omega$ be the set of integers which are not perfect squares. This is clearly infinite, and obviously if $x,y\in X$ then neither $x=y^{2}$ nor $y=x^{2}$, so $f$ is homogeneous on $X$.

Title Ramsey’s theorem RamseysTheorem 2013-03-22 12:55:49 2013-03-22 12:55:49 mathcam (2727) mathcam (2727) 9 mathcam (2727) Theorem msc 05D10 RamseysTheorem2 GraphTheory