Lecture 3 For general graphs H,we are interested in the function ex(n,H),defined as follows ex(n,H)maxfe(G):G]=n,HG). Turan's theorem itself tells us that ea,ks(-）爱 We are now going to deal with the general case.We will show that the behaviour of the extremal function ex(n,H)is tied intimately to the chromatic number of the graph H. Definition 1 The chromatic number x(H)of a graph H is the smallest natural number c such that the vertices of H can be coloured with c colours and no two vertices of the same colour are adjacent. The fundamental result which we shall prove,known as the Erdos-Stone-Simonovits theorem,is the following. Theorem 1 (Erdos-Stone-Simonovits)For any fired graph H and any fired e>0,there is no such that,for any n>no, (-智saa助≤(-+g 1 For the complete graph K,the chromatic number isr+1,so in this case the Erdos-Stone-Simonovits the orem reduces to an approximate version of Turan's theorem.For bipartite H,it gives ex(n,H)< en2 for all0.This is an important theme,one we will return to later in the course. To prove the Erds-Stone-Simonovits theorem,we will first prove the following lema which already contains most of the content. Lemma 1 For any natural numbers r and t and any positive e with e<1/r,there erists an no such that the following holds.Any graph G with nz no vertices and(1-1+e)edges contains r+1 disjoint sets of vertices A1,....Ar+of size t such that the graph between Ai and Aj,for every 1≤i<j≤r+l,is complete. Proof To begin,we find a subgraph G'of G such that every degree is at least (1-+V(G)l. To find such a graph,we remove one vertex at a time.If,in this process,we reach a graph with vertices and there is some vertex which has fewer than (1+(neighbors,we remove it. Suppose that this process terminates when we have reached a graph Gwith n'vertices.To show that small,coder the of edes that have been removed from the graph.When the graph has e vertices,we remove at most (1-+)(edges.Therefore,the total number of edges removed is at most 三（-+)-(-中+身血g4≤(-+身9，a2 2 》 1 Lecture 3 For general graphs H, we are interested in the function ex(n, H), defined as follows. ex(n, H) = max{e(G) : |G| = n, H 6⊂ G}. Tur´an’s theorem itself tells us that ex(n, Kr+1) ≤  1 − 1 r  n 2 2 . We are now going to deal with the general case. We will show that the behaviour of the extremal function ex(n, H) is tied intimately to the chromatic number of the graph H. Definition 1 The chromatic number χ(H) of a graph H is the smallest natural number c such that the vertices of H can be coloured with c colours and no two vertices of the same colour are adjacent. The fundamental result which we shall prove, known as the Erd˝os-Stone-Simonovits theorem, is the following. Theorem 1 (Erd˝os-Stone-Simonovits) For any fixed graph H and any fixed  > 0, there is n0 such that, for any n ≥ n0,  1 − 1 χ(H) − 1 −   n 2 2 ≤ ex(n, H) ≤  1 − 1 χ(H) − 1 +   n 2 2 . For the complete graph Kr+1, the chromatic number is r+1, so in this case the Erd˝os-Stone-Simonovits theorem reduces to an approximate version of Tur´an’s theorem. For bipartite H, it gives ex(n, H) ≤ n2 for all  > 0. This is an important theme, one we will return to later in the course. To prove the Erd˝os-Stone-Simonovits theorem, we will first prove the following lemma, which already contains most of the content. Lemma 1 For any natural numbers r and t and any positive  with  < 1/r, there exists an n0 such that the following holds. Any graph G with n ≥ n0 vertices and ￾ 1 − 1 r + 
n 2 2 edges contains r + 1 disjoint sets of vertices A1, . . . , Ar+1 of size t such that the graph between Ai and Aj , for every 1 ≤ i < j ≤ r + 1, is complete. Proof To begin, we find a subgraph G0 of G such that every degree is at least ￾ 1 − 1 r +  2
|V (G0 )|. To find such a graph, we remove one vertex at a time. If, in this process, we reach a graph with ` vertices and there is some vertex which has fewer than ￾ 1 − 1 r +  2
` neighbors, we remove it. Suppose that this process terminates when we have reached a graph G0 with n 0 vertices. To show that n 0 is not too small, consider the total number of edges that have been removed from the graph. When the graph has ` vertices, we remove at most ￾ 1 − 1 r +  2
` edges. Therefore, the total number of edges removed is at most Xn `=n0+1  1 − 1 r +  2  ` =  1 − 1 r +  2  (n − n 0 )(n + n 0 + 1) 2 ≤  1 − 1 r +  2  (n 2 − n 02 ) 2 + (n − n 0 ) 2 . 1