Past exam of the mathematics course of the University of Cambridge / 2008 / ii / Paper 4 / 17F / Solution

Define the multicolour graph Ramsey number $R_k(s_1,\dots ,s_k)$ as the least $n$ such that every colouring of the edges of the complete graph $K_n$ with $k$ colours contains, for some $i$, a complete subgraph on $s_i$ vertices all of whose edges have colour $i$.

Prove finiteness by induction on ${\sum }_i{s}_i$, temporarily allowing $s_i=1$. If some $s_i=1$, a single vertex supplies the required vacuous monochromatic clique, so the Ramsey number is one. Otherwise put $N_i=R_k(s_1,\dots ,s_i-1,\dots ,s_k)$, which is finite by induction, and takeFix a vertex $v$ and partition its other $n-1$ vertices according to the colour of their edge to $v$. Some colour-$i$ class has at least $N_i$ vertices: if every class had at most $N_i-1$, their total would be at most ${\sum }_i{N}_i-k=n-2$. In that class the inductive property either gives a colour-$j$ clique of size $s_j$ with $j\ne i$, or a colour-$i$ clique of size $s_i-1$. In the latter case add $v$. ThusIn particular the requested two-colour diagonal number is $R(s)=R_2(s,s)$, so it exists for every $s\ge 2$.

Now colour each positive integer by its partition class, say there are $k$ classes, and take $m=R_k(3,\dots ,3)$. Colour the edge $ij$, $1\le i<j\le m$, by the class of $j-i$. There is a monochromatic triangle $a<b<c$. Its three differences $x=b-a$, $y=c-b$, $z=c-a$ are positive integers in one class, andThis is the finite-Ramsey proof of the partition conclusion. The statement does not require $x$ and $y$ to be distinct.