In this and the next lecture,we will prove a beautiful consequence of the regularity lemma,the triangle removal lemma.and show how one may deduce Roth's theorem from it.The triangle removal lemma says that if a graph contains very few triangles,then one may remove all such triangles by removing very few edges.Though this lemma souds simple,its proof is surprisingly subtle.We begin with what is known as a counting lemma. Lemma 2 Let G be a graph and let X,Y,Z be subsets of the verter set V(G).Suppose that (X,Y) (Y,Z)and (Z,X)are e-regular and that d(X,Y)=a,d(Y,Z)=B and d(z,X)=7.Then,provided a,B,y>2e,the num0 er of triangles ryz uith x∈X,I∈Y and z∈Z1 s at least (1-2E)(-E)(B-E)(Y-)xIYZ. Proof For every let dy()and dz()be the number of neighbours of r in Y and Z,respectively. Then the number of X with dy(z)<(a-e)Y|is at most eX.Suppose otherwise.Then there will be a subset X'of X of size at least eX]such that the density of edges between X'and Y is less than o But this would contradict regu We may similarly show that there are at most values of r for which dz(r)<(-e)ZI.If dy(r)>(a-e)Yl and dz()>(-e)IZl,the number of edges between N(r)nY and N(r)nZ,and consequently the number of triangles containing r,is at least (a-e)(B-e)(-e). Summing over all r E X gives the result. ▣ We will complete the proof of the removal lemma in the next lecture. 2In this and the next lecture, we will prove a beautiful consequence of the regularity lemma, the triangle removal lemma, and show how one may deduce Roth’s theorem from it. The triangle removal lemma says that if a graph contains very few triangles, then one may remove all such triangles by removing very few edges. Though this lemma sounds simple, its proof is surprisingly subtle. We begin with what is known as a counting lemma. Lemma 2 Let G be a graph and let X, Y, Z be subsets of the vertex set V (G). Suppose that (X, Y ), (Y, Z) and (Z, X) are -regular and that d(X, Y ) = α, d(Y, Z) = β and d(Z, X) = γ. Then, provided α, β, γ ≥ 2, the number of triangles xyz with x ∈ X, y ∈ Y and z ∈ Z is at least (1 − 2)(α − )(β − )(γ − )|X||Y ||Z|. Proof For every x, let dY (x) and dZ(x) be the number of neighbours of x in Y and Z, respectively. Then the number of x ∈ X with dY (x) < (α − )|Y | is at most |X|. Suppose otherwise. Then there will be a subset X0 of X of size at least |X| such that the density of edges between X0 and Y is less than α − . But this would contradict regularity. We may similarly show that there are at most |X| values of x for which dZ(x) < (γ − )|Z|. If dY (x) > (α − )|Y | and dZ(x) > (γ − )|Z|, the number of edges between N(x) ∩ Y and N(x) ∩ Z, and consequently the number of triangles containing x, is at least (α − )(β − )(γ − )|Y ||Z|. Summing over all x ∈ X gives the result. ✷ We will complete the proof of the removal lemma in the next lecture. 2