The Unity of Combinatorics

In his famous 1906 “white suit” speech, Mark Twain recalled a meeting before the House of Lords committee, where he argued in favor of perpetual copyright. According to Twain, the chairman of the committee with “some resentment in his manner,” countered:

“What is a book? A book is just built from base to roof on ideas, and there can be no property in it.” 10

Sidestepping the copyright issue, the unnamed chairman had a point. In the year 2021, in the middle of the pandemic, books are ideas. They come in a variety of electronic formats and sizes, they can be “borrowed” from the “cloud” for a limited time, and are more ephemeral than long-lasting. Clinging to the bygone era of safety and stability, we just keep thinking of them as sturdy paper volumes.

When it comes to math books, the ideas are fundamental. Really, we judge them largely based on the ideas they present, and we are willing to sacrifice both time and effort to acquire these ideas. In fact, as a literary genre, math books get away with a slow uninventive style, dull technical presentation, anticlimactic ending, and no plot to speak of.

The book under review is very different. As math books go, it is extraordinarily well written, permeated with several intertwining ideas we are about to untangle. It is also founded on a somewhat dated idea worth discussing.

The authors are Ezra Brown (b. 1944), a Distinguished Professor Emeritus at Virginia Tech, and Richard Guy (1916–2020), a British-born mathematician who until his death was a Professor Emeritus at the University of Calgary. To say they are famous is an understatement. They are both mathematical celebrities, winners of numerous awards for their mathematical exposition.

As the authors helpfully explain in the beginning, the book began as a talk by Richard Guy titled “The unity of combinatorics.” The talk was later published as an article 4 with the same title. As an enterprising MAA editor, Don Albers wanted to turn this article into a book. Twenty-five years later, this task was accomplished. Yep, you read that right—sometimes it takes a quarter of a century to get things done.

The original article is an exquisite piece of mathematical art. It is written in a highly unusual style of many very short sections, each of which is but a glimpse at some connections between nice problems in different areas of combinatorics. Like the ubiquitous SciFi “space portals,” these connections are far-reaching and appear seemingly out of nowhere as neither is the background explained nor is the extent of the connections clarified. You can easily see the case for the book: curious readers want to know what’s really going on….

It would be cool if the publishers had ignored the occasional overlap and included the original article in the beginning of the book, as a sort of “treasure map” to the full thrill of a story. Here is a quote from the introduction of both the book and the article:

“One reason why Combinatorics has been slow to become accepted as part of mainstream Mathematics is the common belief that it consists of a bag of isolated tricks, a number of areas: [very long list – IP] with little or no connection between them. We shall see that they have numerous threads weaving them together into a beautifully patterned tapestry.” 4

We will come back to the “bag of isolated tricks” part, but for now let us concentrate on the “tapestry” line and the long list of areas we hid in that quote.

The kind of combinatorics the authors have in mind is the study of configurations, which are certain finite arrangements of elements. The reader can be forgiven for not knowing the exact meaning of a “configuration,” as it was an abstraction popular back in the 1960s and 70s, before modern ideas, methods, and applications shifted combinatorics in many other directions. It was best described by Claude Berge:

“A configuration arises every time objects are distributed according to certain predetermined constraints. [..] The concept of configuration can be made mathematically precise by defining it as a mapping of a set of objects into a finite abstract set with a given structure [..] Nevertheless, one is only interested in mappings satisfying certain constraints.” 1

If you are still unclear about what these mysterious “configurations” are, you are in good company. Bear with me. This is what the book is about.

The authors are largely concerned with the existence of many different types of configurations, such as discrete geometries, Steiner systems, magic squares, error-correcting codes, Hadamard matrices, packings of graphs, aperiodic tilings, graph embeddings, winning positions in combinatorial games, etc. If this looks like a random list, that’s completely intentional. These are the kind of items the authors included in the “very long list” in the quote above.

