You are here

Extremal Combinatorics

Stasys Jukna
Publication Date: 
Number of Pages: 
[Reviewed by
Miklós Bóna
, on

This is an entertaining and impressive book. I say impressive because the author managed to cover a very large part of combinatorics in 27 short chapters, without assuming any graduate-level knowledge of the material. Each chapter focuses on a proof technique, and presents that proof technique with some of the most spectacular examples available. Because this is a problem-oriented book, there is relatively little elaboration between the theorems, but the examples are so well-chosen that the reader will not really mind. Another impressive feat is that the chapters are almost completely self-contained, so you can skip any number of them, and then continue reading without missing the skipped chapters.

The collection of topics covered is another big advantage of the book. In addition to the expected areas, such as extremal set theory, coding theory, Ramsey theory and the probabilistic method, we find more surprising (but welcome) subjects such as random walks, spectral graph theory, matchings in bipartite graphs, and communication complexity. Three of these chapters are new to the second edition: on error-correcting codes, on expander graphs and eigenvalues, and on the polynomial method. Other chapters also have been extended and updated.

There are about ten exercises per chapter. A few have hints, but none come with full solutions. The book is ideal as reference material or for a reading course for a dedicated graduate student. One could teach a very enjoyable class from it as well, just one would have to make a lot of choices as to what to include and what to skip, since there is too much here for a single class. And if you start reading the book somewhere, you risk spending your night studying it before putting it down.

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