Lecture 8 We are now going to begin an in-depth study of the extremal number for bipartite graphs.We have already seen that if H is a bipartite graph ex(n,H)<en2 for any e>0.We now prove a much stronger result,due essentially to Kovari,Sos and Turan. Theorem 1 For any natural numbers s and t with s <t,there erists a constant c such that ex(n,Kst)≤cm2- Proof Suppose that we have a graph G with n vertices,at least cn2-edges and not containing as asubgraph.Note that the average degree of are going to count pairs (S) consisting of sets S of size s all elements of which are connected by an edge to v.On the one hand, the number of such pairs is given by for n sufficiently large.On the other hand,the number of pairs (v,S)is at mos e-(9）st- for otherwise there would be some set S of s vertices which have t neighbours in common.Therefore, if we choose c so that c2t-1,we have a contradiction 口 By being a little more careful,we could have obtained the bound ex(m,Ks)≤(1+o(1》5(t-1)n2-. It is known that this bound is sharp in various specific cases.For example,when H=K1.t and n satisfies some divisibility,there isagraph onvertices which does not contain any copies of H-simply take a graph such that every vertex has degree1. A more interesting example is H=K2.2.The following K2.2-free construction,due to Erdos,Renyi and Ss,allows us to show that er(nK) Construction of K2.2-free graph Let p be a prime and consider the graph on n=p2-1 vertices whose vertex set is Zp x Zp {(0,0)}and where (y)is joined to (a,b)if and only if ax +by =1. For a fixed (,y),there are exactly p solutions (a,b)to ax+by =1.To see this,we must split into some subcases.If r =0,then there is a unique non-zero solution for b and anything works for a. Similarly,if y=0,a is uniquely determined and b may be anything.If both x and y are non-zero,it is elementary to see that any choice of b gives rise to a unique choice of a,i.e.,a=-1(1-by). Therefore,(,y)has degree at least p-1 (one of the solutions could be (a,b)=(,y),which we ignore)and the graph has at least in(p-1)n3/2 edges.Moreover,the graph does not contain a K2.2.Suppose otherwise and that (a,b),(r,y),(a',B),(r',y)is a K2.2.Then the set of simultaneous equations ur+vy =1 and ur'+vy'=1 would have two solutions,(u,v)=(a,b)and (a',b),which is clearly impossible,since any two distinct lines meet in at most one point. 1 Lecture 8 We are now going to begin an in-depth study of the extremal number for bipartite graphs. We have already seen that if H is a bipartite graph ex(n, H) ≤ n2 for any  > 0. We now prove a much stronger result, due essentially to K˝ov´ari, S´os and Tur´an. Theorem 1 For any natural numbers s and t with s ≤ t, there exists a constant c such that ex(n, Ks,t) ≤ cn2− 1 s . Proof Suppose that we have a graph G with n vertices, at least cn2− 1 s edges and not containing Ks,t as a subgraph. Note that the average degree of G is 2cn1− 1 s . We are going to count pairs (v, S) consisting of sets S of size s all elements of which are connected by an edge to v. On the one hand, the number of such pairs is given by X v  d(v) s  ≥ n  1 n P v d(v) s  ≥ n  2cn1− 1 s s  ≥ n c sn s−1 s! = c s n s s! , for n sufficiently large. On the other hand, the number of pairs (v, S) is at most (t − 1) n s  ≤ (t − 1)n s s! , for otherwise there would be some set S of s vertices which have t neighbours in common. Therefore, if we choose c so that c s ≥ t − 1, we have a contradiction. ✷ By being a little more careful, we could have obtained the bound ex(n, Ks,t) ≤ (1 + o(1))1 2 (t − 1) 1 s n 2− 1 s . It is known that this bound is sharp in various specific cases. For example, when H = K1,t and n satisfies some divisibility assumptions, there is a graph on n vertices with 1 2 (t − 1)n edges which does not contain any copies of H - simply take a graph such that every vertex has degree t − 1. A more interesting example is H = K2,2. The following K2,2-free construction, due to Erd˝os, R´enyi and S´os, allows us to show that ex(n, K2,2) ≈ 1 2 n 3/2 . Construction of K2,2-free graph Let p be a prime and consider the graph on n = p 2 − 1 vertices whose vertex set is Zp × Zp\{(0, 0)} and where (x, y) is joined to (a, b) if and only if ax + by = 1. For a fixed (x, y), there are exactly p solutions (a, b) to ax + by = 1. To see this, we must split into some subcases. If x = 0, then there is a unique non-zero solution for b and anything works for a. Similarly, if y = 0, a is uniquely determined and b may be anything. If both x and y are non-zero, it is elementary to see that any choice of b gives rise to a unique choice of a, i.e., a = x −1 (1 − by). Therefore, (x, y) has degree at least p − 1 (one of the solutions could be (a, b) = (x, y), which we ignore) and the graph has at least 1 2 n(p − 1) ≈ 1 2 n 3/2 edges. Moreover, the graph does not contain a K2,2. Suppose otherwise and that (a, b),(x, y),(a 0 , b0 ),(x 0 , y0 ) is a K2,2. Then the set of simultaneous equations ux + vy = 1 and ux0 + vy0 = 1 would have two solutions, (u, v) = (a, b) and (a 0 , b0 ), which is clearly impossible, since any two distinct lines meet in at most one point. 1