A

David

Darling

Graham, Ronald Lewis (1935–2020)

Ronald Graham

Ronald Graham was an American mathematician and leading combinatorialist after whom Graham's number is named. Graham was also one of the country's best jugglers and former president of the International Juggler's Association. In his youth, he and two friends were professional trampolinists who performed with a circus as the Bouncing Baers. His office ceiling was covered with a large net that he could lower and attach to his waist so that when practicing juggling with six or seven balls, any that were dropped would roll back to him. Graham was a professor in the department of computer science and engineering at the University of California at San Diego.

 

Ron Graham was born in 1935, in Taft, California, where his father worked in the nearby oil fields. The family were always on the move when Graham was young, mostly between California and Georgia, as his dad shifted from one oil or shipbuilding job to another. Being exceptionally bright, an effect of this itinerant lifestyle was that, when starting a new school, Graham would often be put in a class of older children so that he skipped grades and made rapid academic progress. Astronomy was his first passion but this was soon replaced by the subject at which he excelled: mathematics. At the age of 15 he won a scholarship to the University of Chicago and began his studies there without ever graduating from high school. Strangely, in his three years at Chicago he didn't take a single maths course due to the fact that his scholarship score in this area was so high. On the upside, he did learn gymnastics and developed a special talent for juggling and trampoline.

 

In 1954, Graham moved to the University of California at Berkeley for a year, where he majored in electrical engineering. He also took a course in number theory, given by Derrick Henry Lehmer, which shaped his future career. To help support himself while studying he and two other students performed as a trampoline troupe at schools, supermarket openings, and even the circus. In 1962, he earned his PhD at Berkeley, under Lehmer's supervision, with a thesis titled "On Finite Sums of Rational Numbers".

 

At a conference in Boulder, Colorado, in 1963, Graham first met Hungarian number theorist Paul Erdös – one of the most prolific mathematicians of the last century. Erdös spent almost every waking hour solving mathematical problems and essentially living out of a battered suitcase, which he took with him from one conference or university to another. Colleagues opened their homes to him, more than happy to exchange board and lodging for deep mathematical conversation, and he donated much of his income to good causes or toward prizes for correct solutions to problems he suggested. Graham and Erdös had similar interests, became close friends despite a generational difference in age, and wrote nearly 30 papers together. In total, Erdös published around 1,500 papers – more than any other mathematician in history – many of them with collaborators. Graham popularised the idea of the Erdös number. Anyone who had co-authored a paper with Erdös had an Erdös number of 1. Someone who'd co-authored a paper with someone who'd co-authored a paper with Erdös had an Erdös number of 2, and so on.

 


Graham's number

Graham's number is a stupendously large number that found its way in to the Guinness Book of Records as the biggest number ever obtained as part of a mathematical proof; it is named after its discoverer, Ronald Graham. Graham's number is the upper bound solution to a very exotic problem in Ramsey theory, namely: What is the smallest dimension n of a hypercube such that if the lines joining all pairs of corners are two-colored, a planar complete graph K4 of one color will be forced?

 

This is exactly equivalent to a problem that can be stated in plain language: Take any number of people, list every possible committee that can be formed from them, and consider every possible pair of committees. How many people must be in the original group so that no matter how the assignments are made, there will be four committees in which all the pairs fall in the same group, and all the people belong to an even number of committees. Graham's number is the greatest value that the answer could take. It is so large that it can only be written using special big-number notation, such as Knuth's up-arrow notation. Even then, it must be built up in stages.

 

First, construct the number G1 = 3↑↑...↑↑3, where there are 3↑↑↑↑3 up-arrows. This, in itself, is a number far, far beyond anyone's ability to even remotely comprehend. Next, construct G2 = 3↑↑...↑↑3, where there are G1 up-arrows; then construct G3 = 3↑↑...↑↑3, where there are G2 up-arrows; then continue this pattern until the number G62 has been made. Graham's number G = 3↑↑...↑↑3, where there are G62 up-arrows. While the unthinkably large upper boundary to the problem described earlier is given by Graham's number, nobody, including Graham himself, believes the solution is nearly so large. In fact, it is thought that the actual answer is probably 6!

 


Reference

1. Gardner, M. "Mathematical Games." Scientific American, 237, 18-28, Nov. 1977.