3
$\begingroup$

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?

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.