This construction works fornp1,but the result that e(H)follows for all nsince we know that,for n large,there exists a prime between vn-n1/3 and vn(though this is a very deep result). ▣ There is also a result of Fiiredi extending this result.It says that,for each t, crn.ka) There is also a construction,due to Brown,which gives a lower bound ex(n,K33)>c'n5/3.Roughly speaking,take a prime p=3(mod 4)and consider the graph on p vertices whose vertex set iswhere (y,2)is joined to (a,b,c)if and only if (a-x)2+(b-y)2+(c-z)2=1.For any given (y,2),there will be on the order of p2 elements(a,b,c)to which it is connected.There are,therefore,around c'n/ edges in the graph.Moreover,the unit spheres around the three distinct points (,,)(,)and (",")cannot meet in more than two points,so the graph does not contain a K3.3.The result follows for all n by a similar argument to above. Other than the constructions mentioned,there is also an impressive construction of Alon,Kollar Ronyai and Szabo which shows that if t (s-1)!+1,the upper bound we gave at the start of the lecture is essentially sharp,that is,er(n,K)>cn2.This includes,though without sharp multiplying constants,all the cases discussed thusfar. Apart from this.almost the best known lower bound follows from the following random construction Theorem 2 For any s,t>2,there erists a constant d such that e(n,K)≥cn2-号 Proof Choose each edge in the graph randomly with probabilityp The expected number of copies of Kst is p(））≤ Phrased differently,if is the random variable counting copies of KthenE(On the other hand,the expected number of edges in the graph is p(2)>ipn2.Again,if I is the random variable coutin the umber of edges in the graph,then E(nBy linearity of expectation. u-刀=0-0≥m2-n≥m2=忘 The final inequality follows since psnttspn2.This in turn follows from t-1 p-n-2≤()≤g Therefore,there exists some graph Gonn vertices for which We may therefore remove one edge from each of the Kremoving all copies of Kand still be left with a graph 2This construction works for n = p 2 − 1, but the result that ex(n, H) ≈ 1 2 n 3/2 follows for all n since we know that, for n large, there exists a prime between √ n − n 1/3 and √ n (though this is a very deep result). ✷ There is also a result of F¨uredi extending this result. It says that, for each t, ex(n, K2,t+1) ≈ √ t 2 n 3/2 . There is also a construction, due to Brown, which gives a lower bound ex(n, K3,3) ≥ c 0n 5/3 . Roughly speaking, take a prime p ≡ 3(mod 4) and consider the graph on p 3 vertices whose vertex set is Z 3 p , where (x, y, z) is joined to (a, b, c) if and only if (a−x) 2 + (b−y) 2 + (c−z) 2 = 1. For any given (x, y, z), there will be on the order of p 2 elements (a, b, c) to which it is connected. There are, therefore, around c 0n 5/3 edges in the graph. Moreover, the unit spheres around the three distinct points (x, y, z),(x 0 , y0 , z0 ) and (x 00, y00, z00) cannot meet in more than two points, so the graph does not contain a K3,3. The result follows for all n by a similar argument to above. Other than the constructions mentioned, there is also an impressive construction of Alon, Koll´ar, R´onyai and Szab´o which shows that if t ≥ (s − 1)! + 1, the upper bound we gave at the start of the lecture is essentially sharp, that is, ex(n, Ks,t) ≥ c 0n 2− 1 s . This includes, though without sharp multiplying constants, all the cases discussed thusfar. Apart from this, almost the best known lower bound follows from the following random construction. Theorem 2 For any s, t ≥ 2, there exists a constant c 0 such that ex(n, Ks,t) ≥ c 0n 2− (s+t−2) (st−1) . Proof Choose each edge in the graph randomly with probability p = 1 2 n − (s+t−2) (st−1) . The expected number of copies of Ks,t is p st n s n t  ≤ p stn s+t . Phrased differently, if J is the random variable counting copies of Ks,t, then E(J) ≤ p stn s+t . On the other hand, the expected number of edges in the graph is p ￾ n 2
≥ 1 4 pn2 . Again, if I is the random variable counting the number of edges in the graph, then E(I) ≥ 1 4 pn2 . By linearity of expectation, E(I − J) = E(I) − E(J) ≥ 1 4 pn2 − p stn s+t ≥ 1 8 pn2 = 1 16 n 2− (s+t−2) (st−1) . The final inequality follows since p stn s+t ≤ 1 8 pn2 . This in turn follows from p st−1n s+t−2 ≤  1 2 st−1 ≤ 1 8 . Therefore, there exists some graph G on n vertices for which I − J ≥ 1 16n 2− (s+t−2) (st−1) . We may therefore remove one edge from each of the Ks,t, removing all copies of Ks,t and still be left with a graph containing 1 16n 2− (s+t−2) (st−1) edges. ✷ 2