You are here

The Probabilistic Method

Noga Alon and Joel H. Spencer
John Wiley
Publication Date: 
Number of Pages: 
[Reviewed by
Miklós Bóna
, on

Researchers of any kind of extremal combinatorics or theoretical computer science will welcome the new edition of this book. The authors' goal with the new edition is clearly to keep up with new developments of this very rapidly developing field.

This ambitious goal is achieved through two new chapters, one on the Erdős-Rényi phase transition, and one on graph property testing. The latter contains some relatively accessible applications of the powerful Szemerédi Regularity Lemma. Other new topics include half-liar games and percolation.

While most combinatorialists are at least somewhat familiar with earlier editions of this book, this reviewer belongs to the smaller group of instructors who has actually taught a class using this book, and will do so again, so I will comment on that aspect as well.

The book has two main parts, Methods and Topics. There is way too much material for one course, so the instructor needs to make a decision as to how much of the methods to cover before jumping to topics. Selecting half of both parts is ambitious, but doable.

The book is primarily a reference book, not a textbook, so there are not too many exercises, and a large proportion of the existing exercises are too hard for the overwhelming majority of students. This did not change from earlier editions. Therefore, student work in the class should not be based on assigning homework from the book, but on presenting papers related to the material covered.

Miklós Bóna is Associate Professor of Mathematics at the University of Florida.

The table of contents is not available.