The probabilistic Method Third Edition Noga Alon School of Mathematics Raymond and Beverly Sackler Faculty of Exact Sciences Tel Aviv University Joel H.Spencer WILEY A JOHN WILEY SONS,INC.,PUBLICATION
The Probabilistic Method Third Edition Noga Alón School of Mathematics Raymond and Beverly Sackler Faculty ofExact Sciences TelAviv University Joel H. Spencer Courant Institute of Mathematical Sciences New York University WILEY A JOHN WILEY & SONS, INC., PUBLICATION
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 impor- ant role of rando 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 dis- cussion 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 descrip- tion of the tools applied in probabilistic arguments,including the basic techniques that use expectation and variance,as well as the more recent applications of martin- one The second parndsdy ofaous tos have ben This part chapters on discrepancy and random graphs,as well as on several areas in theoretical com- puter science:circuit complexity,computational geometry,and derandomization of the heading The Probabilistic L 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 ap probability space and show that a ra hosen element in this 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, appropriate to call itThe Erdos Method.His contribution can be the area. It seems impossible to write an encyclopedic book on the Probabilistic Method; describe the ideas,and not always to give the best possible results if these are too
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
PREFACE technical to allow a clear presentation.Many of the results are asymptotic,and we ctions fandg,we writef(g)if cg for all sufficiently large values of the variables of the two functions,where c is an absolute positive constant.We write f=n(g)if g=O()and f=e(g)if f=O(g)and =(g).If the limit of the ratio f/g tends to zero as the variables ends with a list of exercises.The more difficult ones are marked by (*)The exercis- es enable readers to check their understanding of the material and also provide the possibility of using the book as a. This is the third edition of the book;it contains several improved results and cov- ers various additional topics that developed extensively during the last few years. The additions include a modern treatment of the Erdos-Renyi phase transition dis- cussed in Chapter 11,focusing on the behavior of the random graph near the emer- gence of the giant compone nt and briefly explo ing its conection to classical per colation theory.Another addition is Chapter 17,Graph Property Testing-a recent topic that combines combinatorial,probabilistic and algorithmic techniques.This chapter also includes a proof of the Regularity Lemma of Szemeredi(described in a language)and a preser at on of some of its applic tions in the area Further additions are two new Probabilistic Lenses.several additional exercises, and a new part in Appendix A focused on lower bounds. It is a special pleasure to thank our wives.Nurit and Mary Ann.Their patience. understanding and encouragement have been key ingredients in the success of this enterprise. NOGA ALON JOEL H.SPENCER
XÍV PREFACE technical to allow a clear presentation. Many of the results are asymptotic, and we use the standard asymptotic notation: for two functions/and g, we write/= 0(g) if f^cg for all sufficiently large valúes of the variables of the two functions, where c is an absolute positive constant. We write / = íl(g) if g = 0(f) and / = @(g) if / = 0{g) and / = íi(g). If the limit of the ratio f/g tends to zero as the variables of the functions tend to infinity we write / = o(g). Finally, f~g denotes that f = (1 + o(l))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 third edition of the book; it contains several improved results and covers various additional topics that developed extensively during the last few years. The additions include a modern treatment of the Erdós-Rényi phase transition discussed in Chapter 11, focusing on the behavior of the random graph near the emergence of the giant component and briefly exploring its connection to classical percolation theory. Another addition is Chapter 17, Graph Property Testing—a recent topic that combines combinatorial, probabilistic and algorithmic techniques. This chapter also includes a proof of the Regularity Lemma of Szemerédi (described in a probabilistic language) and a presentation of some of its applications in the área. Further additions are two new Probabilistic Lenses, several additional exercises, and a new part in Appendix A focused on lower bounds. It is a special pleasure to thank our wives, Nurit and Mary Ann. Their patience, understanding and encouragement have been key ingredients in the success of this enterprise. NOGA ALÓN JOEL H. SPENCER
Acknowledgments We are very grateful to all our students and colleagues who contributed to the cre- ons and useful com Sariel Har-Peled,Johan Hastad,Rani Hod,Mihyun Kang,Michael Krivelevich, Eyal Lubetzky,Russell Lyons,Nabil Mustafa,Nathan Linial,Yuval Peres,Xue Rui, Alexander Sapozhenko,Asaf Shapira,Aravind Srinivasan,Benny Sudakov,Prasad Tetali and William Wu,who pointed out various inaccuracies and misprints,and suggested improvements in the presentation as well as in the results.Needless to say,the responsibility for the remaining mistakes,as well as the responsibility for It is a pleasure to tha help in the preparation of the final manuscript for this book
Acknowledgments We are very grateful to all our students and colleagues who contributed to the creation of this third edition by joint research, helpful discussions and useful comments. These include Miklos Bona, Andrzej Dudek, Mathieu Dutour, Juliana Freiré, Sariel Har-Peled, Johan Hastad, Rani Hod, Mihyun Kang, Michael Krivelevich, Eyal Lubetzky, Russell Lyons, Nabil Mustafa, Nathan Linial, Yuval Peres, Xue Rui, Alexander Sapozhenko, Asaf Shapira, Aravind Srinivasan, Benny Sudakov, Prasad Tetali and William Wu, who pointed out various inaccuracies and misprints, and suggested improvements in the presentation as well as in the results. Needless to say, the responsibility for the remaining mistakes, as well as the responsibility for the (hopefully not many) new ones, is solely ours. It is a pleasure to thank Rani Hod and Eyal Lubetzky for their great technical help in the preparation of the final manuscript for this book. xv
Part I METHODS
Partí METHODS