Combinatorics and Finite Geometry

This is one of a number of books that are intended as textbooks for an undergraduate course in combinatorics at the junior/senior level. It differs from its competition largely in the selection of topics that it covers. 

 

More specifically, this book, as the title suggests, introduces combinatorics by focusing primarily on finite geometries. It starts with basic counting, but covers the rudiments at a somewhat more rapid pace than do many other texts. The first chapter covers, in less than 35 pages, permutations and combinations (including the symmetric group), binomial and multinomial coefficients, the Pigeonhole Principle, and generating functions (with applications to the Fibonacci sequence). Then, anticipating further work with finite geometry, Chapter 2 introduces relevant number theory and algebra, including modular arithmetic (covering the Euler phi-function, Fermat’s Little Theorem, Euler’s theorem, and the Chinese Remainder theorem) and finite fields. (The existence and uniqueness of a finite field for every prime power order is stated without proof, though some discussion is given of how to construct finite fields of low prime power order.) The rest of the chapter is spent dealing with numbers of number-theoretic or combinatorial significance, including square, cubical, triangular and perfect numbers, and also Catalan numbers and Stirling numbers (of the first and second kind). I was puzzled by the fact that the author proved that any integer of the form \( 2^{p-1}(2^{p}-1) \), where \( 2^{p}-1 \) is prime, is perfect, but did not even state that any even perfect number is of this form.

 

The next chapter introduces Latin squares and, in particular, mutually orthogonal Latin squares (MOLS), which are strongly related to the question of whether affine and projective planes of a given order exist. Indeed, chapter 4 then introduces affine and projective planes. The relationship between affine and projective planes is established, and the connection between these planes and MOLS is stated and proved. Connections with finite fields are also discussed, as is the big unsolved question in this area, which is: for which n does a projective plane of order n exist? Another mild criticism: the author states that a projective plane has order n if every line contains n + 1 points, but fails to mention that any two lines in a finite projective plane must have the same number of points. It seems to be implicit in the book that any finite projective plane has an order, but this result should be proved.  

 

Chapter 5 looks at graph theory and offers, in less than 25 pages, a quick tour of the very basics of the subject. Instructors of a combinatorics course who want to include some discussion of graph theory should find this chapter very suitable for that purpose. 

 

The next chapter returns to geometry and discusses higher-dimensional affine and projective spaces, using linear algebra as a major tool. A highlight of this chapter is the Bruck-Ryser theorem on finite projective planes; the proof of this result is often omitted in introductory texts, but is given here.  This chapter also contains a fairly extensive discussion of Desargues’ theorem and non-Desarguesian projective planes, topics that, again, are rarely covered in books like this one.

 

Finite projective and affine planes are special cases of more general objects called designs, and these are studied in Chapter 7, which addresses a number of topics that are discussed in some other combinatorics books: balanced incomplete block designs, symmetric designs, the Kirkman schoolgirl problem, etc. 

 

These seven chapters offer a nice course that introduces the basic principles of combinatorics, focusing on finite geometry. There is likely more here than can be covered in a one-semester course.  But there is more to come. From this point on, the book breaks up into individual and largely independent chapters, covering miscellaneous combinatorial objects (e.g., Hadamard matrices and partially ordered sets), discrete probability on finite sample spaces (another mild criticism: the author uses the phrases “sample space” and “event” without defining them, and fails to mention explicitly that his definition of probability works only when the sample space consists of equally-likely events), group theory (including applications to automorphisms of finite geometries), algebraic coding theory, cryptography, and combinatorial games.

 

Given that this book covers a lot of topics that competing books do not, it is only natural that there will be some topics omitted from this text that many other books cover. Exponential generating functions offer, I think, the most glaring omission. Hall’s “marriage theorem” is also missing, as is any discussion of counting under symmetry (e.g., Burnside’s lemma and Polya counting). This last omission is a bit surprising since the author does, as previously noted, develop group theory for another purpose. I also would have liked to see some more interesting illustrations of the Pigeonhole Principle than are presented here—for example, a statement and proof of the Erdös-Szekeres theorem. 

 

Some readers might question the advisability of including chapters on, say, cryptography and coding theory, which are not typically taught in combinatorics courses, while omitting some of these other topics, but this is a matter of taste. The author’s selection of topics does have the advantage of allowing the reader to see a wide variety of applications of combinatorial principles. 

 

The author’s writing style is reasonably clear, albeit a bit terse on occasion. The reader is assumed to be familiar with basic ideas of proof (including mathematical induction), but apart from that very little in the way of substantive mathematical knowledge is assumed. The reader should know the very basics of set theory (union, intersection, etc.) and be familiar with the definition of an equivalence relation, and the fact that the equivalence classes of an equivalence relation partition the underlying set; however, the basic definitions involving functions (injective, surjective, bijective) are defined in the text. 

 

There are a reasonable number of exercises at the end of each chapter; based on a quick perusal, they seem to vary from easy to moderate. Solutions to the odd-numbered ones appear at the end of the book, but an instructor may not think these solutions are the optimal ones. For example, one exercise asks the reader to prove that C(2n, n) is always even. The author solves this by manipulating factorials rather than giving a more illuminating combinatorial proof (counting subsets of order n, pairing each one with its complement). 

 

To summarize and conclude: an instructor looking for a text for a somewhat unusual combinatorics course should certainly take a look at this book. The students may not see everything they would in a more traditional course, but at the same time will get a good idea of how the subject of combinatorics intersects with other branches of mathematics, such as algebra, geometry and number theory. 

---

 

Mark Hunacek (mhunacek@iastate.edu) is a Teaching Professor Emeritus at Iowa State University.