Ron Graham

Ronald Graham was an American Mathematician, born on the 13th of October, 1935. He is perhaps best known for "Graham's Number", the (previously) largest number used in a proof, but his influence in the world of mathematics extends much further. He made contributions in the fields of number theory, graph theory, Ramsey theory, probability & statistics, computational geometry, and more. He taught as a professor at UC San Diego and was the doctoral advisor of nine students^[NAMS]. Of his many books and papers, many were collaborations with Paul Erdos and Fan Chung. Fan Chung, his wife, is an accomplished mathemetician in her own right and professor of Math and Computer Science at UCSD. Sadly, Ron passed away on the 6th of July, 2020^[NAMS].

I'd be remiss to write a biography on Ron Graham without mentioning that as well as being a legendary mathematician, he was also an accomplished juggler (and former president of the International Jugglers' Association!)^[IJA]. The photo below shows Ron juggling a 4-ball fountain. (Photo by Peter Vidor)

Graham's contributions to discrete mathematics

Graham's Number

Graham's Number^[NP] is the upper bound of the Graham-Rothschild theorem (published by Graham and Bruce Rothschild in 1971) which applies to a certain problem in Ramsey Theory. The problem can be understood like this:

Given a cube with $n$ dimensions (2 is a square, 3 is a cube, 4 is a hypercube, and so on), connect each vertex. We now have a complete graph on $2^n$ vertices. Try to find a 2-coloring of the edges of this graph that avoids having any 4-vertex coplanar complete subgraph that is only one color. In 2 dimensions, failing this would just mean coloring each edge the same color, and in 3 dimensions it can fail only at the faces of the cube. In 2 and 3 dimensions it's fairly easy to draw or imagine a coloring that avoids this pattern, so the next logical question is if we can always do this. Graham proved that the answer was no: given a hypercube of a certain number of dimensions, the pattern is unavoidable. The proof states the pattern is unavoidable with a cube of Graham's number dimensions.

The number used in the proof is almost impossibly large. If we tried to write down the number of digits (not even the number itself) using numbers as small as a Plank Length (the smallest possible distance) then we would run out of space in the observable universe^{BCMU]. The same is true for a definition in the form of $a ^ {b ^ {c ^ {\cdots}}}$. The smallest number of dimensions where the pattern is unavoidable is still unknown, but it's somewhere between 13^[JB] and (the slightly larger) Graham's Number.

Graham–Pollak theorem

The Graham-Pollak theorem concerns graph theory and was published by Graham and Henry O. Pollak. To understand it intuitively^[FD], draw 6 points, labeled $A$ through $F$, and see how many steps it takes to connect each point with an edge to create a complete graph with these vertices. You could connect them one edge at a time, $A$ to $B$, $B$ to $C$, etc., in which case it would take you 15 steps. Alternatively, you can connect multiple in one move, so long as each vertex is distinct, so $A$ to $B$, $C$, $D$, $E$, and $F$ is one "step" and draws a line from $A$ to each of the other vertices. Something like $A$ and $C$ to $B$, $E$, and $F$ is also valid, since each vertex appears only once and it doesn't repeat any edges from the previous step. Keeping in mind that each edge can only be drawn once (no repeats!), it turns out that the fewest possible steps are 5, in our example of 6 vertices. And, in general, the theorem states that it is impossible to partition the edges of a graph with $n$ vertices into fewer than $n - 1$ complete bipartite graphs. The example above is just to get an intuition for the problem; the original paper was concerned with telephone switching (which isn't used today), but it this theorem appears in many other places in mathematics.

Reflection on the constructed nature of the digital world

There was a lot of information on Ron Graham online. Being somewhat of a legendary modern figure, many mathematicians have written about him. I also got a lot of information about his life from his obituary, which lovingly recounts much of his life and work. The Numberphile video featuring Ron^[NP] was very informative and sweet, and hearing it straight from the horse's mouth made Graham's number make more sense to me. It made me think "What if other, older, famous mathematicians had had YouTube?". In all seriousness, the amount of information about him online (all good things), and the such high regard he was held in made me appreciate how genuine of a person he seemed and I wish I had gotten to meet him.

References

[NAMS] Buhler, Joe, et al. “Ronald Lewis Graham (1935–2020).” Notices of the American Mathematical Society, vol. 68, no. 11, Dec. 2021, p. 1, www.ams.org/notices/202111/rnoti-p1931.pdf.

[IJA] Cain, David. “Ron Graham Obituary.” _International Jugglers' Association_, 9 July 2020, www.juggle.org/ron-graham-obituary/.

[BCMU] Deserno, Markus. “Nobody Comprehends Graham’s Number.” Biophysics at CMU, research.phys.cmu.edu/biophysics/2021/01/09/nobody-comprehends-grahams-number/. Accessed 15 Feb. 2024.

[NP] "What Is Graham’s Number? (Feat Ron Graham)." YouTube, uploaded by Numberphile, 21 July 2014 www.youtube.com/watch?v=HX8bihEe3nA.

[FD] "A theorem with only rude proofs: The Graham-Pollak Theorem." YouTube, uploaded by Fine Design, 20 August 202 www.youtube.com/watch?v=6ByCnuCbPsg

[JB] Barkley, Jerome. Improved Lower Bound on an Euclidean Ramsey Problem. 2008. doi.org/10.48550/ARXIV.0811.1055.