# 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}\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 $\left\lvert C_{1}\right\rvert$ is bounded since it contains no $k_{1}-1$-clique of color $1$ and no $k_{2}$-clique of color $2$. Similarly, $\left\lvert C_{2}\right\rvert$ is bounded. QED.

Similar argument shows that for any positive integers $k_{1},k_{2},\ldots,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},\ldots,k_{t})$ 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 (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)\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. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0455.05045Zbl 0455.05045.
• 2 Noga Alon and Joel H. Spencer. . John Wiley & Sons, Inc., second edition, 2000. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0996.05001Zbl 0996.05001.
• 3 Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer. Wiley-Interscience series in discrete mathematics. 1980. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0455.05002Zbl 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. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0832.05084Zbl 0832.05084. Preprint is http://research.microsoft.com/research/theory/jehkim/papers/ramsey5.pdfavailable online.
• 5 Stanislaw Radziszowski. Small Ramsey numbers. Electronic Journal of Combinatorics, Dynamical Survey, 2002. http://www.combinatorics.org/Surveys/ds1.pdfAvailable online.
• 6 James B. Shearer. A note on the independence number of triangle-free graphs. Discrete Mathematics, 46:83–87, 1983. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0516.05053Zbl 0516.05053. Abstract is http://www.research.ibm.com/people/s/shearer/abstracts/intfg.htmlavailable online
Title Ramsey’s theorem RamseysTheorem 2013-03-22 13:53:09 2013-03-22 13:53:09 bbukh (348) bbukh (348) 18 bbukh (348) Theorem msc 05D40 msc 05D10 RamseysTheorem ProbabilisticMethod Ramsey number