EXERCISES 11 Clearly, 品®=222m2-n LetYbe a random variable whose value is the number of membersBthat are disjoint to all the A;(1i<t).By the convexity of z the expected value of Y satishes E[Y] Since Y m we conclude that Pry≥m-w22]≥m2p (1.3) One can check that for t=[1+1/6],m1-t52/2>2n/2 and the right-hand side (2 an u hisunion is disjoint to more than member .This contradiction implies inequality(.D. 1.6 EXERCISES 1.Prove that if there is a real p,0<p 1 such that (）p+(⑨a-p6<1, then the Ramsey number R(,t)satisfies R(,t)>n.Using this,show that R(4,)≥2(t3/2/nt)3/2). 2.Supposen and let H be an n-uniform hypergraph with at most edges.Prove that there is a coloring of the vertices of H by four colors so that in every edge all four colors are represented. 3.()Prove that for every two independent,identically distributed real random variables X and y. PrX-YI≤2≤3PrIX-Y1≤1). 4.(Let G=(V,E)be a graph with n vertices and minimum degree 10. Prove that there is a partition of V into two disjoint subsets A and B so thatEXERCISES 11 Clearly, £ v(B) = 2d{F) > 2m2 - p l 2 . Let y be a random variable whose valué is the number of members B € T that are disjoint to all the At (1 < i < t). By the convexity of z l the expected valué of Y satisfies E[y] Since y<mw e conclude that > i_.mf?ffiy>w-^. nv \ m ) ude that Pr Y > m1 "^ 2 / 2 ' > m"tó2 / 2 . (1.3) One can check that for t = [1 + 1/<5~|, m1_t<52/ 2 > 2ra/ 2 and the right-hand side of (1.3) is greater than the right-hand side of (1.2). Thus, with positive probability, |^41 U A2 U • • • U At | > n/2 and still this unión is disjoint to more than 2"/2 members of F. This contradiction implies inequality (1.1). • 1.6 EXERCISES 1. Prove that if there is a real p, 0 < p < 1 such that then the Ramsey number R(k, t) satisfies R(k, t) > n. Using this, show that ü(4,í) >0(í 3 / 2 /(lní) 3/2 ). 2. Suppose n > 4 and let H be an n-uniform hypergraph with at most 4™~1 /3Tl edges. Prove that there is a coloring of the vértices of H by four colors so that in every edge all four colors are represented. 3. (*) Prove that for every two independent, identically distributed real random variables X and Y, Pr [\X -Y\<2}< 3Pr [\X - Y\ < 1] . 4. (*) Let G = {V, E) be a graph with n vértices and mínimum degree 5 > 10. Prove that there is a partition of V into two disjoint subsets A and B so that