EXERCISES 17 2.Suppose n4.and let H be an n-uniform hypergraph with at most 4-1/3 edges.Prove that there is a coloring of the vertices of A by four colors so that in every edge all four colors are represented. PrIx-YI≤2]≤3PlX-YI≤1]. 4.(*LetG=(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 Al s O(nIn 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 graphonn10 vertices,and suppose that if we add toG any edge not in G.then the number of copies of a complete graph on 10 vertices 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 integ (V.E)with IVI>k t mostk vertices of T there is at all directed ares【(o,):u∈U are in E Show that each such tournament contains at leastv 7.Let(A:,B).I sish)be a family of pairs of subsets of the set of integers such that IA.=k for all iand Bl =I for all i.AnB=0.and (A:nB)U(AnB) for all i≠j.Prove that h≤k+D/, 8.(Prefix-free codes;Kraft inequality).Let F be a finite collection of binary strings of finite lengths,and assume that no member of F is a prefix of another one.Let N:denote the number of strings of length iin F.Prove that 4s1. 9.()(Uniquely decipherable codes;Kraft-McMillan inequality).Let Fbe 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 N denote the number of strings of length i in F.Prove that 益 s.Then there is don of no umn
EXERCISES 17 2. Suppose n ≥ 4, and let H be an n-uniform hypergraph with at most 4n−1∕3n 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 and identically distributed real random variables X and Y, Pr[|X − Y| ≤ 2] ≤ 3 Pr[|X − Y| ≤ 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 |A| ≤ O(n ln 𝛿∕𝛿), 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 G any edge not in G, then the number of copies of a complete graph on 10 vertices 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 vertices of Tk there is a vertex 𝑣 so that all directed arcs {(𝑣, u) ∶ u ∈ U} are in E. Show that each such tournament contains at least Ω(k2k) vertices. 7. Let {(Ai, Bi ), 1 ≤ i ≤ h} be a family of pairs of subsets of the set of integers such that |Ai | = k for all i and |Bi | = l for all i, Ai ∩ Bi = ∅, and (Ai ∩ Bj )∪(Aj ∩ Bi ) ≠ ∅ for all i ≠ j. Prove that h ≤ (k + l) k+l ∕(kkl l ). 8. (Prefix-free codes; Kraft inequality). Let F be a finite collection of binary strings of finite lengths, and assume that no member of F is a prefix of another one. Let Ni denote the number of strings of length i in F. Prove that ∑ i Ni 2i ≤ 1. 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 Ni denote the number of strings of length i in F. Prove that ∑ i Ni 2i ≤ 1. 10. Prove that there is an absolute constant c > 0 with the following property: let A be an n × 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 √n
THE PROBABILISTIC LENS: The Erdos-Ko-Rado Theorem A family F of sets is called intersecting if A.BF implies A Suppose n 2 2k,and let F be an intersecting family of k-element subsets of an n-set,for def- initeness (0.....n-1).The Erdos-Ko-Rado theorem is that (This is achievable by taking the family of particular pointWe givea short proof due to Katona(1972). Lemma 1 For 0sssn-1,set A,=(s,s+1.....s+k-1).where addition is modulo n.Then F can contain at most k of the sets A. Proof.Fix some A,EF.All other sets A,that intersect A,can be partitioned into k-1 pairs (A..A).(1 sisk-1),and the members of each such pair are disjoint.The result follows,since F can contain at most one member of each pair. ■ Now we prove the Erdos-Ko-Rado theorem.Let a permutation of (0. n-l)andi∈(0，…，n-l}be chosen randomly,uniformly and independently and set A ((i),(i+1)....,(+k-1)),addition again modulo n.Conditioning on any choice of o,the lemma gives Pr[A∈F]≤k/n.Hence Pr[A∈F]≤k/m.ButA is uniformly chosen from all k-sets so A之mAeI ( and ms（)=(-)
THE PROBABILISTIC LENS: The Erdos–Ko–Rado ˝ Theorem A family of sets is called intersecting if A, B ∈ implies A ∩ B ≠ ∅. Suppose n ≥ 2k, and let be an intersecting family of k-element subsets of an n-set, for definiteness {0, … , n − 1}. The Erdos–Ko–Rado theorem is that ˝ || ≤ ( n−1 k−1 ) . This is achievable by taking the family of k-sets containing a particular point. We give a short proof due to Katona (1972). Lemma 1 For 0 ≤ s ≤ n − 1, set As = {s,s + 1, … ,s + k − 1}, where addition is modulo n. Then can contain at most k of the sets As. Proof. Fix some As ∈ . All other sets At that intersect As can be partitioned into k − 1 pairs {As−i, As+k−i}, (1 ≤ i ≤ k − 1), and the members of each such pair are disjoint. The result follows, since can contain at most one member of each pair. ◾ Now we prove the Erdos–Ko–Rado theorem. Let a permutation ˝ 𝜎 of {0, … , n − 1} and i ∈ {0, … , n − 1} be chosen randomly, uniformly and independently and set A = {𝜎(i), 𝜎(i + 1), … , 𝜎(i + k − 1)}, addition again modulo n. Conditioning on any choice of 𝜎, the lemma gives Pr[A ∈ ] ≤ k∕n. Hence Pr[A ∈ ] ≤ k∕n. But A is uniformly chosen from all k-sets so k n ≥ Pr[A ∈ ] = || (n k ) and || ≤ k n (n k ) = (n − 1 k − 1 )
2 Linearity of Expectation The search for truth is more precious than its possession. -Albert Einstein 2.1 BASICS Let X.....X be random variables,X=c++cX Linearity of Expectation states that EX=c1EX】+…+C E[X]. The power of this principle comes from there being no restrictions on the dependence or independence of X.In many instances,E[X]can easily be calculated by ajudicious decomposition into simple(often indicator)random variables X.. Let o be a random permutation on (1.....n.uniformly chosen.Let X()be the EX=Pmo0=司=月 so that ic加ttd5Ea器o e e
2 Linearity of Expectation The search for truth is more precious than its possession. –Albert Einstein 2.1 BASICS Let X1, … , Xn be random variables, X = c1X1 +···+ cnXn. Linearity of Expectation states that E[X] = c1E[X1]+···+ cnE[Xn] . The power of this principle comes from there being no restrictions on the dependence or independence of Xi . In many instances, E[X] can easily be calculated by a judicious decomposition into simple (often indicator) random variables Xi. Let 𝜎 be a random permutation on {1, … , n}, uniformly chosen. Let X(𝜎) be the number of fixed points of 𝜎. To find E[X], we decompose X = X1 +···+ Xn, where Xi is the indicator random variable of the event 𝜎(i) = i. Then E[Xi ] = Pr[𝜎(i) = i] = 1 n so that E[X] = 1 n +···+ 1 n = 1 . The Probabilistic Method, Fourth Edition. Noga Alon and Joel H. Spencer. © 2016 John Wiley & Sons, Inc. Published 2016 by John Wiley & Sons, Inc
LINEARITY OF EXPECTATION In applications,we often use that there is a point in the probability space for which X>E[X]and a point for which X s E[X].We have selected results with a purpose of describing this basic methodology.The following result of Szele(1943)is oftentimes considered the first use of the probabilistic method. Theorem 2.1.1 There is a tournamentT with nplayers and at least n!Hamil tonian paths. Proof.In the random tournament,let Xbe the number of Hamiltonian paths.Foreach permutation o.let X be the indicator random variable for o giving a Hamiltonian path,that is,satisfying(c(⑦，o(i+l)∈Tfor1≤i<n.Then X=∑X。and E[X)=∑EXJ=n2-m- Thus some tournament has at least E[X]Hamiltonian paths. Szele conjectured that the maximum possible numbe of Hamiltonian path in a tour ment on n players is at most n!/(2-o(1))".This was proved in Alon (1990a)and is presented in"The Probabilistic Lens:Hamiltonian Paths"(following Chapter 4). 2.2 SPLITTING GRAPHS a graph with n vertices ande edges.Then G con Proof.LetT Vbe a random subset given by Prix T]=1/2,these choices being mutually independent.Set B=V-T.Call an edge (x,y)crossing if exactly one of x.y is in T.Let X be the number of crossing edges.We decompose X=∑X LryleE where is the indicator random variable for [x,y)being crossing.Then EX=方 as two fair coin flips have probability 1/2 of being different.Then EN=∑EKl=号 .y)EE Thusfor some choice of T.and the set of those crosing edges forms bipartite graph
20 LINEARITY OF EXPECTATION In applications, we often use that there is a point in the probability space for which X ≥ E[X] and a point for which X ≤ E[X]. We have selected results with a purpose of describing this basic methodology. The following result of Szele (1943) is oftentimes considered the first use of the probabilistic method. Theorem 2.1.1 There is a tournament T with n players and at least n!2−(n−1) Hamiltonian paths. Proof. In the random tournament,let X be the number of Hamiltonian paths. For each permutation 𝜎, let X𝜎 be the indicator random variable for 𝜎 giving a Hamiltonian path, that is, satisfying (𝜎(i), 𝜎(i + 1)) ∈ T for 1 ≤ i < n. Then X = ∑ X𝜎 and E[X] = ∑E[X𝜎] = n!2−(n−1) Thus some tournament has at least E[X] Hamiltonian paths. ◾ Szele conjectured that the maximum possible number of Hamiltonian paths in a tournament on n players is at most n!∕(2 − o(1))n. This was proved in Alon (1990a) and is presented in “The Probabilistic Lens: Hamiltonian Paths” (following Chapter 4). 2.2 SPLITTING GRAPHS Theorem 2.2.1 Let G = (V, E) be a graph with n vertices and e edges. Then G contains a bipartite subgraph with at least e∕2 edges. Proof. Let T ⊆ V be a random subset given by Pr[x ∈ T] = 1∕2, these choices being mutually independent. Set B = V − T. Call an edge {x, y} crossing if exactly one of x, y is in T. Let X be the number of crossing edges. We decompose X = ∑ {x,y}∈E Xxy , where Xxy is the indicator random variable for {x, y} being crossing. Then E[Xxy] = 1 2 as two fair coin flips have probability 1∕2 of being different. Then E[X] = ∑ {x,y}∈E E[Xxy] = e 2 . Thus X ≥ e∕2 for some choice of T, and the set of those crossing edges forms a bipartite graph. ◾
SPLITTING GRAPHS A more subtle probability space gives a small improvement(which is tight for complete graphs). Th s ande edges.then it contains a bipartite subgraph +I vertices and e edges,then it contains a biparnite subgraph with at least e(n 1)/2n I edges. Proof.When Ghas 2n vertices,let T be chosen uniformly from among all n-element subsets of V.Any edge (x.y)now has probability n/(2n-1)of being crossing,and the proof concludes as before.When G has 2n+1 vertices,choose T uniformly from among all n-element subsets of V,and the proof is similar. ■ Here is a more complicated example in which the choice of distribution requires a preliminary lemma.Let V=VIU...UVi.where the V;are disjoint sets of size n.Let h:V1)be a two-coloring of the k-sets.A k-set E is crossing if it contains precisely one point fromeach V.ForSV seth()).the sumover all k-sets Theorem 2.2.3 Suppose h(E)=+1for all crossing k-sets E.Then there is an S V for which IhSl≥ct Lemma 2.2.denote the set fal fp nts ha R abso ute value at mos coeficient 1.Then for allfP there exist p iP2…Px having If(P1,,PI≥ck Here,c is positive and independent off Proof.Set M=…P- Proof [Theorem 2.2.3].Define a randomSC V by setting PeS=px∈V, these choices being mutually independent,with p;to be determined.Set X=h(S). For each k-set E.set XE= h(E)if ECS. 10 otherwise
SPLITTING GRAPHS 21 A more subtle probability space gives a small improvement (which is tight for complete graphs). Theorem 2.2.2 If G has 2n vertices and e edges, then it contains a bipartite subgraph with at least en∕(2n − 1) edges. If G has 2n + 1 vertices and e edges, then it contains a bipartite subgraph with at least e(n + 1)∕2n + 1 edges. Proof. When G has 2n vertices, let T be chosen uniformly from among all n-element subsets of V. Any edge {x, y} now has probability n∕(2n − 1) of being crossing, and the proof concludes as before. When G has 2n + 1 vertices, choose T uniformly from among all n-element subsets of V, and the proof is similar. ◾ Here is a more complicated example in which the choice of distribution requires a preliminary lemma. Let V = V1 ∪···∪ Vk, where the Vi are disjoint sets of size n. Let h ∶ Vk → { ± 1} be a two-coloring of the k-sets. A k-set E is crossing if it contains precisely one point from each Vi . For S ⊆ V set h(S) = ∑ h(E), the sum over all k-sets E ⊆ S. Theorem 2.2.3 Suppose h(E)=+1 for all crossing k-sets E. Then there is an S ⊆ V for which |h(S)| ≥ cknk . Here, ck is a positive constant, independent of n. Lemma 2.2.4 Let Pk denote the set of all homogeneous polynomials f( p1, … , pk) of degree k with all coefficients having absolute value at most 1, and p1p2 ··· pk having coefficient 1. Then for all f ∈ Pk, there exist p1, … , pk ∈ [0, 1] with |f( p1, … , pk)| ≥ ck . Here, ck is positive and independent of f . Proof. Set M(f) = max p1,…,pk∈[0,1] |f( p1, … , pk)| . For f ∈ Pk, M(f) > 0 asf is not the zero polynomial. As Pk is compact and M ∶ Pk → R is continuous, M must assume its minimum ck. ◾ Proof [Theorem 2.2.3]. Define a random S ⊆ V by setting Pr[x ∈ S] = pi , x ∈ Vi , these choices being mutually independent, with pi to be determined. Set X = h(S). For each k-set E, set XE = { h(E) if E ⊆ S, 0 otherwise