Triangle counting lemma for three pairwise regular vertex sets

By [L1], fewer than $ϵ\mathrm{\mid }X\mathrm{\mid }$ vertices have fewer than $(a-ϵ)\mathrm{\mid }Y\mathrm{\mid }$ neighbours in $Y$, and fewer than $ϵ\mathrm{\mid }X\mathrm{\mid }$ have fewer than $(b-ϵ)\mathrm{\mid }Z\mathrm{\mid }$ neighbours in $Z$. Thus at least $(1-2ϵ)\mathrm{\mid }X\mathrm{\mid }$ vertices $x\in X$ satisfy both lower bounds.

For each such $x$, put $Y_x=N(x)\cap Y$ and $Z_x=N(x)\cap Z$. Since $a,b\ge 2ϵ$, step 1.1 gives $\mathrm{\mid }{Y}_x\mathrm{\mid }\ge ϵ\mathrm{\mid }Y\mathrm{\mid }$ and $\mathrm{\mid }{Z}_x\mathrm{\mid }\ge ϵ\mathrm{\mid }Z\mathrm{\mid }$.

By [L2], there are at least $(c-ϵ)\mathrm{\mid }{Y}_x\mathrm{\mid }\mathrm{\mid }{Z}_x\mathrm{\mid }$ edges between $Y_x$ and $Z_x$, and each produces a unique triangle $(x,y,z)$.

Since $a\le 1$ and $a\ge 2ϵ$, we have $ϵ\le 1\mathrm{/}2$, so $1-2ϵ\ge 0$. If $c<ϵ$ then $c-ϵ<0$ makes the claimed lower bound nonpositive, while the triangle count is nonnegative, so the inequality holds. If $c\ge ϵ$ then $c-ϵ\ge 0$, so substituting the bounds $\mathrm{\mid }{Y}_x\mathrm{\mid }\ge (a-ϵ)\mathrm{\mid }Y\mathrm{\mid }$ and $\mathrm{\mid }{Z}_x\mathrm{\mid }\ge (b-ϵ)\mathrm{\mid }Z\mathrm{\mid }$ of step 1.1 into $(c-ϵ)\mathrm{\mid }{Y}_x\mathrm{\mid }\mathrm{\mid }{Z}_x\mathrm{\mid }$ preserves the inequality of step 3.1; summing over the at least $(1-2ϵ)\mathrm{\mid }X\mathrm{\mid }$ good choices of $x$ gives exactly the claimed product bound.