# Ramsey numbers

Define $R(a,b)$ to be the least integer $N$ such that, in any red-blue 2-coloring of the edges of a $N$-vertex complete graph^{} ${K}_{N}$,
there must exist either an all-red ${K}_{a}$ or an all-blue ${K}_{b}$.

Frank Ramsey proved these numbers always exist. He famously pointed out that among any 6 people, some three are mutual friends or some three mutual non-friends. That is, $R(3,3)\le 6$. Since a red pentagon with a blue pentagram drawn inside it has no monochromatic triangle, $R(3,3)\ge 6$. So $R(3,3)=6$.

Special attention is usually paid to the diagonal $R(k,k)$, which is often just written $R(k)$.

One can also generalize this in various ways,
e.g. consider $R(a,b,c)$ for three-colorings^{} of edges, etc (any number of
arguments^{}), and allow general sets of graphs, not just pairs of complete^{} ones.

Ramsey numbers^{} are very difficult to determine.
To prove lower bounds, construct good edge-colorings of some ${K}_{N}$ and, use a clique-finder
to find the largest mono-colored cliques.
To prove upper bounds, the main tool has been $R(a,b)\le R(a-1,b)+R(b-1,a)$
which implies $R(a,b)\le \left(\genfrac{}{}{0pt}{}{a+b-2}{a-1}\right)$ and then $R(k)\le [1+o(1)]{4}^{k}/(4\sqrt{\pi k}$
when $k\to \mathrm{\infty}$.
From considering random colorings and using a probabilistic nonconstructive existence
argument, one may show $R(k)\ge k{2}^{k/2}[o(1)+\sqrt{2}/e]$.
It is known that $R(1)=1$, $R(2)=2$, $R(3)=6$, $R(4)=18$, and $43\le R(5)\le 49$.
For a survey of the best upper and lower bounds available on small
Ramsey numbers, see
http://www.combinatorics.org/Surveys/ds1.pdfRadziszowski’s survey
(http://www.cs.rit.edu/ spr/alternate link).
Another kind of Ramsey-like number which has not gotten as much attention as it deserves,
are Ramsey numbers for directed graphs.
Let $\overrightarrow{R}(n)$ denote the least integer $N$ so that any tournament^{} (complete directed graph^{}
with singly-directed arcs) with $\ge N$ vertices contains an acyclic (also called “transitive^{}”)
$n$-node tournament. (Analogies^{}: 2-color the edges $\to $ two directions for arcs.
Monochromatic $\to $ acyclic, i.e. all arcs “point one way.”)

Again, to prove lower bounds, construct good tournaments and apply something like
a clique-finder (but instead aimed at trying to find the largest acyclic induced subgraph^{}).
To prove upper bounds, the main tool is $\overrightarrow{R}(n+1)\le 2\overrightarrow{R}(n)$.
That can be used to show the upper bound, and
random-orientation arguments combined with a nonconstructive probabilistic existence argument
show the lower bound, in $[1+o(1)]{2}^{n+1)/2}\le \overrightarrow{R}(n)\le 55\cdot {2}^{n-7}$.
It is known that $\overrightarrow{R}(1)=1$,
$\overrightarrow{R}(2)=2$,
$\overrightarrow{R}(3)=4$,
$\overrightarrow{R}(4)=8$,
$\overrightarrow{R}(5)=14$,
$\overrightarrow{R}(6)=28$,
and
$32\le \overrightarrow{R}(7)\le 55$.
For a full survey of directed graph Ramsey numbers includng proofs and refererences,
see http://www.rangevoting.org/PuzzRamsey.htmlSmith’s survey.

Title | Ramsey numbers |
---|---|

Canonical name | RamseyNumbers |

Date of creation | 2013-03-22 16:16:32 |

Last modified on | 2013-03-22 16:16:32 |

Owner | wdsmith (13774) |

Last modified by | wdsmith (13774) |

Numerical id | 10 |

Author | wdsmith (13774) |

Entry type | Definition |

Classification | msc 05D10 |

Related topic | RamseysTheorem2 |

Defines | Ramsey numbers |