The Probabilistic Method

This book is the leading reference on probabilistic methods in combinatorics, and there is no direct competition. The Probabilistic Method, Third Edition begins with basic techniques that use expectation and variance, as well as the more recent martingales and correlation inequalities, then explores areas where probabilistic techniques proved successful, including discrepancy and random graphs as well as cutting-edge topics in theoretical computer science. A series of proofs, or "probabilistic lenses," are interspersed throughout the book, offering added insight into the application of the probabilistic approach. The number of exercises included in the third edition has been almost doubled from that of the second edition, and hints and/or answers to some of the exercises are provided.