We study quantitative relationships between the triangle removal lemma and several of its variants. One such variant, which we call the triangle-free lemma, states that for each $epsilon>0$ there exists $M$ such that every triangle-free graph $G$ has an $epsilon$-approximate homomorphism to a triangle-free graph $F$ on at most $M$ vertices (here an $epsilon$-approximate homomorphism is a map $V(G) to V(F)$ where all but at most $epsilon |V(G)|^2$ edges of $G$ are mapped to edges of $F$). One consequence of our results is that the least possible $M$ in the triangle-free lemma grows faster than exponential in any polynomial in $epsilon^{-1}$. We also prove more general results for arbitrary graphs, as well as arithmetic analogues over finite fields, where the bounds are close to optimal.
Download