Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 132 / 4 / c

Solution

Let

R = R (C_{5})

be the fixed graph Ramsey number of the five-cycle. Partition

⌊ n / R ⌋ R

⌊ n / R ⌋

disjoint blocks of size

R

. For any one block, the probability that

G (n, 1/2)

q = 2^{- (2 R)} > 0.

These events are independent for the disjoint blocks. Therefore the probability that none of them induces

K_{R}

(1 - q)^{⌊ n / R ⌋} ⟶ 0.

With probability tending to one,

G

contains a copy of

K_{R}

. Every red-blue colouring of this copy contains a monochromatic

C_{5}

by the definition of

R (C_{5})

. Hence

n \to \infty lim P (G \to C_{5}) = 1.

There are no discussions about this article yet.

There are currently no matching articles.