EXERCISES 27 so for some choice ofe,∈(0，l, Iws2<lw2+p,(1-p)lv As this holds for all 1 ss sn(taking wo=0),the final w.P≤∑p-pleP While the proofs appear similar,a direct implementation of the proof of Theorem 2.4.2 to find e.....e might take an exhaustive search with expo- nential time.In applying the greedy algorithm at the sth stage,one makes two calculations of w,2,depending on whethere.=0 or 1,and picks that e.giving the smaller value.Hence there are only a linear number of calculations of norms to be entire algo ratic time.In Chapter 16.we discuss 2.7 EXERCISES 1.Suppose 22 edges.Show uniorm hypergraph with E=4-1 ow that thereisa coloring of by four colors so that no edge is monochromatic 2.Prove that there is a positive constant c so that every set A of n nonzero reals contains a subset B CA of size B]2 cn.so that there are no bb2.b3.bEB satisfying b1+2b2=2b3+2b4 3.Prove that every set of n nonzero real numbers contains a subset A of strictly more than n/3 numbers such that there are no.A satisfying+=a 4.Supposep>n>10m2,with pprime,and let0<a<d.<<am<pbe inte gers.Prove that there is an integerx,0<x<p,for which the m numbers (xa;(modp)modn,1≤i≤m are pairwise distinct. 5.Let H be a graph,and let n>V(H)I be an integer.Supp bose there is a granh on n vertices and t edges containing no copy of H,and su Show that there is a coloring of the edge kcolors with no monochromatic copy of H. 6.()Prove,using the technique in the probabilistic lens on Hamiltonian paths,that there is a constant c>0 such that for every even n24 the following holds:for every undirected complete graphK onn vertices whose edges are colored red and
EXERCISES 27 so for some choice of 𝜖s ∈ {0, 1}, |𝑤s| 2 ≤ |𝑤s−1| 2 + ps(1 − ps)|𝑣s| 2 . As this holds for all 1 ≤ s ≤ n (taking 𝑤0 = 0), the final |𝑤n| 2 ≤ ∑n i=1 pi(1 − pi )|𝑣i | 2 . While the proofs appear similar, a direct implementation of the proof of Theorem 2.4.2 to find 𝜖1, … , 𝜖n might take an exhaustive search with exponential time. In applying the greedy algorithm at the sth stage, one makes two calculations of |𝑤s| 2, depending on whether 𝜖s = 0 or 1, and picks that 𝜖s giving the smaller value. Hence there are only a linear number of calculations of norms to be made, and the entire algorithm takes only quadratic time. In Chapter 16, we discuss several similar examples in a more general setting. 2.7 EXERCISES 1. Suppose n ≥ 2 and let H = (V, E) be an n-uniform hypergraph with |E| = 4n−1 edges. Show that there is a coloring of V by four colors so that no edge is monochromatic. 2. Prove that there is a positive constant c so that every set A of n nonzero reals contains a subset B ⊂ A of size |B| ≥ cn, so that there are no b1, b2, b3, b4 ∈ B satisfying b1 + 2b2 = 2b3 + 2b4 . 3. Prove that every set of n nonzero real numbers contains a subset A of strictly more than n∕3 numbers such that there are no a1, a2, a3 ∈ A satisfying a1 + a2 = a3. 4. Suppose p > n > 10m2, with p prime, and let 0 < a1 < a2, < ··· < am < p be integers. Prove that there is an integer x, 0 < x < p, for which the m numbers (xai (mod p)) mod n, 1 ≤ i ≤ m are pairwise distinct. 5. Let H be a graph, and let n > |V(H)| be an integer. Suppose there is a graph on n vertices and t edges containing no copy of H, and suppose that tk > n2 log en. Show that there is a coloring of the edges of the complete graph on n vertices by k colors with no monochromatic copy of H. 6. ( ∗) Prove, using the technique in the probabilistic lens on Hamiltonian paths, that there is a constant c > 0 such that for every even n ≥ 4 the following holds: for every undirected complete graph K on n vertices whose edges are colored red and
LINEARITY OF EXPECTATION blue,the number of alternating Hamilton cycles in K(i.e.,properly edge-colored cycles of length n)is at most 7.Let F be a family of subsets of N=(1.2.....n).and suppose there are no A,B F satisfying A C B.Let oeS be a random permutation of the elements of N. and consider the random variable X=Ii:{σ(1)，a(2).…,o(01∈Fl By consideringtheexpecaionof,prove that≤（ta/月） n 8.()Let be a collection of pairwise orthogonal unit vectors in R",and suppose the projection of each of these vectors on the first k coordinates is of Euclidean norm at least e.Show that XIsk/e2,and this is tight for all e2=k/2<1. 9.Let G=(V.E)be a bipartite graph with n vertices and a list S(v)of more than each that there is a proper col
28 LINEARITY OF EXPECTATION blue, the number of alternating Hamilton cycles in K (i.e., properly edge-colored cycles of length n) is at most nc n! 2n . 7. Let be a family of subsets of N = {1, 2, … , n}, and suppose there are no A, B ∈ satisfying A ⊂ B. Let 𝜎 ∈ Sn be a random permutation of the elements of N, and consider the random variable X = |{i ∶ {𝜎(1), 𝜎(2), … , 𝜎(i)} ∈ }| . By considering the expectation of X, prove that || ≤ ( n ⌊n∕2⌋ ) . 8. (*) Let X be a collection of pairwise orthogonal unit vectors in Rn, and suppose the projection of each of these vectors on the first k coordinates is of Euclidean norm at least 𝜖. Show that |X| ≤ k∕𝜖2, and this is tight for all 𝜖2 = k∕2r < 1. 9. Let G = (V, E) be a bipartite graph with n vertices and a list S(𝑣) of more than log 2n colors associated with each vertex 𝑣 ∈ V. Prove that there is a proper coloring of G assigning to each vertex 𝑣 a color from its list S(𝑣)
THE PROBABILISTIC LENS: Bregman's Theorem LetA=[al be an n x n matrix with all a∈{0，l.Letr:=∑be the number of I's in the ith row.Let S be the set of permutationsoS witha=I for I sis n.Then the permanent per(A)is simply S].The following result was conjectured by Minc and proved by Bregman(1973).The proof presented here is similar to that of Schrijver(1978). Theorem 1 [Bregman's Theorem]per(A)≤Ⅱ(r,i. PickS andrS independently and uniformly.SetA)=A.Let R be the number of I's in row rl in A().Delete row rl and column orl fromA()to giveA(2). In general,let A(i denote A with rows r1,...,r(i-1)and columnsorl,....r(i-1) deleted and let R.denote the number of I's of row ri in A(.(This is nonzero as the arith column has a 1.)Set L=(a,t)=∏Ri I≤i≤n We think,roughly.of Las Lazyman's permanent calculation.There are R choices fora I in rowr1,each of which leads to a different subpermanent calculation.Instead, Lazyman takes the factor R.,takes the one from permutation o,and examines A(2) As a e s is chosen uniformly.Lazyman tends toward the high subpermanents and so it should not he s prising that he tends to over stimate the pe anent.To make this precise.w mean G].If takes values etyo pectaio tmtr fapructbin the product of the geometric means. Claim1 per(A)≤G[g
THE PROBABILISTIC LENS: Brégman’s Theorem Let A = [aij] be an n × n matrix with all aij ∈ {0, 1}. Letri = ∑ 1≤j≤naij be the number of 1’s in the ith row. Let S be the set of permutations 𝜎 ∈ Sn with ai,𝜎i = 1 for 1 ≤ i ≤ n. Then the permanent per(A) is simply |S|. The following result was conjectured by Minc and proved by Brégman (1973). The proof presented here is similar to that of Schrijver (1978). Theorem 1 [Brégman’s Theorem] per(A) ≤ ∏ 1≤i≤n (ri!) 1∕ri . Pick 𝜎 ∈ S and 𝜏 ∈ Sn independently and uniformly. Set A(1) = A. Let R𝜏1 be the number of 1’s in row 𝜏1 in A(1) . Delete row 𝜏1 and column 𝜎𝜏1 from A(1) to give A(2) . In general, let A(i) denote A with rows 𝜏1, … , 𝜏(i − 1) and columns 𝜎𝜏1, … , 𝜎𝜏(i − 1) deleted and let R𝜏i denote the number of 1’s of row 𝜏i in A(i) . (This is nonzero as the 𝜎𝜏ith column has a 1.) Set L = L(𝜎, 𝜏) = ∏ 1≤i≤n R𝜏i . We think, roughly, of L as Lazyman’s permanent calculation. There are R𝜏1 choices for a 1 in row 𝜏1, each of which leads to a different subpermanent calculation. Instead, Lazyman takes the factor R𝜏1, takes the one from permutation 𝜎, and examines A(2) . As 𝜎 ∈ S is chosen uniformly, Lazyman tends toward the high subpermanents and so it should not be surprising that he tends to overestimate the permanent. To make this precise, we define the geometric mean G[Y]. If Y > 0 takes values a1, … , as with probabilities p1, … , ps, respectively, then G[Y] = ∏ a pi i . Equivalently, G[Y] = eE[ln Y] . Linearity of Expectation translates into the geometric mean of a product being the product of the geometric means. Claim 1 per(A) ≤ G[L]
30 THE PROBABILISTIC LENS:BREGMAN'S THEOREM Proof.We show this for any fixed r.Set=1 for convenience of notation.We use induction on the size of the matrix.Reorder,for convenience,so that the first row has I's in the first r columns,where r=r.For I sjsr,let t;be the permanent of A with the first row and jth column removed or,equivalently,the number ofo S with al=j.Set 1=++ so that per(A)=rt.Conditioning on ol =j.R2...R is Lazyman's calculation of per(A).where A)is A with the first row and jth column removed.By induction. GR2…Rnlo1=1≥ and so G0≥1/w=ri mm2(g）之 Proof.Taking logarithms,this is equivalent to which follows from the convexity of the function f()=xIn x. Applying the lemma. GU≥rI≥rM=n=perA reorder so that all i.and assume that the first row has I's in precis r columns.With r selected uniformly,the columns 1.....are deleted in a random order uniform over all r!possibilities.R is the number of those columns remaining when the first column is to be deleted.As the first column is equally likely to be in any position among those r columns,R is uniformly distributed from I to r and G[R ]=(r!)/n."Linearity"then gives a4=cI风-1cR1=Ⅱw% The overall G[L]is the geometric mean of the conditional G[L]and hence has the same value.That is perA≤G☑=ΠG
30 THE PROBABILISTIC LENS: BRÉGMAN’S THEOREM Proof. We show this for any fixed 𝜏. Set 𝜏1 = 1 for convenience of notation. We use induction on the size of the matrix. Reorder, for convenience, so that the first row has 1’s in the first r columns, where r = r1. For 1 ≤ j ≤ r, let tj be the permanent of A with the first row and jth column removed or, equivalently, the number of 𝜎 ∈ S with 𝜎1 = j. Set t = t1 +···+ tr r so that per(A) = rt. Conditioning on 𝜎1 = j, R2 ··· Rn is Lazyman’s calculation of per(A(2) ), where A(2) is A with the first row and jth column removed. By induction, G[R2 ··· Rn|𝜎1 = j] ≥ tj and so G[L] ≥ ∏r j=1 (rtj) tj∕ per(A) = r ∏r j=1 t tj∕rt j . ◾ Lemma 2 ( ∏r j=1 t tj j )1∕r ≥ t t . Proof. Taking logarithms, this is equivalent to 1 r ∑r j=1 tj ln tj ≥ t ln t , which follows from the convexity of the function f(x) = x ln x. ◾ Applying the lemma, G[L] ≥ r ∏r j=1 t tj∕rt j ≥ r(t t ) 1∕t = rt = per(A) . ◾ Now we calculate G[L] conditional on a fixed 𝜎. For convenience of notation, reorder so that 𝜎i = i, all i, and assume that the first row has 1’s in precisely the first r1 columns. With 𝜏 selected uniformly, the columns 1, … ,r1 are deleted in a random order uniform over all r1! possibilities. R1 is the number of those columns remaining when the first column is to be deleted. As the first column is equally likely to be in any position among those r1 columns, R1 is uniformly distributed from 1 to r1 and G[R1]=(r1!) 1∕r1 . “Linearity” then gives G[L] = G [ ∏n i=1 Ri ] = ∏n i=1 G[Ri ] = ∏n i=1 (ri!) 1∕ri . The overall G[L] is the geometric mean of the conditional G[L] and hence has the same value. That is, per(A) ≤ G[L] = ∏n i=1 (ri !) 1∕ri
3 Alterations Beauty is the first test:there is no permanent place in the world for ugly mathematics. -G.H.Hardy The basic probabilistic method was described in Chapter 1 as follows:trying to e of struc ce with po e pro nthis chapter weco ns wher thall alteration.we remove the blemishes.givin hee the es not have all the desire structure. 3.1 RAMSEY NUMBERS Recall from Section 1.1 that R(k,)>nmeans there existsa two-coloring of the edges of K by red and blue so that there is neither a red K nor a blue Ki. Theorem31 Forany integer元k,k>n-(g）2-() Proof.Consider a random two-coloring of the edges of K obtained by coloring each edge independently either red or blue,where each color is equally likely.For any set R of k vertices,let Xg be the indicator random variable for the event for which the induced subgraph of K on R is monochromatic.Set X=Xg.the sum over all 0en Publae0 Wlye
3 Alterations Beauty is the first test: there is no permanent place in the world for ugly mathematics. –G. H. Hardy The basic probabilistic method was described in Chapter 1 as follows: trying to prove that a structure with certain desired properties exists, one defines an appropriate probability space of structures and then shows that the desired properties hold in this space with positive probability. In this chapter we consider situations where the “random” structure does not have all the desired properties but may have a few “blemishes.” With a small alteration, we remove the blemishes, giving the desired structure. 3.1 RAMSEY NUMBERS Recall from Section 1.1 that R(k, l) > n means there exists a two-coloring of the edges of Kn by red and blue so that there is neither a red Kk nor a blue Kl. Theorem 3.1.1 For any integer n, R(k, k) > n − (n k ) 2 1− ( k 2 ) . Proof. Consider a random two-coloring of the edges of Kn obtained by coloring each edge independently either red or blue, where each color is equally likely. For any set R of k vertices, let XR be the indicator random variable for the event for which the induced subgraph of Kn on R is monochromatic. Set X = ∑ XR, the sum over all The Probabilistic Method, Fourth Edition. Noga Alon and Joel H. Spencer. © 2016 John Wiley & Sons, Inc. Published 2016 by John Wiley & Sons, Inc