with 0ik-1.Similarly,itk is an edge for at least n/2 values of i.There are at most n- values of i with 0si<k-1.Therefore,since the total number of edges of the form roxi+or of the form rizk with 0<ik-1 is at least n,there must be some i for which both rozi+1 and ritk are edges in G. We claim that C=x02+1r+2…xk工i2i-120 is a Hamiltonian cycle.Suppose not and that there is a set of vertices Y which are not contained in C.Then,since G is connected,there is a vertex z;and a vertex y in Y such that ziy is in E(G).But then we may define a path Pstarting at goingtoand then around the cycle which is longer than P.This would contradict our assumption about P. A tree T is a connected graph containing no cycles.The Erdos-Sos conjecture states that if a tree T has t edges,then any graph G with average degree t must contain a copy of T.This conjecture has been proven,for sufficiently large graphs G,by Ajtai,Komlos,Simonovits and Szemeredi.Here we prove a weaker version of this conjecture. Theorem 3 If a graph G has average degree 2t,it contains every tree T with t edges. Proof We start with a standard reduction,by showing that a graph of average degree 2t has a subgraph of minimum degree t.If the number of vertices in G is n,the number of edges in G is at least tn.If there is a vertex of degree less than t,delete it.This will not decrease the average degree. Moreover,the process must end,since any graph with fewer than 2 vertices cannot have average degree 2t We now use this condition to embed the vertices of the tree greedily.Suppose we have already embedded j vertices,where j<t+1.We will try to embed a new vertex which is connected to some already embedded vertex.By the minimum degree condition,there are at least t possible places to embed this vertex.At most t-1of these are blocked by already embedded vertices,so the embedding may always proceed. 2
with 0 ≤ i ≤ k − 1. Similarly, xixk is an edge for at least n/2 values of i. There are at most n − 1 values of i with 0 ≤ i ≤ k − 1. Therefore, since the total number of edges of the form x0xi+1 or of the form xixk with 0 ≤ i ≤ k − 1 is at least n, there must be some i for which both x0xi+1 and xixk are edges in G. We claim that C = x0xi+1xi+2 . . . xkxixi−1 . . . x0 is a Hamiltonian cycle. Suppose not and that there is a set of vertices Y which are not contained in C. Then, since G is connected, there is a vertex xj and a vertex y in Y such that xjy is in E(G). But then we may define a path P 0 starting at y, going to xj and then around the cycle C which is longer than P. This would contradict our assumption about P. ✷ A tree T is a connected graph containing no cycles. The Erd˝os-S´os conjecture states that if a tree T has t edges, then any graph G with average degree t must contain a copy of T. This conjecture has been proven, for sufficiently large graphs G, by Ajtai, Koml´os, Simonovits and Szemer´edi. Here we prove a weaker version of this conjecture. Theorem 3 If a graph G has average degree 2t, it contains every tree T with t edges. Proof We start with a standard reduction, by showing that a graph of average degree 2t has a subgraph of minimum degree t. If the number of vertices in G is n, the number of edges in G is at least tn. If there is a vertex of degree less than t, delete it. This will not decrease the average degree. Moreover, the process must end, since any graph with fewer than 2t vertices cannot have average degree 2t. We now use this condition to embed the vertices of the tree greedily. Suppose we have already embedded j vertices, where j < t + 1. We will try to embed a new vertex which is connected to some already embedded vertex. By the minimum degree condition, there are at least t possible places to embed this vertex. At most t−1 of these are blocked by already embedded vertices, so the embedding may always proceed. ✷ 2
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
Also,since C has at most edges,we have os-+)9+a+-(-+)+(任-到号+a9 2 2 2 But we also have le(G)2 (1-1+e).Therefore,the process stops once (-)竖-<号-量 that is,when n'vern.From now on,we will assume that we are working within this large well- behaved subgraph G. We will show,by induction on r,that there are r+I sets A1,A2,...,Ar+of size t such that every edge between Ai and Aj,with 1<i<j<r+1,is in G.For r =0,there is nothing to prove. Givenr>0and s=[3t/el,we apply the induction hypothesis to find r disjoint sets B,B2,...,B of size s such that the graph between every two disjoint sets is complete.Let U=V(G)\{BIU...UB} and let W be the set of vertices in U which are adjacent to at least t vertices in each Bi. We are going to estimate the number of edges missing between U and BiU...UBr.Since every vertex in U\W is adjacent to fewer than t vertices in some Bi,we have that the number of missing edges is at least m≥1U八wI(s-t)2(m'-rs-1wD(1-)s On the other hand,every vertex in G'has at most ()n'missing edges.Therefore,counting over all vertices in BU...UBr,we have m≤r(目)r=(-)m Therefore, w1-)2-r0-)-(-)m=(-》m-(-)2 Since ,r and s are constants,we can make W]large by making n'large.In particular,we may make W]such that wm>(食'e- Every element in W has at least t neighbours in each Bi.There are at most ()ways to choose a t-element subset from each of BiU...UBr.By the pigeonhole principle and the size of Wl,there must therefore be some subsets A1,...,Ar and a set Ar+of size t from W such that every vertex in Ar+ is conected to every vertex in A are already joined in the appropriate manner,this completes the proof Note that a careful analysis of the proof shows that one may take t=c(r,e)logn.It turns out that this is also best possible (see example sheet). It remains to prove the Erdos-Stone-Simonovits theorem itself. 2
Also, since G0 has at most n 02 2 edges, we have |e(G)| ≤ 1 − 1 r + 2 (n 2 − n 02 ) 2 + (n − n 0 ) 2 + n 02 2 = 1 − 1 r + 2 n 2 2 + 1 r − 2 n 02 2 + (n − n 0 ) 2 . But we also have |e(G)| ≥ 1 − 1 r + n 2 2 . Therefore, the process stops once 1 r − 2 n 02 2 − n 0 2 < n 2 4 − n 2 , that is, when n 0 ≈ √ rn. From now on, we will assume that we are working within this large wellbehaved subgraph G0 . We will show, by induction on r, that there are r + 1 sets A1, A2, . . . , Ar+1 of size t such that every edge between Ai and Aj , with 1 ≤ i < j ≤ r + 1, is in G0 . For r = 0, there is nothing to prove. Given r > 0 and s = d3t/e, we apply the induction hypothesis to find r disjoint sets B1, B2, . . . , Br of size s such that the graph between every two disjoint sets is complete. Let U = V (G0 )\{B1 ∪ · · · ∪ Br} and let W be the set of vertices in U which are adjacent to at least t vertices in each Bi . We are going to estimate the number of edges missing between U and B1 ∪· · ·∪Br. Since every vertex in U\W is adjacent to fewer than t vertices in some Bi , we have that the number of missing edges is at least m˜ ≥ |U\W|(s − t) ≥ (n 0 − rs − |W|) 1 − 3 s. On the other hand, every vertex in G0 has at most 1 r − 2 n 0 missing edges. Therefore, counting over all vertices in B1 ∪ · · · ∪ Br, we have m˜ ≤ rs 1 r − 2 n 0 = 1 − r 2 sn0 . Therefore, |W| 1 − 3 s ≥ (n 0 − rs) 1 − 3 s − 1 − r 2 sn0 = r 2 − 1 3 sn0 − 1 − 3 rs2 . Since , r and s are constants, we can make |W| large by making n 0 large. In particular, we may make |W| such that |W| > s t r (t − 1). Every element in W has at least t neighbours in each Bi . There are at most s t r ways to choose a t-element subset from each of B1∪· · ·∪Br. By the pigeonhole principle and the size of |W|, there must therefore be some subsets A1, . . . , Ar and a set Ar+1 of size t from W such that every vertex in Ar+1 is connected to every vertex in A1 ∪ · · · ∪ Ar. Since A1, . . . , Ar are already joined in the appropriate manner, this completes the proof. ✷ Note that a careful analysis of the proof shows that one may take t = c(r, ) log n. It turns out that this is also best possible (see example sheet). It remains to prove the Erd˝os-Stone-Simonovits theorem itself. 2
Proof of Erdos-Stone-Simonovits For the lower bound,we consider the Turan graph given by =x(H)-1sets of almost equal size n/r]and [n/r].This has roughly the required number of vertices and it is clear that every subgraph of this graph has chromatic number at most x(H)-1. For the upper bound,note that if H has chromatic number x(H),then,provided t is large enough. it can be embedded in a graph G consisting of x(H)sets A1,A2,...,Ax(H)of size t such that the graph between any two disjoint A;and A,is complete.We simply embed any given colour class into a different A.The theorem now follows from an application of the previous lemma. ▣ 3
Proof of Erd˝os-Stone-Simonovits For the lower bound, we consider the Tur´an graph given by r = χ(H) − 1 sets of almost equal size bn/rc and dn/re. This has roughly the required number of vertices and it is clear that every subgraph of this graph has chromatic number at most χ(H) − 1. For the upper bound, note that if H has chromatic number χ(H), then, provided t is large enough, it can be embedded in a graph G consisting of χ(H) sets A1, A2, . . . , Aχ(H) of size t such that the graph between any two disjoint Ai and Aj is complete. We simply embed any given colour class into a different Ai . The theorem now follows from an application of the previous lemma. ✷ 3
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 1
Lecture 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-StoneSimonovits 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