Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/ii/paper-2/17g/c/solution

Let be a blue triangle and a vertex-disjoint yellow triangle. If some has two yellow neighbours in , those three vertices form a yellow triangle meeting . Otherwise every has at least two blue neighbours in , giving at least six blue cross-edges. Some then has two blue neighbours in , and these form a blue triangle meeting . This proves the overlap assertion.
The triangle-packing Ramsey number is
For completeness, its induction starts from the stated result. At each step, remove two disjoint monochromatic triangles supplied on ten currently unused vertices. If their colour disagrees with the packing already constructed, apply the overlap assertion to an oppositely coloured pair; replacing that pair by the overlapping pair is the augmenting move that shifts the boundary between the two packings. Repeating the move either adds a triangle to the existing colour or converts all pairs needed for the opposite-colour packing. Thus contains pairwise vertex-disjoint monochromatic triangles of one colour.
The bound is sharp. For , split the vertices into with
Colour edges inside and between and yellow; colour all edges from to and all edges within each blue. Every yellow triangle lies wholly in , so there are at most disjoint yellow triangles. Every blue triangle uses at least two vertices of , and such triangles would require a blue perfect matching on those vertices, impossible because the isolated one-vertex blue component and the odd component have no such matching. Hence there is no -triangle packing of either colour for any .

New to topics? Read the docs here!