= Multicolour Ramsey bound
{title2=$R_k(3)\le k(R_{k-1}(3)-1)+2\le3k!$}
Let $R_k(3)$ be the least order of a <complete graph> whose every $k$-edge-colouring has a <monochromatic> <triangle in a graph>. At a vertex of a graph of order $k(R_{k-1}(3)-1)+2$, some colour joins at least $R_{k-1}(3)$ neighbours. An edge of that colour among these neighbours completes a triangle; otherwise the neighbours use at most $k-1$ colours and contain a triangle by induction. This proves the recurrence and the weaker explicit bound $R_k(3)\le3k!$.
Back to article page
