Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2008/ii/paper-4/17f/solution
Past exam of the mathematics course of the University of Cambridge 2008 ii Paper 4 17F Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-14
Define the multicolour graph Ramsey number as the least such that every colouring of the edges of the complete graph with colours contains, for some , a complete subgraph on vertices all of whose edges have colour .
Prove finiteness by induction on , temporarily allowing . If some , a single vertex supplies the required vacuous monochromatic clique, so the Ramsey number is one. Otherwise put , which is finite by induction, and takeFix a vertex and partition its other vertices according to the colour of their edge to . Some colour- class has at least vertices: if every class had at most , their total would be at most . In that class the inductive property either gives a colour- clique of size with , or a colour- clique of size . In the latter case add . ThusIn particular the requested two-colour diagonal number is , so it exists for every .
Now colour each positive integer by its partition class, say there are classes, and take . Colour the edge , , by the class of . There is a monochromatic triangle . Its three differences , , are positive integers in one class, andThis is the finite-Ramsey proof of the partition conclusion. The statement does not require and to be distinct.
New to topics? Read the docs here!