Lecture 5 To complete the proof of the regularity lemma,we need to prove that if a partition is not e-regular there is a refinement of this partition which has a higher mean square density.This is taken care of in the following lemma Lemma 1 Let G be a graph and let X1UX2U...UXk be a partition of the vertices of G which is not e-regular.Then there is a refinement X11U...UXiaU...UXU...UXkax such that every ai is at most and the mean square density is at least Proof Let I={(i,j):(Xi,Xj)is not e-regular}.Let a2 be the mean square density of G with respect to X1UUXk. For each (i,j)E I,the previous lemma gives us partitions X:=AA and X;=BUB for which 万4a4g,g9y2≥40x.XP+ ispas2 For each i,..UXi be the partition of Xi which refines all partitions which arise from partitioning Xi or Xj into Ais or Bis.Note that this partition has at most 22 pieces,that is, a<22k.Moreover,since refining bipartite partitions does not decrease the mean square density,we have 22 xplxld(Xo)≥dx.xP+d g台XX for all(,）∈L.Multiplying both sides of the equation by and summing over all(亿，)，wg have 22xXwP≥∑+e∑X n2 1<<k=19=1 1<<k n2 (1n2 ≥a2+5 The result follows. 0 We now have all the ingredients necessary to finish the proof. Proof of Szemeredi's regularity lemma Start with a trivial partition into one set.If it is e- regular,we are done.Otherwise,there is a partition into at most 4 sets where the mean square density increases by e5. If,at stage i,we have a partition into k pieces and this partition is not e-regular,there is a partition pieces in the final partition is at most a tower of 2s of height 2e. ▣ The tower function i()is defined by to()=x and,for i0,t+()=24().The bound given in the proof above is t2s(2),which is clearly enormous.Surprisingly,as was shown by Gowers,there are graphs where,to get an e-regular partition,one needs roughly that many pieces in the partition. Lecture 5 To complete the proof of the regularity lemma, we need to prove that if a partition is not -regular there is a refinement of this partition which has a higher mean square density. This is taken care of in the following lemma. Lemma 1 Let G be a graph and let X1 ∪ X2 ∪ · · · ∪ Xk be a partition of the vertices of G which is not -regular. Then there is a refinement X11 ∪ · · · ∪ X1a1 ∪ · · · ∪ Xk1 ∪ · · · ∪ Xkak such that every ai is at most 2 2k and the mean square density is at least  5 larger. Proof Let I = {(i, j) : (Xi , Xj ) is not -regular}. Let α 2 be the mean square density of G with respect to X1 ∪ · · · ∪ Xk. For each (i, j) ∈ I, the previous lemma gives us partitions Xi = A ij 1 ∪ A ij 2 and Xj = B ij 1 ∪ B ij 2 for which X 1≤p,q≤2 |A ij p ||B ij q | |Xi ||Xj | d(A ij p , Bij q ) 2 ≥ d(Xi , Xj ) 2 +  4 . For each i, let Xi1 ∪ · · · ∪ Xiai be the partition of Xi which refines all partitions which arise from partitioning Xi or Xj into Ais or Bis. Note that this partition has at most 22k pieces, that is, ai ≤ 2 2k . Moreover, since refining bipartite partitions does not decrease the mean square density, we have Xai p=1 Xaj q=1 |Xip||Xjq| |Xi ||Xj | d(Xip, Xjq) 2 ≥ d(Xi , Xj ) 2 +  4 , for all (i, j) ∈ I. Multiplying both sides of the equation by |Xi||Xj | n2 and summing over all (i, j), we have X 1≤i,j≤k Xai p=1 Xaj q=1 |Xip||Xjq| n2 d(Xip, Xjq) 2 ≥ X 1≤i,j≤k |Xi ||Xj | n2 d(Xi , Xj ) 2 +  4 X (i,j)∈I |Xi ||Xj | n2 ≥ α 2 +  5 . The result follows. ✷ We now have all the ingredients necessary to finish the proof. Proof of Szemer´edi’s regularity lemma Start with a trivial partition into one set. If it is - regular, we are done. Otherwise, there is a partition into at most 4 sets where the mean square density increases by  5 . If, at stage i, we have a partition into k pieces and this partition is not -regular, there is a partition into at most k2 2k ≤ 2 2 k pieces whose mean square density is at least  5 greater. Because the mean square density is bounded above by 1, this process must end after at most  −5 steps. The number of pieces in the final partition is at most a tower of 2s of height 2 −5 . ✷ The tower function ti(x) is defined by t0(x) = x and, for i ≥ 0, ti+1(x) = 2ti(x) . The bound given in the proof above is t2−5 (2), which is clearly enormous. Surprisingly, as was shown by Gowers, there are graphs where, to get an -regular partition, one needs roughly that many pieces in the partition. 1