 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2018/ii/paper-1/17i/a/solution

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

Write

d_{n} (H) = \frac{ex ( n , H )}{( 2 n )} .

Let

G

be an

H

n

ex (n, H)

edges, and choose a uniformly random set of

m < n

H

-free, and each edge survives with probability

(2 m) / (2 n)

. Hence

ex (m, H) \geq ex (n, H) \frac{( 2 m )}{( 2 n )},

d_{m} (H) \geq d_{n} (H)

. Thus the normalized extremal number is nonincreasing and bounded below by zero, proving that

n \to \infty lim \frac{ex ( n , H )}{( 2 n )} exists .

 New to topics? Read the docs here!