《图论》课程教学资源（书籍文献）图论&概率方法阅读教材（The Probabilistic Method，Third Edition，Noga Alón，Joel H. Spencer）.pdf_大学文库

Preface The Probabilistic Method is one of the most powerful and widely used tools applied in combinatorics. One of the major reasons for its rapid development is the important role of randomness in theoretical computer science and in statistical physics. The interplay between discrete mathematics and computer science suggests an algorithmic point of view in the study of the probabilistic method in combinatorics and this is the approach we tried to adopt in this book. The book thus includes a discussion of algorithmic techniques together with a study of the classical method as well as the modern tools applied in it. The first part of the book contains a description of the tools applied in probabilistic arguments, including the basic techniques that use expectation and variance, as well as the more recent applications of martingales and correlation inequalities. The second part includes a study of various topics in which probabilistic techniques have been successful. This part contains chapters on discrepancy and random graphs, as well as on several áreas in theoretical computer science: circuit complexity, computational geometry, and derandomization of randomized algorithms. Scattered between the chapters are gems described under the heading The Probabilistic Lens. These are elegant proofs that are not necessarily related to the chapters after which they appear and can usually be read separately. The basic Probabilistic Method can be described as follows: In order to prove the existence of a combinatorial structure with certain properties, we construct an appropriate probability space and show that a randomly chosen element in this space has the desired properties with positive probability. This method was initiated by Paul Erdos, who contributed so much to its development over a fifty year period, that it seems appropriate to cali it "The Erdos Method." His cdntribution can be measured not only by his numerous deep results in the subject, but also by his many intriguing problems and conjectures that stimulated a big portion of the research in the área. It seems impossible to write an encyclopedic book on the Probabilistic Method; too many recent interesting results apply probabilistic arguments, and we do not even try to mention all of them. Our emphasis is on methodology, and we thus try to describe the ideas, and not always to give the best possible results if these are too xiii

