Help understanding Roth's theorem of arithmetic progression.

Question

I'm getting stuck trying to understand the following proof. Please have a look.

The proof refers to the "Triangle Removal Lemma".

My questions are as follows:

1. Shouldn't the "$\geq$" sign underlined in red be "$=$" instead?

2. In the second to last paragraph, the proof says "From what we showed above", and I assume the flow of argument here is that the second case in the Triangle Removal Lemma must happen because the existence of the triangles in $H$ makes the first case impossible. But how can we conclude that unless we can show there are strictly greater than $\frac{\epsilon}{36}v(H)^2$ triangles in $H$?

3. Just to be sure, is the number $\delta {|V(H)| \choose 3}$ there because we have $\delta {|V(H)| \choose 3} < \delta v(H)^3$?

4. I'm completely clueless about the part that follows.

Answer 1

The answers to questions 1-3 could be summarized as "the author is being slightly careless here, but we can fix that without affecting the argument".

Shouldn't the "$\ge$" sign underlined in red be "$=$" instead?

It can be $=$ (since we're replacing $n^2$ by $\frac{v(H)^2}{36}$, and $v(H) = 6n$ exactly) but $\ge$ is also true. Since we're going to get an inequality at the end anyway, it doesn't matter what we write here, though some people prefer to write $=$ whenever possible to indicate the places where we're potentially "giving something away".

In the second to last paragraph, the proof says "From what we showed above", and I assume the flow of argument here is that the second case in the Triangle Removal Lemma must happen because the existence of the triangles in $H$ makes the first case impossible. But how can we conclude that unless we can show there are strictly greater than $\frac{\epsilon}{36} v(H)^2$ triangles in $H$?

Minor comment: we're not showing that the number of triangles in $H$ is $\frac{\epsilon}{36} v(H)^2$, but that there are this many pairwise edge-disjoint triangles, and as a result, at least $\frac{\epsilon}{36} v(H)^2$ edges need to be deleted to make $H$ triangle-free.

That aside, you're technically right. The author of the proof isn't being careful here, and applying the triangle removal lemma with $\gamma = \frac{\epsilon}{36}$ won't help: the first case of the lemma might hold here. However, it is not hard to fix this mistake: just take $\gamma = \frac{\epsilon}{37}$ (for example) instead. Since the dependence of $\delta$ on $\gamma$ in the lemma is pretty bad anyway - and hidden from us in the statement - we don't care what this constant is.

Just to be sure, is the number $\delta \binom{v(H)}{3}$ there because we have $\delta \binom{v(H)}{3} < \delta v(H)^3$?

That's probably another minor mistake; from the triangle removal lemma, we can guarantee $\delta v(H)^3$ triangles, which is better than $\delta \binom{v(H)}{3}$. Also, the value $\delta v(H)^3$ is what gets used later in the proof.

Since the lemma doesn't tell us the explicit dependence of $\delta$ on $\gamma$, a version of the lemma with $\delta \binom{v(G)}{3}$ instead of $\delta v(G)^3$ in case (B) would be equivalent (they're off by about a factor of $6$); people sometimes use both. The version with the binomial looks nicer to some people because then $\delta$ is the fraction of possible triangles which are present. The version with $\delta v(G)^3$ looks nicer to some people because it's a simpler function of $v(G)$.

I'm completely clueless about the part that follows.

A rough sketch of the argument is this. Triangles in $H$ produce 3-APs in $S$, although a few of the triangles only produce trivial 3-APs (the 3-AP $x,x,x$ for $x \in S$ is a trivial 3-AP, and doesn't count for Roth's theorem). With the triangle removal lemma, we show that there are many triangles in $H$: more than the number which would produce trivial 3-APs in $S$. Therefore there must be triangle which produces a nontrivial 3-AP in $S$, proving the theorem.

The argument in the paragraph where you're lost does two things.

1. It lays out how to use a triangle in $H$ to get a 3-AP in $S$: a triangle formed by vertices $\{a_i, b_j, c_k\}$ corresponds to the 3-AP $j-i, \frac{k-i}{2}, k-j \in S$ (with common difference $\frac{i+k}{2}-j$).
2. It spells out the exact values of "a few" and "many" that I left out of the rough sketch. Essentially, the number of triangles that give trivial 3-APs is $O(n^2)$, with a constant that we get out of the proof, while the number of triangles that are guaranteed to exist in $H$ is $\Omega(n^3)$, also with a constant that we get out of the proof. For sufficiently large $n$, the second number exceeds the first.