Ramsey Numbers – The Math


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:

Screen%20Shot%202014-04-11%20at%2012.53.15%20AM.png

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$.



The math online

Leave a Comment

Your email address will not be published. Required fields are marked *