CS3150 - Homework — Chapter 6 ( 6.14 )∗Dan Li, Xiaohui Kong †, Hammad Ibqal and Ihsan A. QaziDepartment of Computer Science, University of Pittsburgh, Pittsburgh, PA 15260† Intelligent Systems Program, University of Pittsburgh, Pittsburgh, PA 15260February 4, 2006Contents1 Problem 6.2 22 Problem 6.14 33 Problem 6.16 4∗This was written by Dan Li11 PROBLEM 6.21 Problem 6.2(a) Prove that for every integer n, there exists a coloring of the edges of the complete graph Knby twocolors so that the total number of monochromatic copies of Kais at mistn42−5.(b) Give a randomized algorithm for finding a coloring with at mostn42−5monochromatic copies of K4that runs in expected time polynomial in n.(c) Show how to construct such a coloring deterministically in polynomial time using the methods of con-ditional expectations.Proof:(a) Each edge has 1/2 probablity to be colored in each of the two colors. There are 6 edges in each K4, sothe probability that a K4is monochromatic is 2·126= 2−5.The expected number of monochromatic K4is thusn4· 2−5, so that there exists such coloring suchthat the number of monochromatic K4is at mostn42−5.(b) By fliping a coin, if it is head, we use color 1, otherwise we use color 2. Assuming we haveprobability p to get such a coloring, then:n42−5≥ (1− p)(n42−5+ 1)So,1− p ≤n4/32n4/32+ 1p ≥ 1−n4/32n4/32+ 1=1n4/32+ 1(1)Simply repeat the process, with success probability of p. The expected number of trials before asuccess is thus 1/p, where1p=n4/32+ 1 = 1+ O(n4) = O(n4) (2)(c)22 PROBLEM 6.142 Problem 6.14Consider a graph in Gn,p, with p = 1/n. Let X be the number of triangles in the graph, where a triangle isa clique with tjree edeges. Show thatPr(X ≥ 1) ≤ 1/6and thatlimn→∞Pr(X ≥ 1) ≥ 1/7 (3)( it Hint: Use the conditional expecation inequality.Proof:By using the conditional expectation inequality, we havePr(X ≥ 1) = Pr(X > 0) =(n3)∑i=1Pr(Xi= 1)E[X|Xi= 1](4)For any triangle, Pr(Xi= 1) = p3, andE[X|Xi= 1] = 1+n− 33p3+n− 32p3+n− 31p2(5)So,Pr(X ≥ 1) =(n3)∑i=1p31+n−33p3+n−32p3+n−31p2=n3p31+n−33p3+n−32Pp3+n−31p2≤n3p3≤n36p3(6)Since p = 1/n, we have Pr(X ≥ 1) ≤ (n3p3)/6.33 PROBLEM 6.16We also have:limn→∞Pr(X ≥ 1) = limn→∞n3p31+n−33p3+n−32p3+n−31p2= limn→∞n3/n31+n−33/n3+n−32/n3+n−31/n3= limn→∞n(n− 1)(n− 2)/(6n3)1+ (n− 3)(n− 4)(n− 5)/(6n3) + (n− 3)(n− 4)/(2n3) + (n− 3)/n3= limn→∞1/61+ 1/6+ 0+ 0=1/67/6=17(7)3 Problem 6.16Use the lovatz local lemma to show that if4k2nk− 221−(k2)≤ 1 (8)then it is possible to color the edges of Knwith two colors so that is has no monochromatic Kksubgraph.Proof:Using lovatz local lemma, we need to 4dp ≤ 1.Define the events set E asE = {Ei| Ei∈ Kk,Eiis monochromatic} (9)By fliping coins, we can color the graph with two colors, each color has the same probability of 1/2.The probability for each Eiis thus 2· (12)(k2)= 21−(k2), since there arek2edges in each Kk.Next we need to prove that d =k2nk−2.Two Kkare dependent means they should have at least two common edges, or say three commonvertices. To bound the degree of dependence, we do the following. Choose one edge from the current Kk,choose one or more vertices from this Kk, and the rest from all vertices not in this Kk. Any such a selectionis an instance of choose k− 2 vertices from all the n vertices. So the degree of dependence is bounded byd =k2nk− 2(10)We have 4dp ≤ 1, so we havePr(n[i=1¯Ei) > 0 (11)43 PROBLEM 6.16which means that it is possible to color the graph wuch that neither Kkis monochromatic.For any one Kk, to construct a graph which is dependent on it, we can choose 2 vertices from thisgraph, and the rest from all vertices which are not in this Kk. Any such an instance must be an
View Full Document
Unlocking...