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\leq 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 $\abs{C_1}$ is bounded since it contains no $k_1-1$ -clique of color $1$ and no $k_2$ -clique of color $2$ . Similarly, $\abs{C_2}$ is bounded. QED.

Similar argument shows that for any positive integers 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 for multicolored graphs). The above proof shows that $R(k_1,k_2)\leq 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)\leq \binom{k_1+k_2-2}{k_1-1}$ . In the most interesting case $k_1=k_2=k$ this yields approximately $R(k,k)\leq (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}\binom{n}{k}$ . 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)\geq (\sqrt{2}+o(1))^{k}$ .

The gap between the lower and upper bounds has been open for several decades. There have been a number of improvements in $o(1)$ terms, but nothing better than $\sqrt{2}+o(1)\leq R(k,k)^{1/k}\leq 4+o(1)$ is known. It is not even known whether $\lim_{k\to \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)\leq 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 $\tfrac{1}{162}(1+o(1)) k^2/\log k \leq R(3,k)\leq (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].

References

1

Miklós Ajtai, János Komlós, and Endre Szemerédi.
A note on Ramsey numbers.
J. Combin. Theory Ser. A, 29(3):354-360, 1980.
Zbl 0455.05045.

2

Noga Alon and Joel H. Spencer.
The probabilistic method.
John Wiley & Sons, Inc., second edition, 2000.
Zbl 0996.05001.

3

Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer.
Ramsey Theory.
Wiley-Interscience series in discrete mathematics. 1980.
Zbl 0455.05002.

4

Jeong Han Kim.
The Ramsey number $R(3,t)$ has order of magnitude $t^2/\log t$ .
Random Structures & Algorithms, 7(3):173-207, 1995.
Zbl 0832.05084.
Preprint is available online.

5

Stanislaw Radziszowski.
Small Ramsey numbers.
Electronic Journal of Combinatorics, Dynamical Survey, 2002.
Available online.

6

James B. Shearer.
A note on the independence number of triangle-free graphs.
Discrete Mathematics, 46:83-87, 1983.
Zbl 0516.05053.
Abstract is available online