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

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.