You are here

A Primer in Combinatorics

Alexander Kheyfits
Walter de Gruyter
Publication Date: 
Number of Pages: 
[Reviewed by
Michael Berg
, on

I had the great good fortune to spend my undergraduate years at UCLA in the 1970s, when their roster of number theorists included a cadre of scholars who were also exceptionally active in combinatorics. For instance, there were Bruce Rothschild (properly a Ramsey theorist, I guess), Basil Gordon (to this day the clearest lecturer I have ever seen), and the late E. G. Straus, from whom I took my very first number theory course, in my first year: I was immediately hooked.

As time went on, however, I gravitated rather emphatically toward algebraic number theory, still often under the tutelage of Straus and Gordon, but now with V. S. Varadarajan taking charge of me (for which I will always be thankful) and instilling in me a passion for everything from class field theory to the theory of automorphic forms, and all this with something of a French flavor: a book by Weil, a book by Serre, a lecture series featuring adèlic and idèlic methods, and so on. So combinatorics, and much else, was largely eclipsed by any and all things to do with algebraic number fields: Varadarajan is both a deep and a broad mathematician, but he is not a combinatorialist.

Thus, despite wonderful and abundant opportunities I never properly pursued this “art of counting” and have over the years, happily more off than on, found this gap to be a burden. For one thing, generating functions are beautiful and useful things and I have experienced at least two occasions where they might have been of value in a research context. I had to find another way, however, possibly less elegant and more opaque.

Another example from my personal experience along these lines is found in the subject of graph theory. In fact, something very close to my heart, the vast strategy of analytic methods in number theory, i.e. the exploitation of the foibles and idiosyncrasies of special functions to study algebraic number fields — typically with something like Fourier analysis packed along in one’s toolkit — can sometimes also benefit rather dramatically from a dose of graph theory: UCSD’s Audrey Terras (my advisor, now emerita) has been playing with zeta functions of graphs for quite a while now, for example.

Well, that’s a lot of convincing propaganda for the cause, is it not? Should not analytic and algebraic number theorists, e.g. automorphic formers (for instance), learn some combinatorics in earnest, even if it be somewhat off their beaten track? There is a strong case to be made here, I believe (and propose to follow suit myself).

Happily, along comes Alexander Kheyfits’ book. It is good news, I think, at least for some one like me, that Kheyfits is, as far as his stated specialty is concerned, a complex analyst and potential theorist, as opposed to a combinatorialist down to the bone marrow: it makes his presentation of the subject, in this aptly titled Primer in Combinatorics, more user-friendly and pain-free. This certainly jives with the relatively easy pace of Kheyfits’ presentation and the care he takes in developing his themes, making appropriate use of (many) examples and illustrations. And there are, equally appropriately, scads of exercises: perhaps more so than any other subject, combinatorics is a learn-by-doing affair: Fingerspitzenkunde and all that…

Qua specifications, the book is proposed as a one-semester text for “a course in combinatorics with elements of graph theory,” and is pitched at the level of undergraduates and (particularly with Ch’s 4, 5 in the mix) beginning graduate students.

A Primer in Combinatorics is split into two parts, the first being “Introductory Combinatorics and Graph Theory,” the second consisting of Ch’s. 4 and 5, “Combinatorial Analysis.” Ch. 1 deals with basic counting: permutations, combinations, sum and product rules, &c.; Ch’s. 2 and 3 do graph theory — with élan. After this, in Ch. 4, the extremely important topics of “inclusion-exclusion” and generating functions are covered, while Ch. 5 introduces Ramsey Theory, Hall’s (marriage) theorem, block designs, and “the proof, due to Hilton, of the necessary and sufficient conditions [for] the existence of Steiner triple systems.” (Wow!).

This said, A Primer in Combinatorics looks to be considerably more than what Kheyfits describes it to be: it is a primer, yes, but there’s a lot more to it than that. The book not only serves to lay a good foundation in the art of counting for any one interested (and in need of the skill), it will kindle and foster a genuine enthusiasm for the artistry that comes with its practice.

Michael Berg is Professor of Mathematics at Loyola Marymount University in Los Angeles, CA.