Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 122 / 4 / b / Solution

The triangle embedding lemma for regular pairs states that if $0<\epsilon <1/2$, the three pairs among disjoint nonempty sets $A,B,C$ are $\epsilon$-uniform, and all three densities are at least $2\epsilon$, then the graph contains a triangle with one vertex in each set.

In an $\epsilon$-uniform pair $(A,B)$ of density $d$, fewer than $\epsilon |A|$ vertices of $A$ have fewer than $(d-\epsilon )|B|$ neighbours in $B$; otherwise those vertices and $B$ would violate uniformity. Apply this observation to $(A,B)$ and $(A,C)$. Since $2\epsilon <1$, choose $a\in A$ that is typical for both pairs. Thensatisfy $|B^{\prime }|\ge \epsilon |B|$ and $|C^{\prime }|\ge \epsilon |C|$. Uniformity of $(B,C)$ givesThus some $bc$ joins $B^{\prime }$ to $C^{\prime }$, and $abc$ is the required triangle.