If there is a triangle zyz in G,then (,y),(,y+(--y)),(+(--y),y)will all be in A and thus motwvo es and make the graph triangl-free.But every point in A determines adegenerate triangle.Hence,there are at least 6n2 degenerate triangles,all of which are edge disjoint.We cannot,therefore,remove them all by removing n2 edges.This contradiction implies the required result. ▣ This implies Roth's theorem as follows. Theorem 3 (Roth)For all >0 there erists no such that,for,any subset A of [n]with at least &n elements contains an arithmetic progression of length 3. Proof Let B C [2n2 be{():-yA).Then B]2 n2 =(2n)2 so we have (.).(d,) and (,+d)in B.This translates back to tell us thatyd,-y and-d are in A,as required. ▣ To prove Szemeredi's theorem by the same method,one must first generalise the regularity lemma to hypergraphs.This was done by Gowers and,independently,by Nagle,Rodl,Schacht and Skokan. This method also allows you to prove the following more general theorem. Theorem 4(Multidimensional Szemeredi)For any natural number d,any 6>0 and any subset P ofzd,there erists an no such that,for any n>no,every subset of n]of density at least 6 contains a homothetic copy of P,that is,a set of the form k.P,wherek and eE Zd The theorem proved above corresponds to the case where d =2 and P ={(0,0),(1,0),(0,1)}.Sze- meredi's theorem for length k progressions is the case where d=1 and P=(0,1,2,...,-1). 2If there is a triangle xyz in G, then (x, y),(x, y+(z−x−y)),(x+(z−x−y), y) will all be in A and thus we will have the required triple unless z = x + y. This means that there are at most n 2 = 1 64n (4n) 3 triangles in G. By the triangle removal lemma, for n sufficiently large, one may remove δ 2 n 2 edges and make the graph triangle-free. But every point in A determines a degenerate triangle. Hence, there are at least δn2 degenerate triangles, all of which are edge disjoint. We cannot, therefore, remove them all by removing δ 2 n 2 edges. This contradiction implies the required result. ✷ This implies Roth’s theorem as follows. Theorem 3 (Roth) For all δ > 0 there exists n0 such that, for n ≥ n0, any subset A of [n] with at least δn elements contains an arithmetic progression of length 3. Proof Let B ⊂ [2n] 2 be {(x, y) : x − y ∈ A}. Then |B| ≥ δn2 = δ 4 (2n) 2 so we have (x, y),(x + d, y) and (x, y + d) in B. This translates back to tell us that x − y − d, x − y and x − y + d are in A, as required. ✷ To prove Szemer´edi’s theorem by the same method, one must first generalise the regularity lemma to hypergraphs. This was done by Gowers and, independently, by Nagle, R¨odl, Schacht and Skokan. This method also allows you to prove the following more general theorem. Theorem 4 (Multidimensional Szemer´edi) For any natural number d, any δ > 0 and any subset P of Z d , there exists an n0 such that, for any n ≥ n0, every subset of [n] d of density at least δ contains a homothetic copy of P, that is, a set of the form k.P + `, where k ∈ Z and ` ∈ Z d . The theorem proved above corresponds to the case where d = 2 and P = {(0, 0),(1, 0),(0, 1)}. Sze￾mer´edi’s theorem for length k progressions is the case where d = 1 and P = {0, 1, 2, . . . , k − 1}. 2