zbMATH — the first resource for mathematics

The probabilistic method. With an appendix on the life and work of Paul Erdős. 3rd ed. (English) Zbl 1148.05001
Wiley-Interscience Series in Discrete Mathematics and Optimization. Hoboken, NJ: John Wiley & Sons (ISBN 978-0-470-17020-5/hbk). xv, 352 p. (2008).
The first and second editions of this book were published in 1992 and 2000 and were reviewed in Zbl 0767.05001 and Zbl 0996.05001. This third edition is about 50 pages longer and has about 40 more references than the second edition. There is a new chapter on the Erdős-Rényi phase transition concerning the behavior of the random graph near the emergence of the giant component that contains a section on analogies to percolation theory. There is also a new chapter on graph property testing that includes a proof of Szemeredi’s regularity lemma. The chapter on Codes, Games and Entropy contains a new section on a Half Liar Game; and the appendix contains a new section on lower bounds for large deviation probabilities. The book provides an up-to-date survey of the application of numerous types of probabilistic arguments to problems of a combinatorial nature that arise in diverse fields.

05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
Biographic References:
Erdős, Paul