# Ronald Lewis Graham

### Born: 31 Oct 1935 in Taft, California, USA

Ronald Graham is known by all as Ron. When he was born, his father was working in the oil fields around Taft, which is not surprising for someone living there since the town owes its existence to the two major California oilfields on either side. However, his father did not keep the same job for very long and, as Ron was growing up, the family moved back and forward between Georgia and California as Ron's father worked in various jobs related to oil fields and shipbuilding. As a result of continual moving, Ron's schooling was in a whole variety of different schools, none of which he was in for more than eighteen months. In 1941, with the United States entering World War II, Ron's father enlisted in the Merchant Marine.

Moving schools had the effect that the extremely bright young boy could enter a new school in a higher class than normal for his age. This meant that he progressed rapidly missing out a few grades. Being younger, and therefore smaller, than his classmates, his interests at this time tended to be academic rather than sporting. His first real fascination was with astronomy but soon he fell in love with mathematics. When in the fifth form a teacher showed him how to extract square roots, he immediately wondered if he could generalise the method to find cube roots and, although he was not able to solve his own problem for a long time, he learnt a lot of advanced mathematics in the attempt. When he was eleven years old his mathematics teacher, Mr Schwab, gave him a problem which he could not solve [2]:-

I knew algebra and trigonometry and thought I could solve any problem given to me. But one day, Mr Schwab gave me one I couldn't do. The problem was to find the size of a population of mice if it was known that the death rate was proportional to the size of the population. It took a knowledge of differential equations to solve it. He then gave me a book and told me that I would be able to solve the problem by the time I finished it. That book was 'Calculus' by Granville, Smith and Longley. He was right. By the end of the semester, I finished the book and had a solution. He also chose me to be on the school chess team.

Graham saw little of his father after he joined the Merchant Marine and eventually his parents were divorced. His mother then went to live in Florida, and Graham once again had to adjust to a new school. At 15 he won a Ford Foundation scholarship to the University of Chicago and he began his university studies without graduating from high school. He spent three years at the University of Chicago where, due to the level of his mathematics attainment in the scholarship examinations he took no further mathematics courses, but he learnt gymnastics and in particular became proficient at juggling and the trampoline. His scholarship lasted for three years after which he spent the year 1954-55 at the University of California at Berkeley where he majored in electrical engineering. However he took a number theory course given by Derrick Henry Lehmer [1]:-

As an undergraduate at Berkeley, a one-year course in number theory taught by D H Lehmer fired my imagination for the subject ... Although I never took another course from Dick Lehmer, he taught me the value of independence of thought and an appreciation for the algorithmic issues in mathematics.

Graham decided to enlist in the U.S. Air Force rather than wait to be drafted. He spent four years in the Air Force, three of which were spent in Fairbanks, Alaska. Keen to continue his education, he enrolled at the University of Alaska and, carrying out his studies as well as his Air Force duties, he was awarded a B.S. in physics in 1959. When he had served four years in the Air Force he returned to the University of California, Berkeley, and was awarded an M.A. in 1961. Then he undertook research for his doctorate with D H Lehmer as his thesis advisor [13]:-

While he was there, he and two other students formed a professional trampoline troupe, earning money by performing at schools, supermarket openings, and even the circus.

He was awarded a Ph.D. in 1962 for his thesis On Finite Sums of Rational Numbers. While working towards his doctorate, Graham married Nancy Young who was a mathematics major at Berkeley; they had two children Cheryl and Mark. Following the award of his doctorate he moved to New Jersey and joined the staff at the Bell Telephone Laboratories. Soon he was publishing papers which related to his doctoral thesis. Within two years he had eight papers in print: On a theorem of Uspensky (1963); A combinatorial theorem for partial sums (1963); A theorem on partitions (1963); On quadruples of consecutive kth power residues (1964); On finite sums of reciprocals of distinct nth powers (1964); On finite sums of unit fractions (1964); Complete sequences of polynomial values (1964); and On a conjecture of Erdős in additive number theory (1964).

To get a flavour of these papers we give William LeVeque's summary of A theorem on partitions:-

