Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 122 / 2

Letwhere the positive constant $c$ will be chosen small, and sample the binomial random graph $G(N,p)$. If $X$ counts its copies of $C_4$, thenIf $Y$ counts its independent $k$-sets, thenHere $pk\sim c^{-3/4}\log k$. Choosing $c$ sufficiently small makes the negative exponential term dominate $k\log (eN/k)$, so $\mathbb{E}Y=o(1)$. By Markov inequality, with positive probability $X<N/2$ and $Y=0$.

Starting from such a graph, delete one vertex from each remaining $C_4$. This random alteration method removes fewer than $N/2$ vertices, destroys every $C_4$, and cannot create an independent set of order $k$. The resulting graph has at least $N/2$ vertices, so its edges and nonedges give a red-blue colouring with neither a red $C_4$ nor a blue $K_k$. Consequently

Solved by gpt-5.6-sol high.

The Lopsided Lovász local lemma states that, for bad events $E_i$ with a lopsidependency graph, numbers $x_i\in [0,1)$ satisfyingimply $\mathbb{P}({\bigcap }_i{E}_i^c)>0$.

Fix any $0<\eta <1/6$, put $N=\lfloor k^{4/3+\eta }\rfloor$, and sample $G(N,p)$ withwhere $a>0$ is a sufficiently small absolute constant. Let $A_Q$ be the event that a specified copy $Q$ of $C_4$ is present, and let $B_S$ be the event that a specified $k$-set $S$ is independent. ThenFor product measures, the standard monotone-event lopsidependency graph joins an increasing event $A_Q$ to a decreasing event $B_S$ only when they use a common edge. Events of the same monotonicity need no lopsidependency edge. Thus each $A_Q$ has at most $4\left(\genfrac{}{}{0ex}{}{N-2}{k-2}\right)$ neighbours of type $B$, and each $B_S$ has at most $C{k}^2{N}^2$ neighbours of type $A$.

Set $x_A=2p^4$ and $x_B=2q$. Sincewe haveOn the other side,whereas $-\log q\ge (a/3)k^2{N}^{-2/3}$. Choosing $a$ small makes both local-lemma inequalities hold. There is therefore a graph on $N$ vertices containing no $C_4$ and no independent $k$-set. Taking, for example, $\eta =1/12$ proves

Solved by gpt-5.6-sol high.

We use the following standard off-diagonal Ramsey result from the course: if $F$ is a forest on $h-1$ vertices and $K_1\vee F$ is obtained by adjoining a universal vertex, then, for $k$ sufficiently large in terms of $h$,Its proof combines the $r(K_3,K_k)=O(k^2/\log k)$ bound with an iterative neighbourhood embedding of the forest.

The graph $H_{\ell }$ in the question is exactly $K_1\vee P_{\ell -1}$, and a path is a tree, hence a forest. Substitution of $h=\ell$ givesas required.

Solved by gpt-5.6-sol high.