You are here

A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory

Miklós Bóna
Publisher: 
World Scientific
Publication Date: 
2006
Number of Pages: 
469
Format: 
Paperback
Edition: 
2
Price: 
59.00
ISBN: 
9789812568861
Category: 
Textbook
BLL Rating: 

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

[Reviewed by
Christopher Hanusa
, on
01/30/2009
]

Bóna’s A Walk Through Combinatorics achieves its goal of bringing together many ideas in combinatorics in an accessible way. Undergraduates are shown the basics and then are presented topics that bring active areas of combinatorial research to their fingertips.

The book is broken down into four parts: basic methods, enumerative combinatorics, graph theory, and advanced topics; there is more than enough material in the eighteen chapters for two semesters of discrete mathematics courses. The topics are chosen for breadth without sacrificing depth — it is nice to see complete chapters on generating functions, the probabilistic method, and permutation pattern avoidance.

The final two chapters are on algorithms and computational complexity. These are important topics to cover as many math majors are not given this insight into theoretical computer science. Unfortunately, these last two sections of the book are written much less intuitively than the other sections.

The reviewer also wishes there were more guidance to new instructors on how to choose topics for a one-semester course. The variety of subjects presented allows a more seasoned instructor to vary the topics taught.

My few criticisms, however, are overshadowed by the clarity and accessibility of most of the chapters. Sections start with a motivating intuitive premise that sets the tone. For example, the section on permutations starts with n patients arriving at a dentist’s office at the same time and needing to be seen; the section on matchings in bipartite graphs starts with the concrete example of m job openings and n applicants. Bóna leads the reader through the subjects by way of examples, which helps the student to develop the ever-important “intuition” needed for combinatorial reasoning. The book is easy to read and follow, and has a feel of a guided tour.

An extremely positive part of the book is the organization of each chapter’s examples and problems. At the end of each chapter there is a set of worked exercises and a set of (unworked) supplementary exercises. In contrast to the examples in the sections that are explained thoroughly, the solutions to the worked exercises are written concisely, so even if a student were to flip directly to the solution, a revisiting of the course material would be necessary to comprehend the written solutions. When learning from this book, the solutions to the worked exercises should be treated as part of the chapters, because it appears that hints and guidance for solving problems sometimes only occur in these solutions. An instructor would need to account for this and find some way to work the solved problems explicitly into the course structure.

It appears that a course taught from A Walk Through Combinatorics would be pleasant to take and pleasant to teach; the reviewer is looking forward to teaching a course out of this book in the near future.


Christopher Hanusa is an assistant professor of mathematics at Queens College, part of the City University of New York.

 

  •  
  • Basic Methods: 
  • Seven Is More Than Six. The Pigeon-Hole Principle
  • One Step at a Time. The Method of Mathematical Induction
  • Enumerative Combinatorics: 
  • There Are a Lot of Them. Elementary Counting Problems
  • No Matter How You Slice It. The Binomial Theorem and Related Identities
  • Divide and Conquer. Partitions
  • Not So Vicious Cycles. Cycles in Permutations
  • You Shall Not Overcount. The Sieve
  • A Function is Worth Many Numbers. Generating Functions
  • Graph Theory: 
  • Dots and Lines. The Origins of Graph Theory
  • Staying Connected. Trees
  • Finding a Good Match. Coloring and Matching
  • Do Not Cross. Planar Graphs
  • Horizons: 
  • Does It Clique? Ramsey Theory
  • So Hard to Avoid. Subsequence Conditions on Permutations
  • Who Knows What It Looks Like, but It Exists. The Probabilistic Method
  • At Least Some Order. Partial Orders and Lattices
  • The Sooner The Better. Combinatorial Algorithms
  • Does Many Mean More Than One? Computational Complexity