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