on February 5, 2002
Combinatorics is an area of mathematics that is frequently looked on as one that is reserved for a small minority of mathematicians: die-hard individualists who shun the limelight and take on problems that most would find boring. In addition, it has been viewed as a part of mathematics that has not followed the trend toward axiomatization that has dominated mathematics in the last 150 years. It is however also a field that has taken on enormous importance in recent years do its applicability in network engineering, combinatorial optimization, coding theory, cryptography, integer programming, constraint satisfaction, and computational biology. In the study of toric varieties in algebraic geometry, combinatorics has had a tremendous influence. Indeed combinatorial constructions have helped give a wide variety of concrete examples of algebraic varieties in algebraic geometry, giving beginning students in this area much needed intuition and understanding. It is the the advent of the computer though that has had the greatest influence on combinatorics, and vice versa.The consideration of NP complete problems typically involves enumerative problems in graph theory, one example being the existance of a Hamiltonian cycle in a graph. The use of the computer as a tool for proof in combinatorics, such as the 4-color problem, is now legendary. In addition, several good software packages, such as GAP and Combinatorica, have recently appeared that are explicitly designed to do combinatorics. One fact that is most interesting to me about combinatorics is that it gave the first explicit example of a mathematical statement that is unprovable in Peano arithmetic. Before coming across this, I used to think the unprovable statements of Godel had no direct relevance for mathematics, but were only interesting from the standpoint of its foundations.
This book is an introduction to combinatorics for the undergraduate mathematics student and for those working in applications of combinatorics. As with all the other guides in the Schaums series on mathematics, this one has a plethora of many interesting examples and serves its purpose well. Readers who need a more in-depth view can move on to more advanced works after reading this one. The author dedicates this book to the famous mathematician Paul Erdos, who is considered the father of modern combinatorics, and is considered one of most prolific of modern mathematicians, with over 1500 papers to his credit.
The author defines combinatorics as the branch of mathematics that attempts to answer enumeration questions without considering all possible cases. The latter is possible by the use of two fundamental rules, namely the sum rule and the product rule. The practical implementation of these rules involves the determination of permutations and combinations, which are discussed in the first chapter, along with the famous pigeonhole principle. Most of this chapter can be read by someone with a background in a typical college algebra course. The author considers some interesting problems in the "Solved Problems" section, for example one- and two-dimensional binomial random walks, and problems dealing with Ramsey, Catalan, and Stirling numbers. The consideration of Ramsey numbers will lead the reader to several very difficult open problems in combinatorics involving their explicit values.
Generalized permutations and combinations are considered in chapter two, along with selections and the inclusion-exclusion principle. The author proves the Sieve formula and the Phillip Hall Marriage Theorem. In the "Solved Problems" section, the duality principle of distribution, familiar from integer programming is proved, and the author works several problems in combinatorial number theory. A reader working in the field of dynamical systems will appreciate the discussion of the Moebius function in this section. Particularly interesting in this section is the discussion on rook and hit polynomials.
The consideration of generating functions and recurrence relations dominates chapter 3, wherein the author considers the partition problem for positive integers. The first and second identities of Euler are proved in the "Solved Problems" section, and Bernoulli numbers, so important in physics, are discussed in terms of their exponential generating functions. The physicist reader working in statistical physics will appreciate the discussion on Vandermonde determinants. Applications to group theory appear in the discussion on the Young tableaux, preparing the reader for the next chapter.
A more detailed discussion of group theory in combinatorics is given in chapter 4, the last chapter of the book. The author proves the Burnside-Frobenius, the Polya enumeration theorems, and Cayley's theorem in the "Solved Problems" section. Readers without a background in group theory can still read this chapter since the author reviews in detail the basic constructions in group theory, both in the main text and in the "Solved Problems" section. Combinatorial techniques had a large role to play in the problem of the classification of finite simple groups, the eventual classification proof taking over 15,000 journal pages and involving a large collaboration of mathematicians. Combinatorics also made its presence known in the work of Richard Borchers on the "monstrous moonshine" that brought together ideas from mathematical physics and the largest simple group, called the monster simple group.
The author devotes an appendix to graph theory, which is good considering the enormous power of combinatorics to problems in graph theory and computational geometry. Even though the discussion is brief, he does a good job of summarizing the main results, including a graph-theoretic version of Dilworth's theorem. Combinatorial/graph-theoretic considerations are extremely important in network routing design and many of the techniques discussed in this appendix find their way into these kinds of applications. The author asks the reader to prove that Dilworths' theorem, the Ford-Fulkerson theorem, Hall's marriage theorem, Konig's theorem, and Menger's theorem are equivalent. A very useful glossary of the important definitions and concepts used in the book is inserted at the end of the book.