There are two different statements that are supposed to be equivalent reformulations of the Triangle Removal Lemma from combinatorics. One says that given any $f(n)\in o(n^3)$, there is some $g(n)\in o(n^2)$ such that any $n$-vertex graph with at most $f(n)$ triangles can be made triangle-free by removing at most $g(n)$ edges. Another states that for every $\epsilon > 0$, there is some $\delta(\epsilon)>0$ such that any graph on $n$ vertices with at most $\delta n^3$ triangles can be made triangle-free by eliminating at most $\epsilon n^2$ edges.
Now in this question, the second of these was shown to imply the first. As inept as this sounds, I was simply unable to see why the first implies the second. More generally, I have a major lack of intuition as to why these might be equivalent statements: the first says that for any $f(n)$ (which controls the triangles) there is some $g(n)$ (controlling the edges) whereas the second version says that for every $\epsilon$ (controlling the edges) there is some $\delta$ (controlling the triangles), thus my intuition is crying out to me saying that the quantifiers have been reversed so these statements can't possibly encode the same information.
Could someone explain why first of these statements implies the second and, if possible, why my (intuitive/soft) concern about quantifier reversal isn't correct?
![1]](https://latex.artofproblemsolving.com/3/7/e/37e5874ca1da264a885e6af8eb5414e482304926.png)
Best Answer
Why the quantifiers cannot be any other way
First of all, let me address what's going on with quantifier reversal.
We may check that out of 8 possibilities for the quantifiers (we may put $\forall$ or $\exists$ on each variable, and we can put them in either order):
I will not check all $16$ cases here, they're mostly boring, but here is why neither lemma can be stated in the form of the other.
If we state the first lemma as $\forall g(n) \in o(n^2)$ $\exists f(n) \in o(n^3)$, we state a much weaker result. The proof is: for any $g(n) \in o(n^2)$, pick $f(n) = g(n)$. It is true that in an $n$-vertex graph with at most $g(n)$ triangles, we can delete at most $g(n)$ edges and get a triangle-free graph: delete an arbitrary edge from each triangle.
If we state the second lemma as $\forall \delta>0$ $\exists \epsilon>0$, we also state a much weaker result. The proof is: for any $\delta>0$, pick $\epsilon = \frac12$. It is true that in an $n$-vertex graph with any number of triangles you like, we can delete at most $\frac12n^2$ edges and get a triangle-free graph: delete all the edges.
Why these quantifiers actually make sense together
Okay, but why is this happening?
The reason is that there are extra quantifiers hidden inside the $o(n^2)$ and $o(n^3)$:
These hidden quantifiers inside the little-o statements of the first lemma are actually the quantifiers corresponding to the visible quantifiers of the second lemma.
Why the first lemma implies the second
This is a bit long, and essentially the reason for that is we need triangle removal to give us a "nice" dependency between triangles and edges. The $o(n^3)$ and $o(n^2)$ only say what is going on as $n \to \infty$, and we'll need to work to fill in the gaps.
Let $\epsilon>0$. Define $f(n)$ as follows: for each $n$, $f(n)$ is the largest value $t \in \{0,\dots,\binom n3\}$ such that the statement "If an $n$-vertex graph has at most $t$ triangles, it can be made triangle-free by removing at most $\frac14\epsilon n^2$ edges" holds.
If $f(n)$ were $o(n^3)$, then the first lemma would actually give us much more: a function $g(n)$ which is $o(n^2)$, and can replace $\frac14\epsilon n^2$ in the statement above. Eventually, for large enough $n$, $g(n)$ is less than $\frac14\epsilon n^2 - 1$. At this point, if a graph has at most $f(n)+1$ triangles, it can also be made triangle-free by removing at most $\frac14\epsilon n^2$ edges: remove a single edge from some triangle (leaving at most $f(n)$ triangles), then remove $g(n)$ more edges to destroy all remaining triangles. This contradicts our choice of $f(n)$: for this $n$, it could have been $1$ higher!
Therefore $f(n)$ is not $o(n^3)$. In other words, there is a $\delta>0$ such that for infinitely many values of $n$ we have $f(n) > \delta n^3$.
But we need the proof to work for arbitrary $n$, not just for these special values. So take any $n$ and take any $n$-vertex graph with at most $\delta n^3$ triangles, then choose some $m > 10n$ such that $f(m) > \delta m^3$. Write $m = qn + r$ with $0 \le r < n$, noting that our choice of $m$ means $q \ge 10$.
From $G$, construct an $m$-vertex graph $H$ by replacing every vertex of $G$ by $q$ vertices and every edge by a copy of $K_{q,q}$, then adding $r$ isolated vertices. Each triangle in $G$ corresponds to a complete tripartite graph $T \cong K_{q,q,q}$ in $H$, with $q^3$ triangles, and there are no other triangles in $H$, thus $H$ has at most $\delta n^3 q^3 \le \delta m^3$ triangles. Therefore it is possible to remove $\frac14 \epsilon m^2$ edges from $H$ to make it triangle-free.
Now we try to imitate that edge deletion in $G$, with some loss of efficiency. Delete from $G$ every edge such that the corresponding copy of $K_{q,q}$ in $H$ lost at least $\frac13 q^2$ of its edges. This cannot delete more than $\epsilon n^2$ edges, because then we'd be deleting $(\frac13q^2)(\epsilon n^2) > \frac14 \epsilon m^2$ edges from $H$. (Here we use $m < qn+n$ and $q \ge 10$.) Now we must check that this destroys every triangle in $G$.
Each triangle in $G$, again, corresponds to a complete tripartite graph $T \cong K_{q,q,q}$ in $H$, with $q^3$ triangles, and each edge of $T$ is contained in only $q$ of those triangles, so at least $q^2$ of the $3q^2$ edges in $T$ are deleted when $H$ is made triangle-free. By averaging, one of the three copies of $K_{q,q}$ in $T$ loses at least $\frac13 q^2$ of its edges. Therefore one of the edges of this triangle in $G$ will be deleted by the rule in the previous paragraph.
So we've successfully removed all triangles from $G$ with only $\epsilon n^2$ deleted edges.