Ramsey Numbers
Table of Contents

Ramsey Numbers

Definition: The Ramsey Number, $R(s,t)$ is the least positive integer $n$ such that for any edge $2$-colouring of $E(K_n)$, there exists either a $K_s$ or a $K_t$ with a monochromatic colouring.

For example, the Ramsey number $R(3, 3) = 6$. We can prove this by seeing if $R(3, 3) \leq 6$. First, suppose that $R(3, 3) = 5$, and let's produce the following edge $2$-colouring:


In this colouring, we cannot find any subgraphs $K_3$ that are just red or just blue. Hence the Ramsey number $R(3,3) \geq 6$. We will not prove that $R(3, 3) = 6$ since it becomes a long and tedious process.

Nevertheless, we note that $R(s, 2) = s$ for $s > 2$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License