xiv PREFACE 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 technical to allow a clear presentation.Many of the results are asymptotic,and we use the standard asymptotic notation:for two functions f and g,we write f=O(g)iff scg for all sufficiently large values of the variables of the two functions,where c is an absolute positive constant.We write f=(g)if g=o(f)and f=e(g)if f =O(g) andf=().If the limit of the ratiof/g tends to roas the variables of the function tend to in y we writef=o(g).Fina g denotes thatf=(1+(1)g:that f/g tends to I when the variables tend to infinity.Each chapter ends with a list of exercises.The more difficult ones are marked by (*)The exercises enable readers to check their understanding of the material and also provide the possibility of using the book as a textbook. This is the fourth edition of the book;it contains several improved results and covers various additional topics that developed extensively during the last few years. A breakthrough approach to the Local Lemma is described in Chapter 5.A new algorithmic sented app ach to the"six standard deviations"result in disc oter 12.A novel proof for the study of Property B.ba ed o oring.appears in Chapter 3.In all the above ses,the algorith mic proofs provide essentially new arguments for the existence of the desired objects A new,short section on graph limits has been added to Chapter 9.A technique for counting independent sets in graphs and its application in a graph coloring problem is described in Chapter 1.Further additions include a new Probabilistic Lens,several additional exercises,and a new appendix with hints to selected exercises. As in the previous editions,it is a special pleasure to thank our wives.Nurit and Mary Ann.Their patience,understanding,and encouragement have been key ingre dients in the success of this enterprise. oga Alor JoelH.Spencer Tel Aviv and New York,2015 xiv PREFACE 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 technical to allow a clear presentation. Many of the results are asymptotic, and we use the standard asymptotic notation: for two functions f and g, we write f = O(g) if f ≤ cg for all sufficiently large values of the variables of the two functions, where c is an absolute positive constant. We write f = Ω(g) if g = O(f) and f = Θ(g) if f = O(g) and f = Ω(g). If the limit of the ratio f ∕g tends to zero as the variables of the functions tend to infinity we write f = o(g). Finally, f ∼ g denotes that f = (1 + o(1))g; that is, f ∕g tends to 1 when the variables tend to infinity. Each chapter ends with a list of exercises. The more difficult ones are marked by (∗). The exercises enable readers to check their understanding of the material and also provide the possibility of using the book as a textbook. This is the fourth edition of the book; it contains several improved results and covers various additional topics that developed extensively during the last few years. A breakthrough approach to the Local Lemma is described in Chapter 5. A new algorithmic approach to the “six standard deviations” result in discrepancy theory is presented in Chapter 12. A novel proof for the study of Property B, based on a random greedy coloring, appears in Chapter 3. In all the above cases, the algorith￾mic proofs provide essentially new arguments for the existence of the desired objects. A new, short section on graph limits has been added to Chapter 9. A technique for counting independent sets in graphs and its application in a graph coloring problem is described in Chapter 1. Further additions include a new Probabilistic Lens, several additional exercises, and a new appendix with hints to selected exercises. As in the previous editions, it is a special pleasure to thank our wives, Nurit and Mary Ann. Their patience, understanding, and encouragement have been key ingre￾dients in the success of this enterprise. Noga Alon Joel H. Spencer Tel Aviv and New York, 2015