Lecture 4 The main aim of the next two lectures will be to prove the famous regularity lemma of Szemeredi. This was developed by Szemeredi in his work on what is now known as Sze meredi's theorem.This astonishing theorem says that for any 6>0 and k 23 there exists an no such that,for n2 no,any subset of {1,2,...,n}with at least 6n elements must contain an arithmetic progression of length k. The particular case when k=3 had been proven earlier by Roth and is accordingly known as Roth's theorem. Our initial purpose in proving the regularity lemma will be to give another proof of the Erdos-Stone Simonovits theorem.However,its use is widespread throughout extremal graph theory and we will see a number of other applications in the course. Roughly speaking,Szemeredi's regularity lemma says that no graph is entirely random because every graph is at least somewhat random.More precisely,the regularity lemma says that any graph may be partitioned into a finite number of sets such that most of the bipartite graphs between different sets are random-like.To be absolutely precise,we will need some notation and some definitions Let G be a graph and let A and B be subsets of the vertex set.If we let E(A,B)be the set of edges between A and B,the density of edges between A and B is given by d(A.B)=E(A.B) IAIIBI Definition1 Let Gbe grph and let A and B be two subsets of the verte set.The pair (A.B)is said to be e-regular if,for every A'C A and B'C B with andB d(A',B)-d(A,B)l≤e. We say that a partition V(G)=X1UX2U...UXk is c-regular if ∑XX1s6 n2 where the sum is taken over all pairs (Xi,Xj)which are not e-regular. That is,a bipartite graph is c-regular if all small induced subgraphs have approximately the same density as the full graph and a partition of the vertex set of a graph G into smaller sets isc-regular if almost every pair forms a bipartite graph which is c-regular.The regularity lemma is now as follows. Theorem 1 (Szemeredi's regularity lemma)For every e>0 there erists an M such that,for every graph G,there is an e-regular partition of the vertex set of G with at most M pieces. In order to prove the regularity lemma,we will associate a function,known as the mean square density, with each partition of V(G).We will prove that if a particular partition is not e-regular it may be further partitioned in such a way that the mean square density increases.But,as we shall see,the mean square density is bounded above by 1,so we eventually reach a contradiction. Definition 2 Let G be a graph.Given a partition V(G)=X1UX2U...UXk of the verter set of G, the mean square density of this partition is given by ∑xaxlacx,.XP 1Lecture 4 The main aim of the next two lectures will be to prove the famous regularity lemma of Szemer´edi. This was developed by Szemer´edi in his work on what is now known as Szemer´edi’s theorem. This astonishing theorem says that for any δ > 0 and k ≥ 3 there exists an n0 such that, for n ≥ n0, any subset of {1, 2, . . . , n} with at least δn elements must contain an arithmetic progression of length k. The particular case when k = 3 had been proven earlier by Roth and is accordingly known as Roth’s theorem. Our initial purpose in proving the regularity lemma will be to give another proof of the Erd˝os-Stone￾Simonovits theorem. However, its use is widespread throughout extremal graph theory and we will see a number of other applications in the course. Roughly speaking, Szemer´edi’s regularity lemma says that no graph is entirely random because every graph is at least somewhat random. More precisely, the regularity lemma says that any graph may be partitioned into a finite number of sets such that most of the bipartite graphs between different sets are random-like. To be absolutely precise, we will need some notation and some definitions. Let G be a graph and let A and B be subsets of the vertex set. If we let E(A, B) be the set of edges between A and B, the density of edges between A and B is given by d(A, B) = |E(A, B)| |A||B| . Definition 1 Let G be a graph and let A and B be two subsets of the vertex set. The pair (A, B) is said to be -regular if, for every A0 ⊂ A and B0 ⊂ B with |A0 | ≥ |A| and |B0 | ≥ |B|, |d(A 0 , B0 ) − d(A, B)| ≤ . We say that a partition V (G) = X1 ∪ X2 ∪ · · · ∪ Xk is -regular if X |Xi ||Xj | n2 ≤ , where the sum is taken over all pairs (Xi , Xj ) which are not -regular. That is, a bipartite graph is -regular if all small induced subgraphs have approximately the same density as the full graph and a partition of the vertex set of a graph G into smaller sets is -regular if almost every pair forms a bipartite graph which is -regular. The regularity lemma is now as follows. Theorem 1 (Szemer´edi’s regularity lemma) For every  > 0 there exists an M such that, for every graph G, there is an -regular partition of the vertex set of G with at most M pieces. In order to prove the regularity lemma, we will associate a function, known as the mean square density, with each partition of V (G). We will prove that if a particular partition is not -regular it may be further partitioned in such a way that the mean square density increases. But, as we shall see, the mean square density is bounded above by 1, so we eventually reach a contradiction. Definition 2 Let G be a graph. Given a partition V (G) = X1 ∪ X2 ∪ · · · ∪ Xk of the vertex set of G, the mean square density of this partition is given by X 1≤i,j≤k |Xi ||Xj | n2 d(Xi , Xj ) 2 . 1