Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 132 / 2 / b

Solution

We use the Erdős-Rado selection argument. Put

m = R^{(2)} (k - 1) + 1.

Starting with a sufficiently large reservoir, choose vertices

v_{1}, \dots, v_{m}

in order. After choosing

v_{j}

, successively halve the remaining reservoir for each

i < j

so that the colour of

{v_{i}, v_{j}, x}

is constant as

x

ranges over the final reservoir. The total number of halvings is at most

(2 m)

, so

2^{(2 m)} + m

initial vertices suffice.

Colour the pair

ij

, for

i < j < m

, by the stabilized colour of

{v_{i}, v_{j}, v_{ℓ}}

for

ℓ > j

. Among

v_{1}, \dots, v_{m - 1}

R^{(2)} (k - 1)

k - 1

vertices. Adjoining

v_{m}

gives a monochromatic

k

-set for the original triple colouring. Hence

R^{(3)} (k) \leq 2^{(2 R ^{(2)} ( k - 1 ) + 1)} + R^{(2)} (k - 1) + 1.

R^{(2)} (k - 1) < 2^{2 k}

, so the right-hand side is at most

2^{2^{C k}}

for an absolute

C > 0

There are no discussions about this article yet.

There are currently no matching articles.