Ebook: The Probabilistic Method

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 modem treatment of the Erdos-Renyi 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 Szemeredi (described in a probabilistic language) and a presentation of some of its applications in the area. Further additions are two new Probabilistic Lenses, several additional exercises, and a new part in Appendix A focused on lower bounds.