# Ron L. Graham’s lesser known significant contributions

Ron L. Graham is sadly no longer with us.

He was very prolific and his work spanned many areas of mathematics including graph theory, computational geometry, Ramsey theory, and quasi-randomness. His long association with Paul Erdős is of course very well known. Graham’s number, and Graham-Rothschild theorem, and the wonderful book Concrete Mathematics are other well known contributions.

However, some of his contributions may not be as widely known, but deserve to be so. This question is to encourage people to comment on such contributions. I am not familiar with his work on scheduling theory, for example.

He was into magic tricks and the mathematics behind them and co-authored a book on this with Persi Diaconis. And he was into juggling, like Claude Shannon.

Edit: Thanks to @LSpice for pointing out the Meta MathOverflow thread here on personal anecdotes.

• MMO thread for anecdotes: meta.mathoverflow.net/questions/4619/ron-graham-1935-2020 . Jul 8 '20 at 23:44
• Another wonderful book of his, co-authored with Rothschild and Spencer, is Ramsey Theory. It's been very influential for me, and although I don't think it qualifies as "lesser known", it is worth a mention here. Jul 9 '20 at 12:32
• Seems to be Bruce Lee Rothschild. Jul 10 '20 at 11:43

The largest small hexagon determines the largest area a plane hexagon of unit diameter can have. (No, it's not the regular hexagon!) I love the title. For further results in this direction, search for Mossinghoff's work on isodiametric polygons.

R. L. Graham, A Fibonacci-like sequence of composite numbers, Mathematics Magazine, Vol. 37, No. 5 (Nov., 1964), pp. 322-324.

Graham defined $$S(L_0,L_1)=(L_0,L_1,L_2,\dots)$$ to be a sequence of numbers satisfying $$L_{n+2}=L_{n+1}+L_n$$ for $$n=0,1,\dots$$. He found relatively prime numbers $$M,N$$ such that every term of $$S(M,N)$$ is composite.

Along with Chung, Diaconis, and Holmes, he determined that there are 17,152 different arrangements of the "Stomachion" tangram puzzle into a square. See, here for a nice summary.

The puzzle is attributed to Archimedes. There is some evidence that Archimedes might have been doing similar counting; after all, Hough taught us that Hellenistic Greeks had some relatively sophisticated combinatorics.

I vaguely recall seeing a video back in the early 2000's, wherein Diaconis and Holmes flew down to visit Chung and Graham; the four of them did the counting one weekend.

I have a soft spot for The cover polynomial of a digraph (co-authored with Fan Chung) because it was one of two papers that motivated my Ph.D. thesis problem. The cover polynomial is a kind of digraph analogue of the Tutte polynomial. They later generalized it to the matrix cover polynomial.

One nice thing about the cover polynomial is that it satisfies a rather unexpected combinatorial reciprocity theorem. It was previously known that the rook polynomial of a board determines the rook polynomial of its complement, but the definition of the cover polynomial allows this relationship to be expressed in a particularly nice combinatorial way. I've continued to reap the benefits of Chung and Graham's insight; just a few years ago, a generalization of this reciprocity theorem provided a key step in a joint paper of mine with Patrick Brosnan, proving a conjecture of Shareshian and Wachs on regular semisimple Hessenberg varieties.

The following was posted by Stuart Margolis on my Facebook. I hope he doesn't mind me including it here lightly edited.

Ron Graham wrote a few papers in finite semigroups in the late 1960s that were known only to the Rhodes school of semigroups for many years. They have been rediscovered over the last few years and are as fresh and important today as they were half a century ago.

The paper:

"On Finite O-Simple Semigroups and Graph Theory", R. Graham, MATHEMATICAL SYSTEMS THEORY, Vol, 2, NO. 4, 325-339, 1968,

was the first paper to explicitly look at finite 0-simple semigroups as bipartite group labeled graphs (also called gain graphs, voltage graphs and other names). Among many results, it has the beautiful theorem that classifies finite 0-simple semigroups whose idempotent generated subsemigroup has only trivial subgroups and idempotent generated subsemigroups of finite 0-simple semigroups in general. By a result of Des FitzGerald this work can be extended to study idempotent generated subsemigroups for all finite semigroups.

The results were rediscovered later and given a more topological flavor by C.H. Houghton in the early 1970s. The so called Graham-Houghton graph of a 0-simple semigroup has been a tool of great import in a burgeoning literature on idempotent generated semigroups that has appeared over the last years.

A treatment of this work appears in in section 4.13 of the Rhodes-Steinberg book, "The Q-Theory of Finite Semigroups".

The paper:

Maximal Subsemigroups of Finite Semigroups* N. GRAHAM, R. GRAHAM, AND J. RHODES, JOURNAL OF COMBINATORIAL THEORY 4, 203-209 (1968) does just what its title says- describes maximal subsemigroups of finite semigroups.

The paper remained largely unknown for many years and gets rediscovered every so often. In the last few years the paper "Chains of subsemigroups" by Cameron, Gadouleau, Mitchell and Peresse uses these results to study the longest chain of subsemigroups of a finite semigroup.

With various collaborators he developed an elegant and deep mathematical theory of juggling, involving for instance the affine Weyl group $$\tilde{A}_n$$. A seminal early paper is here.

My favorite result in combinatorics is Graham-Pollak theorem stating that the minimum number of bicliques (complete bipartite subgraphs) that partition the edge set of the complete graph K_n on n vertices is n-1. There are many such constructions with n-1 bicliques (exercise in Babai-Frankl notes), but the harder part is obtaining the lower bound for which Graham and Pollak used linear algebra. Graham and Pollak studied this problem in the context of addressing graphs, representing the vertices of a graph by words/addresses of the same length k over the alphabet {0,1,*} such that the distance between any two vertices equals the number of positions in their addresses where one has a 0 and the other has a 1. Graham and Pollak proved that you can always address a graph on n vertices and diameter d with addresses of length at most d(n-1) and conjectured an upper bound of n-1. This is known as the Squashed Cube Conjecture and was proved by Winkler in 1980s (also a chapter in Van Lint-Wilson "A Course in Combinatorics" book). As far as I know, determining the minimum value of k is not known to be NP-hard or not.

There are several variations of the biclique decomposition problem that are still open. For r>3, while asymptotically solved by Alon in 1986, the exact value of the minimum number of complete r-partite r-uniform hypergraphs whose edges partition the complete r-uniform hypergraph on n vertices is not known. Also, for t>1, one can define the minimum number of bicliques whose edges cover K_n such that each edge is covered once and at most t times. This parameter has connection to geometric problems as shown by Zaks in 1979 and Alon in 1997. It is known that this parameter is of order of magnitude n^{1/t}, but the exact value is not known for t>1. For example, when t=2, it is between \sqrt{n-1} and 2\sqrt{n} (lower bound due to Huang and Sudakov in 2012 and upper bound due to Alon 1997). See these slides for more details: https://www.ima.umn.edu/materials/2014-2015/W9.8-12.14/21263/ima-1.pdf

Corollary (Graham). A rational number $$p/q$$ can be written as a sum of finitely many distinct reciprocals of integer squares iff $$p/q \in [0,-1+\pi^2/6)~ \cup ~[1,\pi^2/6)$$.

For the statement of the full theorem from which this follows, see On Finite Sums of Unit Fractions, with Graham as the sole author. Link.

This result is not very significant, but in literature surround unit/Egyptian fraction-esque problems, this result is cited often; if not for its use than for its novelty.

• Very nice and interesting. Thanks for your answer. Jul 16 '20 at 2:27