You are here

Combinatorial Problems and Exercises

László Lovász
Publisher: 
AMS/Chelsea Publishing
Publication Date: 
2007
Number of Pages: 
639
Format: 
Hardcover
Edition: 
2
Price: 
69.00
ISBN: 
9780821842621
Category: 
Problem Book
BLL Rating: 

The Basic Library List Committee strongly recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Allen Stenger
, on
08/23/2007
]

This combinatorics problem book has a very strong emphasis on graph theory. Notable topics include the Brun and Selberg sieves in number theory (unfortunately without applications), Pólya-Redfield theory of counting under automorphism, Cayley's theorem on enumerating trees, Kuratowski's theorem on planar graphs, and van der Waerden's theorem on the existence of arithmetic progressions in sets. This is an unaltered 2007 reprint of the 2nd (1993) edition, with new errata sheets.

The book comprises three sections: problem statements, brief hints (usually a single sentence per problem), and complete solutions with references. The book starts out with traditional combinatorial subjects such as permutations, inclusion-exclusion, and generating functions, but quickly moves to graph theory. A number of additional combinatorial techniques are introduced in connection with the graph problems. The book is remarkable for the breadth of techniques (not just combinatorial) that it uses.

I adore problem books, but I am uneasy about this one because of its rapid pace, with very difficult theorems having only 3 or 4 problems leading up to them. I wonder how many students would really be able to use it as a problem book. My favorite problem book of all is Pólya and Szegö's Problems and Theorems in Analysis. I think they handle this building-up problem much better. For very difficult problems they build up through a long series of problems (as many as 20 or 30), and most of the intermediate problems are interesting in themselves.

It may be that the best use for this book is as an enrichment resource for the professor. He can select interesting problems from the book and provide additional hints as needed in class. The book would be especially valuable because it proves a number of famous results that everybody quotes but nobody proves, such as Kuratowski's and van der Waerden's theorems.


Allen Stenger is a math hobbyist, library propagandist, and retired computer programmer. He volunteers in his spare time at MathNerds.com, a math help site that fosters inquiry learning. His mathematical interests are number theory and classical analysis.