Probalistic Method, The

This book is the leading reference on probabilistic methods in combinatorics, and there is no direct competition. New to the Third Edition is a chapter devoted to Graph Property Testing and the included sections are Graph Property Testing; Testing Colorability; Szemeredi's Regularity Lemma; Testing Triangle-Freeness; and Characterizing the Testable Graph Properties. New sections have also been added on Percolation, Webgraphs, and Chernoff Bounds. A substantial revision has been made to the Double Jump section. 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.