= Solution
The diagonal <diagonal Ramsey number> $R(s)$ is the least $n$ such that every red-blue edge coloring of $K_n$ contains a monochromatic $K_s$. More generally let $R(s,t)$ require a red $K_s$ or blue $K_t$. The base cases are $R(1,t)=R(s,1)=1$. Given $R(s-1,t)+R(s,t-1)$ vertices, select one vertex. Either it has at least $R(s-1,t)$ red neighbors or at least $R(s,t-1)$ blue neighbors. Applying the corresponding smaller problem and, when needed, adjoining that selected vertex gives
$$
R(s,t)\leq R(s-1,t)+R(s,t-1).
$$
Induction and Pascal's identity now prove existence and
$$
\boxed{R(s)=R(s,s)\leq\binom{2s-2}{s-1}\leq2^{2s-2}<4^s.}
$$
Back to article page
