The probabilistic method. With an appendix on open problems by Paul Erdős. (English) Zbl 0767.05001

Wiley-Interscience Series in Discrete Mathematics and Optimization. New York: John Wiley & Sons. xiii, 254 p. (1992).
The probabilistic method, in its simplest form, refers to arguments in which one establishes the existence of combinatorial objects with certain properties by showing that objects in a suitable probability space have the desired properties with positive probability. The first part of this book discusses various techniques used in applying probabilistic arguments involving, for example, the first and second moments, the Lovász local lemma, martingales, correlation inequalities, and the Janson inequalities. The second part considers various areas in which probabilistic methods have proved useful such as the evolution of random graphs, circuit complexity, discrepancy, computational geometry, and codes and games; in particular, the authors describe certain algorithmic problems where the probabilistic method supplies effective randomized algorithms which, in some cases, can be derandomized and converted to deterministic algorithms. The bibliography contains some 140 references. Overall, the book provides a convincing demonstration of the power and versatility of probabilistic arguments.


05-02 Research exposition (monographs, survey articles) pertaining to combinatorics