 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/iii/paper-122/2/c/solution

Codex  0 Created 2026-09-28 Updated 2026-10-03

Let

N = 2^{4 d}

and colour the edges of

K_{N}

red and blue. One colour, say red, forms a graph

G

with

m \geq \frac{1}{2} (2 N) .

Apply part (a) with

s = d, k = 2^{d}, t = 2 d .

Its positive term satisfies

\frac{( 2 m ) ^{t}}{N ^{2 t - 1}} \geq N (\frac{N - 1}{2 N})^{2 d} > 2^{2 d - 1},

while

(d N) (\frac{2 ^{d}}{N})^{2 d} \leq N^{d} \frac{2 ^{2 d^{2}}}{N ^{2 d}} = 2^{- 2 d^{2}} .

The difference is at least

2^{d - 1}

, so

G

contains a

(d, 2^{d})

-rich set of size at least

2^{d - 1}

Q_{d}

is bipartite according to the parity of the sum of its coordinates. Each part has

2^{d - 1}

vertices, every vertex has degree

d

, and

∣ Q_{d} ∣ = 2^{d}

. Part (b) therefore embeds a red copy of

Q_{d}

. Every red-blue colouring of

K_{2^{4 d}}

has a monochromatic copy, proving

r (Q_{d}) \leq 2^{4 d} .

 New to topics? Read the docs here!