= Solution
The <diagonal Ramsey number> $R(t)$ is the least positive integer $n$ such that every red-blue colouring of the edges of $K_n$ contains a monochromatic $K_t$.
More generally, let $R(s,t)$ be the least $n$ forcing either a red $K_s$ or a blue $K_t$. We have
$$
R(1,t)=R(s,1)=1.
$$
Assuming the two smaller numbers exist, colour
$$
K_{R(s-1,t)+R(s,t-1)}
$$
and choose a vertex $v$. At least $R(s-1,t)$ of its incident edges are red, or at least $R(s,t-1)$ are blue. In the first case, the corresponding neighbourhood contains a red $K_{s-1}$, which extends with $v$ to a red $K_s$, or a blue $K_t$. The second case is symmetric. Thus
$$
R(s,t)\leq R(s-1,t)+R(s,t-1),
$$
which proves existence by induction.
Pascal's identity then gives the <binomial upper bound for a Ramsey number>
$$
R(s,t)\leq\binom{s+t-2}{s-1}.
$$
Consequently, for $t\geq2$,
$$
\boxed{R(t)=R(t,t)
\leq\binom{2t-2}{t-1}
\leq2^{2t-2}<2^{2t}.}
$$
Back to article page
