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 that
EXERCISES 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
12 THE BASIC METHOD A O(n In 6/6),and each vertex of B has at least one neighbor in A and at least one neighbor in B. 5.(Let G=(V,E)be a graph on n 10 vertices and suppose that if we add to Gany edge not in G then the number of copies of a complete graph on 10 vertices in it increases. Show that the number ofedes of is at 6.(*)Theorem 1.2.I asserts that for every integer>0 there is a tournament Tk= (VE)withsuch that for every setU of at mostvertices of Tk there is a vertex so that all directed arcs ,u):uU}are in E.Show that each such tournament contains at least (2)vertices. 7.Let{(Ai,B),1 is h}be a family of pairs of subsets of the set of integers such that Al =k for all i and Bil =l for all i,A;B:0 and (A,nB,)U(A,nB)≠0 for all i≠j.Prove that h≤(k+I)+'/(k). 8.(Prefix-free codes:Kraft Inequality).Let F be a finite collection of binary strings of finite lengths and assume no member of F is a prefix of another one. Let N denote the number of strings of lengthinFProve that 9.()(Uniquely decipherable codes:Kraft-McMillan Inequality).Let Fbe a finite collection of binary strings of finite lengths and assume that no two distintcotionsofnitefcddm binary sequence.Let N:denote the number of strings of length iin F.Prove that ∑≤1 10.Prove that there is an absolute constant c>0 with the following property. Let A be an n by n matrix a permutation of the rows ofAso that no cointhe permuted marix contains an increasing subsequence of length at least cvn
12 THE BASIC METHOD \A\ < 0(n ln 5/8), and each vértex of B has at least one neighbor in A and at least one neighbor in B. 5. (*) Let G = (V, E) be a graph on n > 10 vértices and suppose that if we add to G any edge not in G then the number of copies of a complete graph on 10 vértices in it increases. Show that the number of edges of G is at least 8n — 36. 6. (*) Theorem 1.2.1 asserts that for every integer k > 0 there is a tournament Tk = (V, E) with | V| > k such that for every set U of at most k vértices of Tfc there is a vértex v so that all directed ares {(v, u) : u e U} are in E. Show that each such tournament contains at least fl(k2k ) vértices. 7. Let {(AÍ,BÍ), 1 < i < h} be a family of pairs of subsets of the set of integers such that \Ai\ = k for all i and |B¿| = l for all i, Ai n fí¿ = 0 and (Ai n Bj) U (A3 C\BÍ)^% for all i ^ j . Prove that h < (k + l)k+l/(kk l l ). 8. (Prefix-free codes; Kraft Inequality). Let F be a finite collection of binary strings of finite lengths and assume no member of F is a prefix of another one. Let Ni denote the number of strings of length i in F. Prove that E — < i. 9. (*) (Uniquely decipherable codes; Kraft-McMillan Inequality). Let F be a finite collection of binary strings of finite lengths and assume that no two distinct concatenations of two finite sequences of codewords result in the same binary sequence. Let AT¿ denote the number of strings of length i in F. Prove that Ni E . <i . 2i - 10. Prove that there is an absolute constant c > 0 with the following property. Let A be an n by n matrix with pairwise distinct entries. Then there is a permutation of the rows of A so that no column in the permuted matrix contains an increasing subsequence of length at least C\fa