Let $R=R(C_5)$ be the fixed <graph Ramsey number> of the five-cycle. Partition $\lfloor n/R\rfloor R$ vertices into $\lfloor n/R\rfloor$ disjoint blocks of size $R$. For any one block, the probability that $G(n,1/2)$ induces a complete graph is
$$
q=2^{-\binom R2}>0.
$$
These events are independent for the disjoint blocks. Therefore the probability that none of them induces $K_R$ is
$$
(1-q)^{\lfloor n/R\rfloor}\longrightarrow0.
$$
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
$$
\boxed{\lim_{n\to\infty}\mathbb P(G\to C_5)=1.}
$$

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/iii/paper-132/4/c/solution