= Solution
The <triangle embedding lemma for regular pairs> states that if $0<\varepsilon<1/2$, the three pairs among disjoint nonempty sets $A,B,C$ are $\varepsilon$-uniform, and all three densities are at least $2\varepsilon$, then the graph contains a triangle with one vertex in each set.
In an $\varepsilon$-uniform pair $(A,B)$ of density $d$, fewer than $\varepsilon|A|$ vertices of $A$ have fewer than $(d-\varepsilon)|B|$ neighbours in $B$; otherwise those vertices and $B$ would violate uniformity. Apply this observation to $(A,B)$ and $(A,C)$. Since $2\varepsilon<1$, choose $a\in A$ that is typical for both pairs. Then
$$
B'=N(a)\cap B,qquad C'=N(a)\cap C
$$
satisfy $|B'|\geq\varepsilon|B|$ and $|C'|\geq\varepsilon|C|$. Uniformity of $(B,C)$ gives
$$
d(B',C')\geq d(B,C)-\varepsilon\geq\varepsilon>0.
$$
Thus some $bc$ joins $B'$ to $C'$, and $abc$ is the required triangle.
Back to article page
