4.II.17F

Graph Theory
Part II, 2008

For s2s \geqslant 2, let R(s)R(s) be the least integer nn such that for every 2 -colouring of the edges of KnK_{n} there is a monochromatic KsK_{s}. Prove that R(s)R(s) exists.

For any k1k \geqslant 1 and s1,,sk2s_{1}, \ldots, s_{k} \geqslant 2, define the Ramsey number Rk(s1,,sk)R_{k}\left(s_{1}, \ldots, s_{k}\right), and prove that it exists.

Show that, whenever the positive integers are partitioned into finitely many classes, some class contains x,y,zx, y, z with x+y=zx+y=z.

[Hint: given a finite colouring of the positive integers, induce a colouring of the pairs of positive integers by giving the pair ij(i<j)i j(i<j) the colour of jij-i.]