Combinatorics Ancient and Modern

Towards the end of 2011, I posted a paper on the arXiv with the title “Aftermath”. A correspondent wondered if this was a Borgesian game, the final chapter to a nonexistent book.

Happily, it was not so. Combinatorics Ancient and Modern, edited by Robin Wilson and John Watkins, has just appeared (or possibly not – my copy claims to be “pre-publication”, but the book is scheduled to appear in June).

Robin Wilson is both a graph theorist and a historian of mathematics, and is also well known as an editor of books on such things as Selected Topics in Graph Theory (several of these) and Music and Mathematics. He is a co-author of mine on the introductory chapter to the volume on Topics in Algebraic Graph Theory. John Watkins is also a co-author of mine, on a research paper on snarks with Amanda Chetwynd. The two editors very generously allowed me the last word in their book.

You might say that my chapter is a bit of an outsider in a book packed with information; what I wrote is probably not so different from some of the things I post here. I discuss what has happened in combinatorics in the last half-century or so, and speculate just a bit on where we might be heading. I had fun writing it, but in any case it is not the reason why you should read the book.

The book is in four sections, of which mine (introduced by a fine photograph of Endre Szemerédi) is the last, and I will say little more about it here.

First comes a chapter by Donald Knuth entitled “Two thousand years of combinatorics”. He is principally concerned with systematic listing of combinatorial objects: why it was done (for example, the compositions of a natural number built of ones and twos, counted by Fibonacci numbers, arose in Sanskrit prosody), how it was done (often first by simply writing down all the objects the author could think of, but usually better methods came along later), and speculation about why trees don’t appear in these endeavours. He expresses the opinion that the construction of long lists by people like Carl Friedrich Hindenburg contributed to the poor reputation of combinatorics:

Gösta Mittag-Leffler, who assembled a magnificent library of mathematical literature about one hundred years after Hindenburg’s death, decided to place all such work on a special shelf marked “Dekadenter” (decadent). And this category still persists in the library of Sweden’s Institut Mittag-Leffler today, even as that institute attracts world-class combinatorial mathematicians whose work is anything but decadent.

The next part, on “Ancient Combinatorics”, has chapters on Indian, Chinese, Islamic, Jewish, and renaissance combinatorics, the origins of modern combinatorics, and an article by Anthony Edwards on the arithmetical triangle which is now misattributed to Pascal. (In both India and China, the arithmetic triangle was known earlier; in India it was called the meru prastāra, or “holy mountain”.)

Eberhard Knobloch dates the origin of modern combinatorics to the Pascal–Fermat correspondence in 1654, more usually regarded as the origin of modern probability theory. Other founding fathers of the subject included Leibniz (whose work on symmetric functions, partitions and determinants was unpublished until recently), Jacob Bernoulli (whose book Ars Conjectandi was perhaps the first modern textbook on combinatorics), Abraham de Moivre, James Stirling, and others; by 1730, the subject was established. It is notable that this list includes some of the great mathematicians of the day; the relatively poor reputation of combinatorics came later. His choice of 1730 as end date of course excludes the huge contributions of Leonhard Euler, who might well be regarded as the founding father of the subject: he worked on partitions, Latin squares, graph theory, and polyhedra in the following years.

The section on “Modern Combinatorics” is thematic rather than geographic (as it should be – we no longer have “Jewish mathematics”, I am glad to say), with chapters on early and modern graph theory, partitions, block designs, Latin squares, enumeration, and combinatorial set theory. Whether these topics give an adequate coverage of combinatorics today, I rather doubt. Also, one of my hobby-horses: the term “block designs” comes from statistics, where it has a very different meaning from the 2-designs discussed here. The chapter on Latin squares is sufficiently up-to-date to include a reference to the result of McGuire, Tugemann and Civario that there are no 16-clue sudoku puzzles; an example of a 17-clue puzzle is given for the reader’s enjoyment.

George Andrews’ chapter on partitions goes from the work of Leibniz to the Rogers–Ramanujan identities and modern results on plane partitions, and includes an unsolved problem:

Are there infinitely many integers n for which the total number of partitions of n is prime?

(He advises us to put our money on “yes”.)

The book is aimed at a variety of readers: mathematicians, historians, students, and even the general public, though of course not all it is appropriate for all of these. There is a lot of serious combinatorics here, some but not all of which is covered in elementary courses; students who work through it will learn a lot, as well as getting a perspective on where it all came from.

Alas, nothing is perfect. The typesetting in the book seems to me to be significantly below the standard one would expect from Oxford University Press. Quotations are set in a very light sans-serif font, which I find distracting; the same font is used for bulleted lists which are not quotes at all, but parts of the running text. The font used for mathematical formulas is the same as that of the surrounding text, and so varies from one occurrence to another. References are done in an uneasy compromise between footnotes at the end of a chapter (history-book style) and simple citations (as mathematicians are used to). A pity. (While proof-reading my chapter, I decided to revise it to include the footnotes in the text, to avoid this difficulty.)