Preface The probabilistic method is one of the most powerful and widely used tools applied in entis the importan The s in theo between mathematicsan ence suggests an 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 e elation inequalities.The second part includes a s udy of various to s in es have cces sful This random grap s,as we on several ar oretical ompute Circuit Complexity,Cor Geometry,Graph Property Testing 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 ce of a comhinalorial structure with certain propertes,we construc w tha ta randomly ch t in this s desired prope es with whocontribu sitive pro ability.This ethod was initiated by Paul Erdos ted so mu o its development over a 50-year period that it seems appro priate to call it"The Erdos Method."His contribution can be measured not only by his numerous deep results in the subject but also by the many intriguing problems and conjectures posed by him that stimulated a big portion of the research in the area. 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 tryPreface 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 areas in theoretical computer science: Circuit Complexity, Computational Geometry, Graph Property Testing 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 appro￾priate 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 50-year period that it seems appro￾priate to call it “The Erdos Method.” His contribution can be measured not only by ˝ his numerous deep results in the subject but also by the many intriguing problems and conjectures posed by him that stimulated a big portion of the research in the area. 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