An improved construction for the triangle removal lemma

Abstract

We construct $n$-vertex graphs $G$ where $\epsilon n^2$ edges must be deleted to become triangle-free, which contain less than ${\epsilon }^{(C_{\text{new}}-o(1)){\log }_{2}1/\epsilon }{n}^3$ triangles for $C_{\text{new}}=\frac{1}{4{\log }_2(4/3)}\approx 1.6601$. Previously, a bound of the same shape was known, but with $C_{\text{new}}$ replaced by $C_{\text{old}}:=C_{\text{new}}/2$. Our construction uses ideas from additive combinatorics, drawing especially from the corners problem, but does not yield new bounds for those problems.

arXiv comment13 pages, comments welcome!