The configurations in the book tend to be combinatorial objects, whose existence is hard to prove directly. Sometimes, the best (or the only) way to give an explicit construction is by assuming a large degree of symmetry of such configurations. That makes constructions intuitively convoluted, but technically easier to describe. This is where the authors come in.

The main idea of the book is to give a very clean and elegant construction of rather delicate and technical configurations by stating them in a more natural language, or by reducing them to simpler configurations constructed earlier. This is done at an astonishing level of engagement with the readers, who are left wondering if they are reading “real” or “recreational” mathematics. Clearly, it is both.

The book chapters are unevenly split into several background chapters and many more advanced chapters. The early chapters are mostly introductory and have some obligatory discussions of Fibonacci and Catalan numbers, graphs, codes, projective spaces, etc. The presentation here is no better and no worse than any other good combinatorics textbook. Advanced readers who feel confident with things like the size of $\operatorname {GL}(n,\mathbb{F}_q)$ may wish to skip most of this material.

The more advanced chapters are largely copied from selected articles in the Mathematics Magazine and The American Mathematical Monthly, written by the authors and other people. These chapters are largely independent of each other and some are pure gems. Several chapters cover various aspects of the unique $(7,3,1)$ block design and its connections to the Fano plane, Nim positions, Heawood’s partitions of the torus, Hamming codes, etc. The automorphism group of this block design is $\operatorname {PSL}(2,\mathbb{F}_7) \simeq \operatorname {GL}(3,\mathbb{F}_2)$, and an explanation of this group isomorphism is an interesting separate chapter.

Other luminaries which make major appearances are Kirkman’s $(15,3,1)$ block design, often called Kirkman’s schoolgirl problem, and the Steiner system $S(5,8,24)$ leading to a construction of the Mathieu group $M_{24}$. This material is largely classical, even if presented in a novel and interesting way. I was especially curious to learn about a nontrivial embedding of $S_5$ into $S_6$, leading to an exceptional outer automorphism of $S_6$ (Chapter 17). While I always knew this fact, I never bothered to look up the construction, which turned out to be related to a curious game-15 style puzzle. The final Chapter 19 covers the Miracle Octad Generator (MOG) describing multiplication in $M_{24}$. This chapter was written by Robert T. Curtis and remained unpublished until now.

The results in the book largely involve elementary combinatorics, linear algebra, and group theory, and can be understood by any math major who has taken introductory courses in all three subjects. It is similar in difficulty to other group theory “puzzle books” such as 5, but is both broader and covers some more advanced material. I would argue that the book can be accessible to all students, including advanced highschoolers willing to read some additional background material on the web or elsewhere.

So, who should buy the book? The beginners, I think. Seeing and understanding a lot of fun math can be inspiring. It doesn’t really matter if the math is old fashioned or cutting edge. If a student likes puzzles and is algebraically curious, this book might be the best summer reading they can get. And they will need all the introductory chapters to get ready for the advanced articles.

On the other hand, I would not recommend that people in the area buy The Unity of Combinatorics, since almost all advanced chapters are available online from journal websites. While it’s convenient to have all of these articles together in the same place, some readers might prefer to save money and download them all individually for free.⁠¹ To such readers and Mark Twain detractors, I prepared a full list here: https://bit.ly/38KCQI9.^✖ Even if you want to teach the MOG, you might still be better off using a more standard exposition in 2, §$11$, which you probably already own. Making this book largely a collection of previously published short stories may not have been the best idea, in my opinion.

Now, back to The Unity of Combinatorics question. What gives? Is combinatorics really a “bag of isolated tricks,” or is it united in some sort of “patterned tapestry”? The answer is emphatically No and No, this being an ultimate false choice.

As I see it, the whole idea of combinatorics as a “slow to become accepted” field feels like a throwback to the long-forgotten era. This attitude was unfair but reasonably common back in 1970, outright insulting and relatively uncommon in 1995, and was utterly preposterous in 2020. Take it from Richard Stanley who wrote this in 1971:

