Given a program ? such that for any n >= 0 and every computation S1 = (1, ?), S2

Question

Explanation / Answer

First we prove the theorem for the 2-colour case, by induction on r + s. It is clear from the definition that for all n, R(n, 1) = R(1, n) = 1. This starts the induction. We prove that R(r, s) exists by finding an explicit bound for it. By the inductive hypothesis R(r - 1, s) and R(r, s - 1) exist. Claim: R(r, s) = R(r - 1, s) + R(r, s - 1): Consider a complete graph on R(r - 1, s) + R(r, s - 1) vertices. Pick a vertex v from the graph, and partition the remaining vertices into two sets M and N, such that for every vertex w, w is in M if (v, w) is blue, and w is in N if (v, w) is red. Because the graph has R(r - 1, s) + R(r, s - 1) = |M| + |N| + 1 vertices, it follows that either |M| = R(r - 1, s) or |N| = R(r, s - 1). In the former case, if M has a red Ks then so does the original graph and we are finished. Otherwise M has a blue Kr-1 and so has blue Kr by definition of M. The latter case is analogous. Thus the claim is true and we have completed the proof for 2 colours. We now prove the result for the general case of c colours. The proof is again by induction, this time on the number of colours c. We have the result for c = 1 (trivially) and for c = 2 (above). Now let c > 2. Claim: R(n1, ..., nc) = R(n1, ..., nc-2, R(nc-1, nc)). Note, that the right hand side only contains Ramsey numbers for c - 1 colours and 2 colours, and therefore exists and is a finite number t, by the inductive hypothesis. Thus, proving the claim will prove the theorem. Proof of claim: Consider a graph on t vertices and colour its edges with c colours. Now 'go colour-blind' and pretend that c - 1 and c are the same colour. Thus the graph is now (c - 1)-coloured. By the inductive hypothesis, it contains either a Kni monochromatically coloured with colour i for some 1 = i = (c - 2) or a KR(nc-1,nc)-coloured in the 'blurred colour'. In the former case we are finished. In the latter case, we recover our sight again and see from the definition of R(nc-1, nc) we must have either a (c - 1)-monochrome Knc-1 or a c-monochrome Knc. In either case the proof is complete. – In the 2-color case, if R(r - 1, s) and R(r, s - 1) are both even, the induction inequality can be strengthened to R(r, s) = R(r - 1, s) + R(r, s - 1) - 1.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.