Lecture 7 We are now ready to give the promised alternative proof of Erdos-Stone-Simonovits.To begin,we will need a counting lemma which generalises that given earlier for triangles. Lemma 1 Let e>be a real number.Let G be a graph and suppose that Vi,V2,...,V are subsets ofV(G)such that V≥2e-△t for each1≤i≤ and the groph between V and V has density d(M,V)≥2 e and is2eA△-l-regular for all1≤i<j≤r.Then G contains a copy of any graph H on t vertices with chromatic number r and marimum degree A. Proof Since the chromatic number of H is at most r.we may split V(A)into r independent sets U1,...,Ur.We will give an embedding f of H into G so that f(Ui)C Vi for all 1<i<r. Let the vertices of H be u1,...,ut.For each 1 h <t,let Lh fu1,...,uhh.For each yeUj Lh, let Th be the set of vertices in V;which are adjacent to all already embedded neighbours of y.That is,letting N(y)=N(y)T is the set of vertices in V adjacent to every elemer nt of f(Nn(y)) We will find,by induction,an embedding of such that,for eachV( Forh=0 there is nothing to prove.We may therefore assume that Ln has been embedded consistent with the induction hypothesis and attempt to embed u=uh+1E Uk into an appropriatevT.Let Y be the set of neighbours of u which are not yet embedded.We wish to find an element vTf() all y e r,lN(o)nT≥T T中NOOT克will complete the proo If such a vertex v exists,taking f(u)=v and Let B be the set of vertices in T which are bad for yY,that is,such that IN(v)< Note that,.by induction,ify∈Ue,Tt|≥elVl.Therefore,,we must have |B,l<e△△-Ikl,for otherwise the density between By and Th would be less than e,contradicting the regularity assumption onG.Hence,since Vl≥2e-△t, T\UeyB,>eIWl-△5eA△-IW≥t Since at most t-1 vertices have already been embedded,an appropriate choice for f(u)exists. In fact,there are at least V-t choices for each vertex u.Therefore,if H has di vertices in Ui, the lemma tells us that,for Vil2e-At,we have at least ca(eΠIWI copies of H,where cH(c)is an appropriate constant.Like the triangle counting lemma,we could make wanted to note that the graph Gcontained a positive proportion of the total number of possible copies of H. We are now ready to give another proof of the Erdos-Stone-Simonovits theorem.That is,we will show that for anyr-chromatic graph H and n sufficiently large,ez(n,H)≤(1-，a+e号， Alternative proof of Erdos-Stone-Simonovits Let H be a graph witht vertices,chromatic number r and maximum degree A.Suppose that G is a graph on n vertices with at least (1-+e edges.We will show how to embed H in G.LetV(G)=X1UX2U,UXy be a号（∈）△△-l-regular partition of the vertex set of G.We remove edges as in the triangle-removal lemma,removing ry if 1 Lecture 7 We are now ready to give the promised alternative proof of Erd˝os-Stone-Simonovits. To begin, we will need a counting lemma which generalises that given earlier for triangles. Lemma 1 Let  > 0 be a real number. Let G be a graph and suppose that V1, V2, . . . , Vr are subsets of V (G) such that |Vi | ≥ 2 −∆t for each 1 ≤ i ≤ r and the graph between Vi and Vj has density d(Vi , Vj ) ≥ 2 and is 1 2  ∆∆−1 -regular for all 1 ≤ i < j ≤ r. Then G contains a copy of any graph H on t vertices with chromatic number r and maximum degree ∆. Proof Since the chromatic number of H is at most r, we may split V (H) into r independent sets U1, . . . , Ur. We will give an embedding f of H into G so that f(Ui) ⊂ Vi for all 1 ≤ i ≤ r. Let the vertices of H be u1, . . . , ut . For each 1 ≤ h ≤ t, let Lh = {u1, . . . , uh}. For each y ∈ Uj\Lh, let T h y be the set of vertices in Vj which are adjacent to all already embedded neighbours of y. That is, letting Nh(y) = N(y) ∩ Lh, T h y is the set of vertices in Vj adjacent to every element of f(Nh(y)). We will find, by induction, an embedding of Lh such that, for each y ∈ V (H)\Lh, |T h y | ≥  |Nh(y)| |Vj |. For h = 0 there is nothing to prove. We may therefore assume that Lh has been embedded consistent with the induction hypothesis and attempt to embed u = uh+1 ∈ Uk into an appropriate v ∈ T h u . Let Y be the set of neighbours of u which are not yet embedded. We wish to find an element v ∈ T h u \f(Lh) such that, for all y ∈ Y , |N(v) ∩ T h y | ≥ |T h y |. If such a vertex v exists, taking f(u) = v and T h+1 y = N(v) ∩ T h y will complete the proof. Let By be the set of vertices in T h u which are bad for y ∈ Y , that is, such that |N(v) ∩ T h y | < |T h y |. Note that, by induction, if y ∈ U` , |T h y | ≥  ∆|V` |. Therefore, we must have |By| < 1 2  ∆∆−1 |Vk|, for otherwise the density between By and T h y would be less than , contradicting the regularity assumption on G. Hence, since |Vk| ≥ 2 −∆t,    T h u \ ∪y∈Y By    > ∆|Vk| − ∆ 1 2  ∆∆−1 |Vk| ≥ t. Since at most t − 1 vertices have already been embedded, an appropriate choice for f(u) exists. ✷ In fact, there are at least 1 2  ∆|Vk| − t choices for each vertex u. Therefore, if H has di vertices in Ui , the lemma tells us that, for |Vi |  2 −∆t, we have at least cH() Yr i=1 |Vi | dr copies of H, where cH() is an appropriate constant. Like the triangle counting lemma, we could make the constant cH() reflect the densities between the various Vi , but I simply wanted to note that the graph G contained a positive proportion of the total number of possible copies of H. We are now ready to give another proof of the Erd˝os-Stone-Simonovits theorem. That is, we will show that for any r-chromatic graph H and n sufficiently large, ex(n, H) ≤  1 − 1 r−1 +   n 2 2 . Alternative proof of Erd˝os-Stone-Simonovits Let H be a graph with t vertices, chromatic number r and maximum degree ∆. Suppose that G is a graph on n vertices with at least  1 − 1 r−1 +   n 2 2 edges. We will show how to embed H in G. Let V (G) = X1 ∪ X2 ∪ · · · ∪ XM be a 1 2 ￾  8
∆ ∆−1 -regular partition of the vertex set of G. We remove edges as in the triangle-removal lemma, removing xy if 1