Ramsey’s theorem

The original version of Ramsey’s theorem states that forevery positive integers $k_1$ and $k_2$ there is $n$ such that ifedges of a complete graph on $n$ vertices are colored in twocolors, 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 proveinduction step we consider the graph $G$ that contains no cliquesof 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 sinceit contains no $k_1-1$-clique of color $1$ and no $k_2$-clique ofcolor $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 largegraph 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 iscalled 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 proofshows that $R(k_1,k_2)\le R(k_1,k_2-1)+R(k_1-1,k_2)$. From thatit 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$. Thelower bounds can be established by means of probabilisticconstruction 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 amonochromatic clique is $2^{1-k}$. Let $I_r$ be the randomvariable which is $1$ if $r$’th set of $k$ elements ismonochromatic clique and is $0$ otherwise. The sum $I_r$’sover all $k$-element sets issimply the number of monochromatic $k$-cliques. Therefore bylinearity 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. Alittle exercise in calculus shows that if we choose $n$ to be no morethan ${(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) forseveral 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 equallymysterious. For this case Ajtai, Komlós andSzemerédi[1] proved that $R(k,x)\le c_k{x}^{k-1}/{(\ln )}^{k-2}$. The matching lower bound has onlyrecently been established for $k=3$ by Kim[4]. Even in this case the asymptotics isunknown. The combination of results of Kim and improvement ofAjtai, 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 todetermine Ramsey numbers for small $k_1$ and $k_2$. An up-to-datesummary of our knowledge about small Ramsey numbers can be foundin [5].