It is first shown that every integer greater than 77 can be partitioned into distinct positive integers whose reciprocals add to 1. This depends on a table of such partitions for the integers between 78 and 333, together with a pair of transformations by which this table may be extended recursively. Using this result and a further lemma, it is then shown that if a and b are positive rational numbers, there is an r = r(a, b) such that if n > r, there is a partition of n into integers larger than b whose reciprocals add to a.

In 1963 there was a Number Theory Conference in Boulder, Colorado. Graham attended the conference as did Paul Erdős and the two mathematicians met for the first time. Graham recalled [2]:-

I saw this rather senior guy of 50, already quite famous, playing ping-pong during one of the breaks. He asked me if I wanted to play and I agreed. He absolutely killed me! I had played casual ping-pong but I couldn't believe that this old guy had beaten me. ... I went back to New Jersey ... I bought a table, joined a club, started playing at Bell Labs, and in the State league. I eventually became the Bell Labs champion at ping-pong, and won one of the New Jersey titles.

Graham also started to collaborate with Erdős and, in total, they published 30 joint papers (many with additional joint authors). Examples of these papers are: On sums of Fibonnaci numbers (1972); On a linear diophantine problem of Frobenius (1972); On packing squares with equal squares (1975); On products of factorials (1976); and Maximal anti-Ramsey graphs and the strong chromatic number (1989). Donald Albers writes [2]:-

As Erdős aged, Graham helped him tend to some of the basics of life - paying taxes, buying clothes, etc. Graham even set up an Erdős room in his home. Up until the time of his death in September 1996, Erdős frequently stayed with Graham ...

Graham was forced to become an expert on currency exchange rates because honoraria from Erdős's lectures were paid in a wide variety of currencies. Graham said:-

I signed his name on cheques and deposited them. I did this so long I doubt the bank would have cashed a cheque if he had endorsed it himself.

There is one further Graham-Erdős link we should mention at this point. Almost every professional mathematician knows his "Erdős number" - the number of links in the shortest chain of papers, adjacent ones with an author in common, leading to Erdős. For example my [EFR] Erdős number is 2 since I have written a joint paper with a mathematician who has written a joint paper with Erdős. This notion (now a part of MathSciNet) was due to Graham in a 1979 paper On properties of a well-known graph or what is your Ramsey number? If you look up this paper you'll find that the author is Tom Odda. That was the pseudonym under which Graham wrote the paper (in fact Tom Odda is a Mandarin term of abuse - Graham was learning Mandarin at the time).

In 1991, Gian-Carlo Rota nominated Graham to be President of the American Mathematical Society writing [12]:-

Graham is one of the charismatic figures in contemporary mathematics, as well as the leading problem-solver of his generation. For the last twenty-five years, he has been the central figure in the development of discrete mathematics. His seminal work has led to the birth of at least three new branches of mathematics: Ramsey theory, computational geometry, and worst case analysis of multiprocessing algorithms (now sometimes referred to as "Graham type analysis.") Graham's characteristic quality is an indefatigable activity, both in the cause of mathematics, and on behalf of it applications. Ron will never turn down a telephone call from a colleague, near or far, asking for help on a problem. Every one of his collaborators knows that Ron will somehow find whatever hours or days are needed to come up with some substantial suggestion, and frequently with the crucial step towards the solution. He is unusual, unique perhaps, in being able to effectively work on several problems at once, while carrying a full load of administrative work at Bell Labs. Ron's positive view of mathematics and of science, as well as his entertaining lectures, have inspired generations of mathematicians.

Graham served as President of the American Mathematical Society in 1993-94. Perhaps this is an appropriate place to note that he was also President of the Mathematical Association of America in 2003-05.

At Bell Laboratories, Graham was Director of Information Sciences from 1962 to 1995. He was then appointed Chief Scientist in 1996. In 1999 he left Bell Laboratories, but we should not think that he had been out of the academic world for these 37 years. During that time he held visiting positions at Princeton University, Stanford University, the California Institute of Technology, the University of California, Los Angeles, and the University of California, Davis. He was appointed as a University Professor of Mathematical Sciences at Rutgers and held this part-time appointment from 1986 to 1999. Graham was appointed to the Irwin and Joan Jacobs Endowed Chair of Computer and Information Science at the University of California at San Diego in 1999; he continues to hold this Chair.

