= Regular triangle counting lemma
{title2=$\#K_3\geq(1-2\varepsilon)(d-\varepsilon)^3L^3$}
If three disjoint <vertex> classes have size $L$, and their three pairs are $\varepsilon$-<regular pairs of vertex sets> of <edge density of a bipartite graph> at least $d$, where $0<\varepsilon\leq d/2$ and $\varepsilon<1/2$, they contain at least the displayed number of transversal <triangles in a graph>. All but $2\varepsilon L$ <vertices> in the first class have at least $(d-\varepsilon)L$ neighbours in both other classes. Regularity between those two neighbour sets supplies the third <edge>. This strengthens a mere <triangle embedding lemma for regular pairs> to a cubic lower count.
Back to article page
