# 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)\leq 6$. Since a red pentagon with a blue pentagram drawn inside it has no monochromatic triangle, $R(3,3)\geq 6$. So $R(3,3)=6$.

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

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)\leq R(a-1,b)+R(b-1,a)$ which implies $R(a,b)\leq{{a+b-2}\choose{a-1}}$ and then $R(k)\leq[1+o(1)]4^{k}/(4\sqrt{\pi k}$ when $k\to\infty$. From considering random colorings and using a probabilistic nonconstructive existence argument, one may show $R(k)\geq k2^{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\leq R(5)\leq 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 $\vec{R}(n)$ denote the least integer $N$ so that any tournament  (complete directed graph  with singly-directed arcs) with $\geq 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 $\vec{R}(n+1)\leq 2\vec{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}\leq\vec{R}(n)\leq 55\cdot 2^{n-7}$. It is known that $\vec{R}(1)=1$, $\vec{R}(2)=2$, $\vec{R}(3)=4$, $\vec{R}(4)=8$, $\vec{R}(5)=14$, $\vec{R}(6)=28$, and $32\leq\vec{R}(7)\leq 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 RamseyNumbers 2013-03-22 16:16:32 2013-03-22 16:16:32 wdsmith (13774) wdsmith (13774) 10 wdsmith (13774) Definition msc 05D10 RamseysTheorem2 Ramsey numbers