2 THE BASIC METHOD 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 fixed et A be the event that the induced subgrap ofo R is monochromatic (i.e.,that either all its edges are red or they are all blue).Clearly, Pr[AR=2-().Since there are (possible choices for R.the probability that at least one of the events Ar occurs is at most ()1.Thus.with positive probability,no event AR occurs and there is a two-coloring of K without monochromatic K'k;that is,R(k,)>n.Note that if k 3 and we take n =2k/2 then (-2/2 for all k 3. ■ This simple example der strates the essence of the probabilistic method.To prove the existence of a good coloring we do not present one explicitly.but rather show,in a nonconstructive way.that it exists.This example appeared in a paper of P.Erdos from 1947.Although Szele had applied the probabilistic method to another combinatorial problem,me ntioned in Chapter 2,already in 1943,Erdos was cer understood the full power of ths method and over the vears to numerous problems.One can.of course.claim that the probability is not essential in the proof given above.An equally simple proof can be described by counting:we just check that the total number of two-colorings of K is larger than the number of those containing a m ochromatic Kk. Moreover.since the vast majority of the probability spaces considered in the study of combinatorial problems are finite spaces,this claim applies to most of the applications of the probabilistic method in discrete mathematics.Theoretically this 1S, indeed,the case. However,in practice,the probability is essential. It be hopeless to replace the applications of many of the tools appearing in this book including,for example,the second moment method,the Lovasz Local Lemma and the concentration via martingales by counting arguments,even when these are applied to finite probabil ity space The probabilistic method has an interesting algorithmic aspect.Consider,for example,the proof of Proposition 1.1.1 that shows that there is an edge two-coloring of K without a monochromatic K2 Can we actually find such a coloring? question,as asked,may so nd ridicul ossible coloring is finite,so we can try them all until we find the desired one. However,such a quiresteps;anamount of time that isexponential in the size he problm.Algorithms whosen m ismoreo the size of the problem are usually considered impractical.The class of problems that can be solved in polynomial time,usually denoted by P[see,e.g.,Aho,Hopcroft and Ullman (1974)1,is,in a sense.the class of all solvable problems.In this sense,the acceptable,and this is the reason for our remark that the proof of Proposition 1.1.1 is nonconstructive;it does not supply a constructive,efficient and deterministic way of

2 THE BASIC METHOD 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 fixed set i? of k vértices, let AR be the event that the induced subgraph of Kn on R is monochromatic (Le., that either all its edges are red or they are all blue). Clearly, Pr[^4ñ] = 21 -' - 2 '. Since there are (£) possible choices for R, the probability that at least one of the events AR occurs is at most (^)2l ~\2> n. Note that if k > 3 and we take n = |_2fc/ 2 J then / n \ i (k\ 21+i nk U > ía) |_2fc/ 2 J for all k > 3. • This simple example demonstrates the essence of the probabilistic method. To prove the existence of a good coloring we do not present one explicitly, but rather show, in a nonconstructive way, that it exists. This example appeared in a paper of P. Erdós from 1947. Although Szele had applied the probabilistic method to another combinatorial problem, mentioned in Chapter 2, already in 1943, Erdós was certainly the first one who understood the full power of this method and applied it successfully over the years to numerous problems. One can, of course, claim that the probability is not essential in the proof given above. An equally simple proof can be described by counting; we just check that the total number of two-colorings of Kn is larger than the number of those containing a monochromatic K¡-. Moreover, since the vast majority of the probability spaces considered in the study of combinatorial problems are finite spaces, this claim applies to most of the applications of the probabilistic method in discrete mathematics. Theoretically, this is, indeed, the case. However, in practice, the probability is essential. It would be hopeless to replace the applications of many of the tools appearing in this book, including, for example, the second moment method, the Lovász Local Lemma and the concentration via martingales by counting arguments, even when these are applied to finite probability spaces. The probabilistic method has an interesting algorithmic aspect. Consider, for example, the proof of Proposition 1.1.1 that shows that there is an edge two-coloring of Kn without a monochromatic i^2iog2n- Can we actually find such a coloring? This question, as asked, may sound ridiculous; the total number of possible colorings is finite, so we can try them all until we find the desired one. However, such a procedure may require 2\2> steps; an amount of time that is exponential in the size [= (2)] of the problem. Algorithms whose running time is more than polynomial in the size of the problem are usually considered impractical. The class of problems that can be solved in polynomial time, usually denoted by P [see, e.g., Aho, Hopcroft and Ullman (1974)], is, in a sense, the class of all solvable problems. In this sense, the exhaustive search approach suggested above for finding a good coloring of Kn is not acceptable, and this is the reason for our remark that the proof of Proposition 1.1.1 is nonconstructive; it does not supply a constructive, efficient and deterministic way of

GRAPH THEORY 3 producing a coloring with the desired properties.However,a closer look at the proof shows that,in fact,it can be used to produce,effectively,a coloring that is very likely to be good.This is because for then <1 Hence,a random coloring of K is very likely not to contain a monochromatic This means that if.for some reason,we must present a two-coloring edges of Kwithout a monochromatic K2o we can simply random two-coloring by flipping a fair coin()times We can the deliver the resulting coloring safely:the probability that it contains a monochromatic K2o is less than 211/20!,probably much smaller than our chances of making a mistake in any rigorous proof that a certain coloring is good!Therefore,in some cases the constructive method doe supply effective probabilistic algorithn Moreover,these algorithms can sometimes be converted into deterministic ones.This topic is discussed in some detail in Chapter 16. The probabilistic method is a powerful tool in Combinatorics and in Graph Theory. It is also extremely useful in Number Theory and in Combinatorial Geome has in the evelopment of effi nt algorithmic and in the study of various computational problems.In the rest of this chapter we present several simple examples that demonstrate some of the broad spectrum of topics in which this method is helpful.More compicated examples involving various more delicate probabilistic arguments,appear in the rest of the book 1.2 GRAPH THEORY A tournament on a set V of n players is an orientation T=(V,E)of the edges of the complete graph on the set of vertices V.Thus for every two distinct elementsx and y of V either(,y)or (y,is in E,but not both.The name"tournament"is natural, since one can think of the set V as a set of players in which each pair participates in asingle match,where(,y)is in the tourn ent iff beats y.We say that T has the property S if for every set of k players there is one who beats them all.For example,a directed triangle T3 =(V.E).where V=1,2,3)and E =(1,2),(2,3),(3,1), has S1.Is it true that for every finite k:there is a tournament T(on more than k vertices) with the property S?As s own by Erdos(1963b).this problem,raised by Schiitte can be solved almost trivially by applying probabilistic arguments.Moreover,these arguments even supply a rather sharp estimate for the minimum possible number of vertices in such a tournament The basic (and natural)idea is that if n is sufficiently large as a function ofk,then a random to nament on the set V={1,...,n}of n players is very likely to have property Sk.By a random tournament we mean here a tournament T'on V obtained by choosing,for each 1 i<j<n,independently, either the edge (ij)or the edge (j.i),where each of these two choices is equally likely.Observe that in this manner,all the 2()possible tournaments on V are

GRAPH THEORY 3 producing a coloring with the desired properties. However, a closer look at the proof shows that, in fact, it can be used to produce, effectively, a coloring that is very likely to be good. This is because for large k, if n = |_2fc/ 2 J then \k) S k\ ^ Henee, a random coloring of Kn is very likely not to contain a monochromatic •f^iogn- This means that if, for some reason, we must present a two-coloring of the edges of KW2i without a monochromatic K2o we can simply produce a random two-coloring by flipping a fair coin ( 2 ) times. We can then deliver the resulting coloring safely; the probability that it contains a monochromatic X20 is less than 211/20!, probably much smaller than our chances of making a mistake in any rigorous proof that a certain coloring is good! Therefore, in some cases the probabilistic, nonconstructive method does supply effective probabilistic algorithms. Moreover, these algorithms can sometimes be converted into deterministic ones. This topic is discussed in some detail in Chapter 16. The probabilistic method is a powerful tool in Combinatorics and in Graph Theory. It is also extremely useful in Number Theory and in Combinatorial Geometry. More recently, it has been applied in the development of efficient algorithmic techniques and in the study of various computational problems. In the rest of this chapter we present several simple examples that demónstrate some of the broad spectrum of topics in which this method is helpful. More complicated examples, involving various more delicate probabilistic arguments, appear in the rest of the book. 1.2 GRAPH THEORY A toumament on a set V of n players is an orientation T = (V, E) of the edges of the complete graph on the set of vértices V. Thus for every two distinct elements x and y of V either (x, y) or (y, x) is in E, but not both. The ñame "toumament" is natural, since one can think of the set Vas a set of players in which each pair participates in a single match, where (x, y) is in the toumament iff x beats y. We say that T has the property Su if for every set of/c players there is one who beats them all. For example, a directed triangle T3 = (V, E), where V = {1,2,3} and £ = {(1,2), (2,3), (3,1)}, has S\. Is it true that for every finite k there is a toumament T (on more than k vértices) with the property Sfc? As shown by Erdos (1963b), this problem, raised by Schütte, can be solved almost trivially by applying probabilistic arguments. Moreover, these arguments even supply a rather sharp estímate for the mínimum possible number of vértices in such a toumament. The basic (and natural) idea is that if n is sufficiently large as a function of k, then a random toumament on the set V = {1,... , n} of n players is very likely to have property Sk. By a random toumament we mean here a toumament T onV obtained by choosing, for each 1 < i < j < n, independently, either the edge (i,j) or the edge (j, i), where each of these two choices is equally likely. Observe that in this manner, all the 2^J possible toumaments on V are

GRAPH THEORY 5 if they are not independent)and since the random variable can be written as a sum of n indicator random variables xv(vE V).where xv=1 if v Y and X知 0 otherwise we conclude that the e expected value of is at mos 吧+n(1-p)+ ly,there is at least one choice of X V such that Yx<np+n(1-p)6+1.The set U=XUYx is clearly a dominating set of G whose cardinality is at most this size. The above argument works for any p[0,1].To optimize the result we use elementary calculus. For convenience we bound 1-p(this holds for all nonnegative p and is a fairly close bound when p is small)to give the simpler bound IU川≤np+ne-p(6+1) Take the derivative of the right-hand side with respect to p and set it equal to zero. The right-hand side is minimized at mf6+1 p= ò+1 Formally,we set p equal to this value in the first line of the proof.We now have UI<n1+In(+1)1/(6+1)as claimec Three simple but important ideas are incorporated in the last proof.The first is appear in Chapter The second is perhaps more subtle and is s an example e of the "alteration"principle that is discussed in Chapter 3.The random choice did not supply the required dominating set U immediately:it only supplied the set X,which has to be altered a little(by adding to it the set Yx)to provide the required dominating set.The third involves the optim oice of p. often wants to o make a random choice but is not certain what probability p should be used.The idea is to carry out the proof with p as a parameter giving a result that is a function of p.At the end,that p is selected which gives the optimal result.There is here yet a fourth idea that might be called asymptotic calculu We wanted the asymptotics where p ranges over 0,1].The actual minimum p =1-(6+1)- to deal with and in many similar cases precise minima are impossible to find in closed form.Rather,we give away a little bit,bounding 1-p e-p,yielding a clean bound.A good pa t of the eart of the probabilisti emethod lies in finding suboptimal but clean bounds.Did we give away too much in this case?The answer depends on the emphasis for the original question.For 6=3 our rough bound gives IU<0.596n while the more precise calculation gives U<0.496n,perhaps a substantial difference.For large both methods give as otically nIn/6 It can easily be deduced from the results in Alon (1990b)that the ound in Theorem 1.2.2 is nearly optimal.A non probabilistic,algorithmic proof of this theorem can be obtained by choosing the vertices for the dominating set one by one,when in each step a vertex that covers the maximum number of yet uncovered vertices is picke note by C(v)the set consisting of together with all its neighbors.Suppose that during the process of picking vertices

