Equivalence of statements of Triangle Removal Lemma

Solution 1:

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):

• The only interesting way to state the first lemma is $\forall f(n) \in o(n^3)$ $\exists g(n) \in o(n^2)$.
• The only interesting way to state the second lemma is $\forall \epsilon>0$ $\exists \delta>0$.

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)$:

1. We can unpack "$f(n) \in o(n^3)$" as "for every $\delta>0$, there is an $n_0$ such that if $n>n_0$, then $f(n) \le \delta n^3$. Since we assume we are given an $f(n) \in o(n^3)$, this definition lets us pick any $\delta>0$ we like and assume our graph has at most $\delta n^3$ triangles - just by taking $n$ large enough. This is a lot like proving $\exists \delta > 0$, which also lets us pick $\delta$.
2. We can unpack "$g(n) \in o(n^2)$" as "for every $\epsilon>0$, there is an $n_0$ such that if $n>n_0$, then $g(n) \le \epsilon n^2$. In order to construct $g(n)$, we must make sure that for all $\epsilon>0$, there is a large enough $n$ that we only delete at most $\epsilon n^2$ edges. From point 1, "large enough $n$" means "we can pick the $\delta>0$ we want".

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 number of triangles such that the statement "If an $n$-vertex graph has $f(n)$ triangles, it can be made triangle-free by removing at most $\frac13\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 $\frac13\epsilon n^2$ in the statement above. Eventually, for large enough $n$, $g(n)$ is less than $\frac13\epsilon n^2 - 1$. At this point, if a graph has $f(n)+1$ triangles, it can also be made triangle-free by removing at most $\frac13\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$.

To finish the proof, pick any $n$, and take any $n$-vertex graph $G$ with at most $\delta n^3$ triangles. We know that there is an $m>n$ such that $f(m) > \delta m^3$, and therefore any $m$-vertex graph with at most $\delta m^3$ triangles can be made triangle-free by removing at most $\frac13\epsilon m^2$ edges.

Construct an $m$-vertex graph $H$ from $G$ by taking a blow-up: replace every vertex of $G$ by $m/n$ vertices (rounded up or down, but I'll ignore this; we might need another small factor in the $\epsilon$ to account for that) and every edge by a complete bipartite graph between its endpoints. We know that we may remove at most $\frac13\epsilon m^2$ edges from $H$ to make it triangle-free.

Any triangle in $G$ corresponds to a complete tripartite subgraph $T$ in $H$. From each of the $(m/n)^3$ triangles in $T$, one edge is deleted when we make $H$ triangle-free, and every edge of $T$ is in the same number of those triangles, so at least $1/3$ of the edges in $T$ are deleted. Therefore at least one of the complete bipartite graphs of $T$ must lose $\frac13(m/n)^2$ of its edges.

Delete the following edges from $G$: all the edges whose corresponding complete bipartite graph lost at least $\frac13(m/n)^2$ of its edges. We know that every triangle of $G$ must lose at least one edge. Also, there cannot be more than $\epsilon n^2$ such edges in $G$, or they'd correspond to more than $\frac13 \epsilon m^2$ edges in $H$.

So we've successfully removed all triangles from $G$ with only $\epsilon n^2$ deleted edges.