Ramsey’s theorem

The original version of Ramsey’s theorem states that for every positive integers $k_1$ and $k_2$ there is $n$ such that if edges of a complete graph on $n$ vertices are colored in two colors, then there is either a $k_1$-clique of the first color or $k_2$-clique of the second color.

The standard proof proceeds by induction on $k_1+k_2$. If $k_1,k_2\le 2$, then the theorem holds trivially. To prove induction step we consider the graph $G$ that contains no cliques of the desired kind, and then consider any vertex $v$ of $G$. Partition the rest of the vertices into two classes $C_1$ and $C_2$ according to whether edges from $v$ are of color $1$ or $2$ respectively. By inductive hypothesis $\left|C_1\right|$ is bounded since it contains no $k_1-1$-clique of color $1$ and no $k_2$-clique of color $2$. Similarly, $\left|C_2\right|$ is bounded. QED.

Similar argument shows that for any positive integers $k_1,k_2,\mathrm{\dots },k_t$ if we color the edges of a sufficiently large graph in $t$ colors, then we would be able to find either $k_1$-clique of color $1$, or $k_2$-clique or color $2$,…, or $k_t$-clique of color $t$.

The minimum $n$ whose existence stated in Ramsey’s theorem is called Ramsey number and denoted by $R(k_1,k_2)$ (and $R(k_1,k_2,\mathrm{\dots },k_t)$ for multicolored graphs). The above proof shows that $R(k_1,k_2)\le R(k_1,k_2-1)+R(k_1-1,k_2)$. From that it is not hard to deduce by induction that $R(k_1,k_2)\le \left(\genfrac{}{}{0pt}{}{k_1+k_2-2}{k_1-1}\right)$. In the most interesting case $k_1=k_2=k$ this yields approximately $R(k,k)\le {(4+o(1))}^k$. The lower bounds can be established by means of probabilistic construction as follows.

Take a complete graph on $n$ vertices and color its edges at random, choosing the color of each edge uniformly independently of all other edges. The probability that any given set of $k$ vertices is a monochromatic clique is $2^{1-k}$. Let $I_r$ be the random variable which is $1$ if $r$’th set of $k$ elements is monochromatic clique and is $0$ otherwise. The sum $I_r$’s over all $k$-element sets is simply the number of monochromatic $k$-cliques. Therefore by linearity of expectation $E(\sum I_r)=\sum E(I_r)=2^{1-k}\left(\genfrac{}{}{0pt}{}{n}{k}\right)$. If the expectation is less than $1$, then there exists a coloring which has no monochromatic cliques. A little exercise in calculus shows that if we choose $n$ to be no more than ${(2+o(1))}^{k/2}$ then the expectation is indeed less than $1$. Hence, $R(k,k)\ge {(\sqrt{2}+o(1))}^k$.

The gap between the lower and upper bounds has been open (http://planetmath.org/Open3) for several decades. There have been a number of improvements in $o(1)$ terms, but nothing better than $\sqrt{2}+o(1)\le R{(k,k)}^{1/k}\le 4+o(1)$ is known. It is not even known whether ${lim}_{k\to \mathrm{\infty }}R{(k,k)}^{1/k}$ exists.

The behavior of $R(k,x)$ for fixed $k$ and large $x$ is equally mysterious. For this case Ajtai, Komlós and Szemerédi[1] proved that $R(k,x)\le c_k{x}^{k-1}/{(\ln )}^{k-2}$. The matching lower bound has only recently been established for $k=3$ by Kim [4]. Even in this case the asymptotics is unknown. The combination of results of Kim and improvement of Ajtai, Komlós and Szemerédi’s result by Shearer [6] yields $\frac{1}{162}(1+o(1))k^2/\log k\le R(3,k)\le (1+o(1))k^2/\log k$.

A lot of machine and human time has been spent trying to determine Ramsey numbers for small $k_1$ and $k_2$. An up-to-date summary of our knowledge about small Ramsey numbers can be found in [5].

Title	Ramsey’s theorem
Canonical name	RamseysTheorem
Date of creation	2013-03-22 13:53:09
Last modified on	2013-03-22 13:53:09
Owner	bbukh (348)
Last modified by	bbukh (348)
Numerical id	18
Author	bbukh (348)
Entry type	Theorem
Classification	msc 05D40
Classification	msc 05D10
Related topic	RamseysTheorem
Related topic	ProbabilisticMethod
Defines	Ramsey number