COM-B2-M06-P013 Ramsey Recursion

Choose a vertex and split the remaining vertices into red and blue neighbours.

Let \(N=R(s-1,t)+R(s,t-1)\), and colour the edges of \(K_N\) red and blue. Choose a vertex \(v\). The remaining \(N-1\) vertices split into red neighbours and blue neighbours of \(v\).

If there are at least \(R(s-1,t)\) red neighbours, then inside them there is either a red \(K_{s-1}\) or a blue \(K_t\). In the first case, together with \(v\) we get a red \(K_s\); in the second case, we already have a blue \(K_t\).

If there are fewer than \(R(s-1,t)\) red neighbours, then there are at least \(R(s,t-1)\) blue neighbours. Inside them there is either a red \(K_s\), or a blue \(K_{t-1}\), which together with \(v\) gives a blue \(K_t\).

In all cases, the required structure exists.

This is the central technical problem of the module.