Lecture 6 We are now ready to prove the triangle removal lemma. Theorem 1 (Triangle removal lemma)For every e>0 there erists 6>0 such that,for any graph G onn vertices with at most n3 triangles,it may be made triangle-free by removing at most en edges Proof Let XiU...UXM be an i-regular partition of the vertices of G.We remove an edge zy from Gif 1.(y)E Xi x Xi,where (Xi,X;)is not an 4-regular pair; 2.(c,)∈X×X,where d(Xi,X）<: 3.EeX,where X≤n. The nmber of edges removed by condition 1 is at most The number removed by condition 2 is clearly at most n2.Finally,the number removed by condition 3 is at most Mnn= in2.Overall,we have removed at most en2 edges. Now,suppose that some triangle remains in the graph,say ryz,where Xi,yE Xj and 2E X. Then the pairs (Xi,X),(Xi,X)and (X,Xi)are all 4-regular with density at least 5.Therefore since,n,we have,by the counting lemma that the number of triangles is at least (-)()3()2 Taking yields a contradiction. We now use this removal emma to prove Roth's theorem.We will actually prove the following stronger theorem. Theorem 2 Let >0.Then there erists no such that,for n>no,any subset A of [n2 with at least 6n2 elements must contain a triple of the form (,y),(+d,y),(,y+d)with d>0. Proof The set A+A={x+y:,y A}is contained in [2n)2.There must,therefore,be some z which is represented as x+y in at least (6m22_62n2 (2mP- 4 different ways.Pick such a z and let A'=An(z-A)and'=.Then A'l 26'n2 and if A'contains a triple of the form()(d (for d,then so doesA.Therefore,A will contain such a triple withd.We may therefore forget about the constraint thatdand simply try to find some non-trivial triple with d0. Consider the tripartite graph on vertex sets X,Y and Z,where=Y=[n]and Z=[2n].X will correspond to vertical lines through A,Y to horizontal lines and Z to diagonal lines with constant values of x+y.We form a graph G by joining rX to yEY if and only if (,y)E A.We also join x and z if(,z-x)∈A and y and if(z-,∈A. 1 Lecture 6 We are now ready to prove the triangle removal lemma. Theorem 1 (Triangle removal lemma) For every  > 0 there exists δ > 0 such that, for any graph G on n vertices with at most δn3 triangles, it may be made triangle-free by removing at most n2 edges. Proof Let X1 ∪ · · · ∪ XM be an  4 -regular partition of the vertices of G. We remove an edge xy from G if 1. (x, y) ∈ Xi × Xj , where (Xi , Xj ) is not an  4 -regular pair; 2. (x, y) ∈ Xi × Xj , where d(Xi , Xj ) <  2 ; 3. x ∈ Xi , where |Xi | ≤  4M n. The number of edges removed by condition 1 is at most P (i,j)∈I |Xi ||Xj | ≤  4 n 2 . The number removed by condition 2 is clearly at most  2 n 2 . Finally, the number removed by condition 3 is at most Mn  4M n =  4 n 2 . Overall, we have removed at most n2 edges. Now, suppose that some triangle remains in the graph, say xyz, where x ∈ Xi , y ∈ Xj and z ∈ Xk. Then the pairs (Xi , Xj ), (Xj , Xk) and (Xk, Xi) are all  4 -regular with density at least  2 . Therefore, since |Xi |, |Xj |, |Xk| ≥  4M n, we have, by the counting lemma that the number of triangles is at least  1 −  2    4 3   4M 3 n 3 . Taking δ =  6 2 20M3 yields a contradiction. ✷ We now use this removal lemma to prove Roth’s theorem. We will actually prove the following stronger theorem. Theorem 2 Let δ > 0. Then there exists n0 such that, for n ≥ n0, any subset A of [n] 2 with at least δn2 elements must contain a triple of the form (x, y),(x + d, y),(x, y + d) with d > 0. Proof The set A + A = {x + y : x, y ∈ A} is contained in [2n] 2 . There must, therefore, be some z which is represented as x + y in at least (δn2 ) 2 (2n) 2 = δ 2n 2 4 different ways. Pick such a z and let A0 = A∩(z −A) and δ 0 = δ 2 4 . Then |A0 | ≥ δ 0n 2 and if A0 contains a triple of the form (x, y),(x + d, y),(x, y + d) for d < 0, then so does z − A. Therefore, A will contain such a triple with d > 0. We may therefore forget about the constraint that d > 0 and simply try to find some non-trivial triple with d 6= 0. Consider the tripartite graph on vertex sets X, Y and Z, where X = Y = [n] and Z = [2n]. X will correspond to vertical lines through A, Y to horizontal lines and Z to diagonal lines with constant values of x + y. We form a graph G by joining x ∈ X to y ∈ Y if and only if (x, y) ∈ A. We also join x and z if (x, z − x) ∈ A and y and z if (z − y, y) ∈ A. 1