Richard K. Guy and The Unity of Combinatorics —Stephen Kennedy

Stephen and Richard at MAA MathFest

This tribute by Stephen Kennedy (Carleton College), AMS/MAA Press Acquisitions, originally appeared in the most recent issue of MAA Focus and is shared with permission.

The news of Richard Guy’s passing was a blow. Not only because he was a dear friend, but also because I knew that the appearance of his last book, The Unity of Combinatorics, was imminent and that he would never see it. When I first met Richard decades ago I was too much in awe of him to actually talk, we had a nod-and-smile relationship for a long time. That changed about 15 years ago. I was sitting at an airport gate leaving JMM to come home and Richard in his familiar brown tweed jacket with his ever-present Peace is a Disarming Concept lapel button sat down next to me and asked about the math on the pad of paper in my lap. At the time I had just discovered Geometer’s Sketchpad and was using its capability to combine Euclidean geometry and motion to generate undergraduate research problems, questions like: What’s the locus of centroids of all the triangles that share a circumcircle? With Geometer’s Sketchpad you could make a little movie and observe that locus being generated in real time. It was thrilling to watch.

I don’t remember exactly what problem I was struggling with at that airport gate but it was something close to the above and Richard listened thoughtfully and we spent an hour swapping ideas and pictures. It was clear that he knew about a thousand times as much about geometry as I did and also clear that his brain worked at about twice the speed mine did. But my awe melted away in the face of his kindness and modesty. He was genuinely interested in my ideas and in working together on the problem. He also had a razor-sharp wit and after one of his jokes would flash his disarming, but devilish, grin. It was great fun to do mathematics with him. Eventually he started telling me about the lighthouse problem [2]: What is the locus of the point of intersection of two rotating lighthouse beams? The cited paper is a great place to go to understand Richard’s approach to mathematics and to experience his sense of humor. For another quick taste of the latter, check out the MAA Review of The Inquisitive Problem Solver by Richard’s alter ego, Dick Fellow.

When I got home I had an e-mail waiting from Richard with some more ideas about my problem. We continued that e-mail correspondence for a while. He always did me the kindness of pretending that I was knowledgeable about geometry; I think it was enough for him that I clearly loved it. A few years later I was in Calgary visiting Richard to talk about a possible book on combinatorial games. I spent a week with him, every morning we’d go to his office at the University of Calgary. He taught me about Sprague-Grundy theory and we analyzed dozens of games together. Every evening we’d go back to his home and eat one of the dreadful frozen pot pies he favored for dinner, then get back to work. For a time I thought I could understand three-car Dodgerydoo, Richard did me the courtesy of taking seriously the possibility that I did. (Of course, I didn’t. I think he probably suspected as much all along but was too polite to say so.) We never got the book put together. In spite of that, it was one of the best mathematical weeks in my life.

The Unity of Combinatorics is the latest volume in the MAA Carus series and its genesis was a paper by that name that Richard published in 1995. Richard was reacting to the perception that combinatorics was nothing more than a bag of disconnected clever tricks for toy problems. It is clear today that combinatorics is a mature mathematical discipline with deep problems, subtle results, and intriguing connections to other areas of mathematics. Twenty-five years ago that was not clear and combinatorics’s connection to recreational mathematics made it seem slightly disreputable and frivolous. This book was first imagined by Don Albers who encouraged Richard to expand his article and recruited Bud Brown as a co-author. The result reflects both authors’ personalities, their mathematical interests and their beguiling expository skills. It’s a pure pleasure to read; the perfect mixture of Richard’s gentle wit, Bud’s down-home, welcoming enthusiasm, and both authors’ deep knowledge of, and absolute joy in, the combinatorial landscape.

Let me give you a taste. Suppose you want to find a collection of five-element subsets of the eleven-element set $\{0,1,2,3,4,5,6,7,8,9,X\}$ with the property that each pair of elements occurs together exactly twice. It’s not obvious, at least to me, that such a collection is even possible. A quick count— each of 55 pairs occurring twice is 110 pairs, a five-element set contains ten pairs—will tell you that any such collection will contain 11 sets. But that’s no help in finding it, or even proving it’s possible. It just reassures you that it is not obviously impossible. The Brown-Guy example is given in Table 1, but you’re encouraged to try and construct your own example before peeking.

