Topic #10    -------------   OP-SF NET 5.2  ------------  March 15, 1998
                             ~~~~~~~~~~~~~
From: Charles Dunkl 
Subject: 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