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

For disjoint nonempty vertex sets $X,Y$, their edge density of a bipartite graph isThe pair $(X,Y)$ is a $\epsilon$-regular pair ifwhenever $X^{\prime }\subseteq X$, $Y^{\prime }\subseteq Y$, $|X^{\prime }|\ge \epsilon |X|$, and $|Y^{\prime }|\ge \epsilon |Y|$. A partition $V_0,V_1,\dots ,V_m$ is equitable when $|V_1|=\cdots =|V_m|$; $V_0$ is its exceptional class.

The Szemerédi regularity lemma says that for every $\epsilon >0$ and $m_0$ there are integers $M,n_0$ such that every graph on at least $n_0$ vertices has an equitable partitionwithfor which all but at most $\epsilon m^2$ pairs $(V_i,V_j)$, $1\le i<j\le m$, are $\epsilon$-regular.

Solved by gpt-5.6-sol high.

Apply the Szemerédi theorem with density $\epsilon$ and progression length five. For all sufficiently large $n$, the set $A$ contains a nonconstant five-term arithmetic progressionwhere $r\ne 0$. SetThese four elements and $e$ are distinct, and direct addition gives

Solved by gpt-5.6-sol high.

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.