“The current resurgence of combinatorics […] is by now recognized by all mathematicians. Scoffers regard combinatorics as a chaotic realm of binomial coefficients, graphs, and lattices, with a mixed bag of ad hoc tricks and techniques for investigating them. In reality, there has been a tremendous unifying drive to combinatorics in recent years.” 9

Compare this quote with Richard Stanley’s views from last year:

“There has been fantastic development since I started doing combinatorics in the 1960s. Algebraic combinatorics by definition involves the relationship between combinatorics and algebra. It is now a major subarea of combinatorics [..] Of course areas of combinatorics beside algebraic combinatorics also have a deep relationship with other parts of mathematics. [..] All these connections are great examples of the unity of mathematics.” 7

What happened to combinatorics in the past few decades is not much different from what happened to algebra some decades earlier: it rapidly developed until it became highly technical and highly specialized. Some areas such as algebraic combinatorics advanced to the point of a near complete separation from the rest of the field, as major results and technical tools became inaccessible to outsiders. To continue with the tapestry analogy, there is no longer a need for weaving loose threads together as each area is now its own intricate Gobelin carpet.

In fact, whenever a bridge between two areas of combinatorics is built, this is now viewed as a major breakthrough, not unlike bridges between combinatorics and other fields such as commutative algebra, computational complexity, number theory, etc. Most relevant to the book, an example of such a bridge is Peter Keevash’s amazing proof of the existence of large enough designs via the probabilistic method 6. You wouldn’t find that work mentioned in this book full of designs, and you can guess why: the powerful but messy probabilistic arguments can spoil the simple elegance of algebraic constructions.

Same with the Ringel conjecture on packing complete graphs $K_{2n+1}$ with $(2n+1)$ isomorphic trees on $n$ vertices, recently resolved for large $n$ in a fantastic development by Richard Montgomery, Alexey Pokrovskiy, and Benny Sudakov 8. By comparison, the book opted for a nice observation on how to use Steiner triple systems to pack 100 triangles into $K_{25}$ (see §$6.5$). There are many other examples of well-intentioned omissions of this type, as the authors’ primary goal is to entertain and clarify, rather than to survey the state of the art.

Note that there is nothing especially mysterious about this phenomenon of disappearing elegance. As combinatorial objects get large, they get more complicated and chaotic in a way that can no longer be captured with fairly rigid algebraic constructions. A prime example of this is the Ramsey graphs whose existence was famously proved by Paul Erdős in a few lines by a probabilistic argument, but no explicit constructions are known to this day. The same pattern can be observed in many other configurations in the book.

For example, the above-mentioned $(7,3,1)$ design is nicely related to the quaternions and the octonions, but as the authors discuss in §$13.3$, the string of normed division algebras stops here (this result is called Hurwitz’s theorem). Similarly, the linear group isomorphism mentioned above is a notable coincidence which does not generalize. Nor does the exceptional automorphism of $S_6$, as we have $\operatorname {Aut}(S_n)=S_n$ for all $n\ge 7$. In fact, if you squint hard enough, all these examples can be seen as further manifestations of the “strong law of small numbers” memorably coined by Richard Guy in 3.

To finish this line of thought, it gives me no pleasure to conclude that the case for the unity of combinatorics is too weak to be taken seriously. Perhaps, the unity of mathematics as a whole is an easier claim to establish, as evident from Stanley’s back-to-back quotes. On the other hand, this lack of unity is not necessarily a bad thing, as we would be amiss without the rich diversity of cultures, languages, open problems, tools, and applications of different areas.

The book by Brown and Guy is a nostalgic trip to the time when this illusory unity seemed within reach. It is an unusual idea and an interesting lesson in the alternative history of combinatorics, of “what could have been” if the field hadn’t advanced as far as it did. It is also a good read to sweeten the deal.