Topic #10 ------------- OP-SF NET 5.2 ------------ March 15, 1998 ~~~~~~~~~~~~~ From: Charles DunklSubject: Review of book on Combinatorics (This item appeared in our Activity Group's Newsletter, vol 8, no 2, February 1998, pp. 15-16) Introduction to Combinatorics By Martin J. Erickson Wiley, Chichester-New York-Brisbane-Toronto-Singapore, xii + 195 pp., 1996, ISBN 0-471-15408-3 This is a book of eleven chapters introducing itself as a textbook. This review is written mainly from the point of view of evaluating it as such. This reviewer admits to preferring textbooks to be systematic and comprehensive. Some chapters of the present work tend to be sketchy rather than systematic. We begin with a description of the contents. Chapter 1 is a collection of needed information about sets, group theory, linear algebra, and algebraic number theory. Sometimes the text can not quite decide between just stating facts with reference to well-known textbooks and actually giving definitions and some proofs. Some definitions should have been avoided: what does it gain to define a finite set as one having finitely many elements without defining "finitely" (or discussing bijections involving the basic sets {1,2,3,...,n})? In the rather important paragraph introducing the symmetric group the example of the cycle decomposition has the element "3" appearing in two cycles (one assumes that the second occurrence should have been "5", but this makes it difficult for a student to understand the concept). The standard binomial coefficient identities, like the Vandermonde sum, appear in this chapter, but the proofs tend to be too swift for a beginner and uninteresting for an expert. Chapter 2 deals with the pigeonhole principle, has lots of detail and presents interesting examples, like good approximation to irrational numbers by rational ones. There is a brief introduction to graph theory (but it refers to planar graphs without giving a definition, except later in one of the problems). Sequences and partial orders are taken up in Chapter 3. The author displays more enthusiasm for the material here, which includes the Erdos-Szekeres and Sperner theorems. The proofs are complete but place some demands on the reader, like making a sketch or supplying more detail. This style holds throughout the book. Chapter 4 continues with the theme of existence theorems and takes up the topic of Ramsey numbers, graph colorings, probabilistic methods and van der Waerden's theorem on arithmetic progressions. These three chapters form the "existence" part. The part on "enumeration" comprises Chapters 5 through 8. Counting problems are introduced mostly using function concepts like injections and surjections. The standard topics of Stirling numbers, Bell numbers, derangements and their generating functions are covered here. The unpleasant notation [x]^n is used for the Pochhammer symbol (x)_n. In six pages, Chapter 7 discusses tableaux, hook-length formulas, and the Robinson-Schensted correspondence. This seems rather sketchy and may not be useful. On the other hand, Chapter 8 is a very good presentation of Polya's theory of counting, with examples from graphs and cycle indices of permutations. The third part of the book on "construction" comprises Chapters 9, 10 and 11, and presents linear codes, Hamming and Golay codes, t-designs, Latin squares, Hadamard matrices and the Leech lattice. There is a bibliography of some sixty monographs and a six-page index. Also there are statements of open problems (most of them have been open for some time!) and selections of problems from past Putnam Competition Examinations. As a textbook this work might be appropriate for an undergraduate seminar for upper level mathematics students or as a supplement in a graduate course. The coverage of Ramsey theory, Polya's counting methods, codes and designs may be the strongest part of the book. Generally the proofs demand careful perusal by the reader and have more words than formulas; nevertheless the words are used very concisely! Every chapter has a section of problems, which tend to be difficult. Somehow the reader is left with the feeling of having been on a hasty tour of combinatorics without a satisfactory amount of detail in the reader's favorite part of the subject (whatever that might be). Indeed, similarly styled books have been designated as "essays", indicating a collection of personal insights and commentaries. This may be the better way of appreciating the present work. Charles Dunkl

Back to Home Page of

SIAM AG on Orthogonal Polynomials and Special Functions

Page maintained by Martin Muldoon