Ron and Nancy Graham were divorced in the late 1970s. In 1983 he married Fan Chung who also worked at Bell Laboratories. Both work on the same areas of mathematics and had been writing joint papers since 1975: for example On multicolor Ramsey numbers for complete bipartite graphs (1975); On the set of distances determined by the union of arithmetic progressions (1976); (with Paul Erdős) On the product of the point and line covering numbers of a graph (1979). By December 2009 MathSciNet records 77 joint papers by Ron Graham and Fan Chung (many with additional joint authors).

We now look briefly at some of the books Graham has written. In 1980, in collaboration with Bruce Rothschild and Joel Spencer, he wrote Ramsey theory. The authors write:-

Ramsey theory has only within the last ten years been recognized as a cohesive subdiscipline of combinatorial analysis. The basic philosophy underlying the theory is that within any sufficiently large system some regularity must always exist. To quote the late T S Motzkin: "Complete disorder is impossible." Consequently, it is not surprising that results from Ramsey theory occur throughout a large part of mathematics - Ramsey theory is a jewel of pure mathematics.

Other books by Graham include: (with Paul Erdős) Old and new problems and results in combinatorial number theory (1980); Rudiments of Ramsey theory (1981) described by a reviewer as "not only very readable in terms of mathematical exposition, it is highly entertaining"; (with Donald Knuth and Oren Patashnik) Concrete mathematics. A foundation for computer science (1989); and (with Fan Chung) Erdős on graphs (1998).

Graham has received the Pólya Prize in Combinatorics from the Society for Industrial and Applied Mathematics in 1972, the Carl Allendoerfer Award from the Mathematical Association of America in 1990, the Lester R Ford Award from the Mathematical Association of America in 1991, and the Euler Medal from the Institute of Combinatorics and Its Applications in 1994. He has been elected to the National Academy of Sciences of the United States (he has served as its treasurer since 1996), the Hungarian Academy of Sciences, the American Academy of Arts and Sciences, and the American Association for the Advancement of Science. He was an invited speaker at the International Congress of Mathematicians held in Warsaw in August 1983 and was the American Mathematical Society's Gibbs Lecturer in 2000. He was a plenary speaker at the British Mathematical Colloquium in East Anglia in 1990 when he gave the lecture Arithmetic progressions: from Hilbert to Shelah and he was again a plenary speaker in 2009 in Galway when he gave the lecture The combinatorics of solving linear equations. He has been awarded honorary degrees by Western Michigan University (1984), St Olaf College (1985), the University of Alaska (1988), Central Michigan University (2000), and Wittenberg University (2000).

In 2003, Graham received the Steele Award for Lifetime Achievement from the American Mathematical Society. The citation reads [1]:-

Ron Graham has been one of the principal architects of the rapid development worldwide of discrete mathematics in recent years. He has made many important research contributions to this subject, including the development, with Fan Chung, of the theory of quasirandom combinatorial and graphical families, Ramsey theory, the theory of packing and covering, etc., as well as to the theory of numbers, and seminal contributions to approximation algorithms and computational geometry (the "Graham scan"). Furthermore, his talks and his writings have done much to shape the positive public image of mathematical research in the USA, as well as to inspire young people to enter the subject. He was chief scientist at Bell Labs for many years and built it into a world-class centre for research in discrete mathematics and theoretical computer science. He served as president of the American Mathematical Society in 1993-94.

In his reply on the occasion of receiving the Steele Award, Graham said [1]:-

I can't remember a time when I didn't love doing mathematics, and that desire has not dimmed over the years (yet!). But I also get great pleasure sharing mathematical discoveries and insights with others, even though this can present a special challenge for mathematicians talking to non-mathematicians. However, I really believe that this type of communication will become increasingly important in the future.

Article by: J J O'Connor and E F Robertson

February 2010

MacTutor History of Mathematics
[http://www-history.mcs.st-andrews.ac.uk/Biographies/Graham.html]