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 tooPreface 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￾tant 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 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￾gales 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 com￾puter 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 ap￾propriate 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