It is also not obvious why you want to do this. The respectable answer is that it is an example of an $(11,5,2)$ symmetric block design, objects that arose in the design of statistical experiments in agriculture. (The parameters correspond to the bolded numbers in the previous paragraph.) The frivolous answer points to the obvious analogy with Kirkman’s Schoolgirl Problem. You are of course wondering which values of $(v,k,\lambda )$ actually correspond to achievable symmetric designs. You should read Chapter 7. I’m more interested in following up on $(11,5,2)$ right now. Brown and Guy call this gadget a biplane. It is worthwhile to understand why.

Suppose that instead of requiring each pair of elements to occur twice we will be satisfied with a single appearance. As noted above there are 55 pairs and each five-tuple contains ten, so $(11,5,1)$ fails the obvious divisibility test and no such object exists. But, to take one example, $(91,10,1)$ does not fail and, so, is not obviously impossible. (Those numbers are a clue to what’s happening, but you might not recognize that.) If we think of the elements as points, we are looking for ten-point subsets such that each pair of points is in exactly one subset. Replace “subset” by “line” and you recognize the description of a finite projective plane of order nine. Thus, the $(11,5,2)$ biplane. More saliently, perhaps you begin to see Brown-Guy’s “Unity.”

Brown in [1] asked himself how he might draw a useful picture of the $(11,5,2)$ biplane. He wanted the picture to reflect some of the symmetries of the design. For example, note that the product of the two five-cycles $(1,3,9,5,4)(2,6,7,X,8)$ is a permutation of our original set of order five. Note that it preserves the block structure, e.g., 2456X goes to 61478. This corresponds to the five-fold rotational symmetry in the figure. In fact, as Brown and Guy show, the symmetry group of the biplane actually has order 660 and can be shown to be $PSL(2,11)$. Many of these symmetries can be seen directly in Figure 1.

One final unification observation. It’s interesting to notice that $2^{11}=1+(\genfrac{}{}{0ex}{}{23}{1})+(\genfrac{}{}{0ex}{}{23}{2})+(\genfrac{}{}{0ex}{}{23}{3})$. It is known that this equality is exactly what is required for the existence of a perfect three-error-correcting binary code. The alphabet has 23 symbols and the codewords are length 12. Similarly, the fact that $1+2\cdot (\genfrac{}{}{0ex}{}{11}{1})+2^2\cdot (\genfrac{}{}{0ex}{}{11}{2})=3^5$ means that there exists a perfect two-error-correcting ternary code. In this case the alphabet has 11 letters and the codewords have length six. Each of these codes can be realized as the row space of a particular matrix. Suppose one were to construct the $11\times 11$ incidence matrix for the $(11,5,2)$ biplane by putting a 1 in the $(i,j)$ entry if element $i$ is in subset $j$ of the biplane and a 0 if not. (NB: The subsets are indexed by their first listed element in Table 1.) This incidence matrix lives inside the code matrix as a submatrix in the case of each of those codes. You are invited to explore why.

All of the above was taken from just one chapter of Brown-Guy, and we have already run into statistics, group theory, linear algebra, coding theory, recreational mathematics, and projective geometry. Perhaps The Ubiquity of Combinatorics would have been a better title. Whatever we call it, it is full of wonders and breathes with Richard’s spirit. It is a fitting memorial to a mathematical giant whom we were lucky to have for 103 years.

******************

[1] Ezra Brown, The Fabulous (11, 5, 2) Biplane, Math. Mag., 77:2,
87–100, 2004, DOI: 10.1080/0025570x.2004.11953234.
[2] Richard K. Guy, The Lighthouse Theorem, Morley & Malfatti—
A Budget of Paradoxes, Amer. Math. Monthly, 114:2,
97–141, 2007, DOI: 10.1080/00029890.2007.11920398.