Solution

R (t)

is the least positive integer

n

such that every red-blue colouring of the edges of

K_{n}

contains a monochromatic

K_{t}

More generally, let

R (s, t)

be the least

n

forcing either a red

K_{s}

or a blue

K_{t}

. We have

R (1, t) = R (s, 1) = 1.

Assuming the two smaller numbers exist, colour

K_{R (s - 1, t) + R (s, t - 1)}

and choose a vertex

v

. At least

R (s - 1, t)

of its incident edges are red, or at least

R (s, t - 1)

are blue. In the first case, the corresponding neighbourhood contains a red

K_{s - 1}

, which extends with

v

to a red

K_{s}

, or a blue

K_{t}

. The second case is symmetric. Thus

R (s, t) \leq R (s - 1, t) + R (s, t - 1),

which proves existence by induction.

R (s, t) \leq (s - 1 s + t - 2) .

Consequently, for

t \geq 2

R (t) = R (t, t) \leq (t - 1 2 t - 2) \leq 2^{2 t - 2} < 2^{2 t} .

Solved by gpt-5.6-sol high.

 Ancestors (11)