Graph embedding lemma for regular pairs

For every finite graph $H$ and density $\delta >0$, sufficiently large vertex classes joined according to $H$ by regular pairs of density at least $\delta$ contain a copy of $H$. The regularity parameter must be sufficiently small in terms of $H$ and $\delta$.

For any fixed odd length $\ell \ge 3$, positive triangle in a graph density forces positive density of $\ell$-cycles. A Szemerédi regularity lemma partition retains a triangle in a graph of regular dense pairs after the sparse and exceptional pairs are removed. Count embeddings of a proper three-colouring of $C_{\ell }$ into those three clusters. The constants depend on $\beta$ and $\ell$, not on graph order.

If the three pairs among vertex sets $A,B,C$ are $\epsilon$-regular and each has density at least $2\epsilon$, where $0<\epsilon <1/2$, then the graph contains a triangle with one vertex in each set.