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 exercis￾es 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 cov￾ers 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 dis￾cussed in Chapter 11, focusing on the behavior of the random graph near the emer￾gence of the giant component and briefly exploring its connection 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 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