Ramsey Number algorithm

Question

In general is there an algorithm to obtain Ramsey Number? For example how should I approach to get $R(2K_2, 2K_2)$ or R(3, 2K_2)?

Answer 1

At the moment, no efficient algorithm exists. In fact, we don't know the exact value of most Ramsey numbers. (See table of known values on Wikipedia.) Even the value of $R(5,5)$ is currently unknown!

As far as I know, the only algorithms for determining Ramsey numbers are terribly inefficient. For instance, we have the following trivial algorithm for determining the Ramsey number $R(k,\ell)$:

• Write $m = \max(k,\ell)$. Try every colouring of the edges of $K_m$ with the colours blue and red. For every colouring, see whether or not there is an induced subgraph on $k$ vertices with only blue edges, or an induced subgraph on $\ell$ vertices with only red edges.

• If every colouring contains at least one of the desired subgraphs, we are done. Otherwise, replace $m$ by $m + 1$ and repeat.

Of course this algorithm is horribly, horribly inefficient. It is however guaranteed to terminate, since every Ramsey number is finite. To answer your question: yes, there is an algorithm, but not a particularly good one.

For small values of $k$ and $\ell$, it is usually easier to do a bit of puzzling and find an ad hoc proof for the particular case at hand.