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}/{(\mathrm{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}/\mathrm{log}k\le R(3,k)\le (1+o(1)){k}^{2}/\mathrm{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. The probabilistic method. 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. Ramsey Theory. 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}/\mathrm{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 |
---|---|
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 |