GRAPH THEORY 5 if they are not independent) and since the random variable \Y\ can be written as a sum of n indicator random variables \v (v & V), where \v = 1 if v € Y and Xv = 0 otherwise, we conclude that the expected valué of \X\ + \Y\ is at most np + n(\ — p)s+1 . Consequently, there is at least one choice oflc y such that \X\ + \Yx\ <np + n(l - p)s+1 . The set U = X U Yx is clearly a dominating set of G whose cardinality is at most this size. The above argument works for any p £ [0,1], To optimize the result we use elementary calculus. For convenience we bound 1 — p < e~ p (this holds for all nonnegative p and is a fairly cióse bound when p is small) to give the simpler bound \U\ < np + ne-^s+l) . Take the derivative of the right-hand side with respect to p and set it equal to zero. The right-hand side is minimized at ln(¿+l) Formally, we set p equal to this valué in the first line of the proof. We now have \U\ < n[l + ln(¿ + 1)]/(S + 1) as claimed. • Three simple but important ideas are incorporated in the last proof. The first is the linearity of expectation; many applications of this simple, yet powerful principie appear in Chapter 2. The second is perhaps more subtle and is an example of the "alteration" principie that is discussed in Chapter 3. The random choice did not supply the required dominating set U immediately; it only supplied the set X, which has to be altered a little (by adding to it the set Yx) to provide the required dominating set. The third involves the optimal choice of p. One often wants to make a random choice but is not certain what probability p should be used. The idea is to carry out the proof with p as a parameter giving a result that is a function of p. At the end, that p is selected which gives the optimal result. There is here yet a fourth idea that might be called asymptotic calculus. We wanted the asymptotics of min np + n( 1 — p)s+1 , where p ranges over [0,1]. The actual mínimum p = 1 - {8 + I)'1 / 5 is difficult to deal with and in many similar cases precise minima are impossible to find in closed form. Rather, we give away a little bit, bounding 1 — p < e~ p , yielding a clean bound. A good part of the art of the probabilistic method lies in finding suboptimal but clean bounds. Did we give away too much in this case? The answer depends on the emphasis for the original question. For 8 = 3 our rough bound gives \U\ < 0.596n while the more precise calculation gives \U\ < 0.496n, perhaps a substantial difference. For 8 large both methods give asymptotically n ln 8/5. It can easily be deduced from the results in Alón (1990b) that the bound in Theorem 1.2.2 is nearly optimal. A non probabilistic, algorithmic proof of this theorem can be obtained by choosing the vértices for the dominating set one by one, when in each step a vértex that covers the máximum number of yet uncovered vértices is picked. Indeed, for each vértex v denote by C(v) the set consisting of v together with all its neighbors. Suppose that during the process of picking vértices