Probabilistic methods: alterations Let p > 0 be a constant that we will choose at the end of the proof Randomly choose a graph G on n vertices by including each edge with probability p. The expected number of copies of Ks,s in G is () ( 25 ) 15 2 In each copy of Ks,s in G, we delete one edge (the alteration) The expected number of edges in the resulting graph is at -2(.() least (2) p - (25) (25) ps2 Problem: If we choose p Se ( n= = 2 7 ( s + 1 ) ) The alterd grush is ky's free Again compare this to the upper bound 2 - 3 ex (n, Ks.s) = O(n2-1/s ) ex (n, Kyy ) = nin ex ( n , kyp ) ? ex ( ", kaz ) = n