Generalizations of the Triangle Removal Lemma to smaller exponents

Question

The Triangle Removal Lemma states:

For all $\epsilon > 0$, there is a $\delta > 0$ such that any graph on $n$ vertices with at most $\delta n^3$ triangles may be made triangle-free by removing at most $\epsilon n^2$ edges.

(This is a special case of the more general Graph Removal Lemma -- see here for a survey.)

There has been a lot of interesting work optimizing the tradeoff between $\epsilon$ and $\delta$ in this lemma. I am wondering if the relationship between the exponents has been studied. For example, is it known if any graph on $\delta n^{2.9}$ triangles may be made triangle-free by removing at most $\epsilon n^{1.9}$ edges?

Answer 1

Okay, sorry, I figured out the answer to my own question. I'll post it here for posterity:

You can create a graph on $n^2 / 2^{O(\sqrt{\log n})}$ edges, in which every edge is part of a unique triangle, like this: construct a progression-free set $A$ of integers in $[n]$ of size $n/2^{O(\sqrt{\log n})}$ (there are known constructions for this; see Behrend or Elkin), then build a three-layered graph where the node set of each layer is $[3n]$ and the edges are of the form $(x \text{ in layer } i) \to (x + a \text{ in layer } i+1)$ for each $a \in A$ and $x+a \in [3n]$. Finally, for each node $x$ in the first layer, add an edge to $x+2a$ in the third layer for each $a \in A$ (if $x + 2a \in [3n]$).

It's not too hard to see that every edge is contained in a unique triangle, and thus, one would need to delete $\Theta(n^2 / 2^{O(\sqrt{\log n})})$ edges to make the graph triangle-free. It follows that only a trivial version of the Triangle Removal Lemma is available for smaller exponents: For graphs with at most $n^{3 - \alpha}$ triangles ($0 < \alpha \le 1$), you still might need to remove $\Theta(n^{2 - o(1)})$ edges to make them triangle-free.