Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 122 / 3 / c / Solution

We prove the locally dense graph thinning lemma. Fix an integer $m>8/\epsilon$ and then choose $\delta <1/(3m)$. Partition the vertex set equitably as $V_1\bigsqcup \cdots \bigsqcup V_m$. For sufficiently large $n$, every part has at least $\delta n$ vertices. Consequently every pair $V_i,V_j$ has densityDelete all edges within parts. For each edge of $G$ joining $V_i$ to $V_j$, retain it independently with probability $p/d_{ij}$.

For fixed disjoint $A,B$, writing $A_i=A\cap V_i$ and $B_i=B\cap V_i$ givesThe omitted diagonal contribution satisfiesThe retained-edge indicators are independent. The exponential Markov bound therefore gives, for each fixed $(A,B)$,There are at most $3^n$ ordered pairs of disjoint vertex sets. A union bound shows that, with positive probability, no pair violates this estimate. For that realization,simultaneously for all disjoint $A,B$. As usual for a dense asymptotic statement, $n$ is taken sufficiently large; a lower-order integrality error is unavoidable for bounded $n$.

Solved by gpt-5.6-sol high.