Newtonpedia ES
Home › Mathematics › Ronald Graham
Ronald Graham
Image: Wikimedia Commons

Ronald Graham

American mathematician who helped build modern discrete mathematics and created Graham's number · 1935–2020

Born
October 31, 1935
Died
July 6, 2020
Country
United States
Section
Mathematics

Biography

Ronald Lewis Graham (Taft, California, 1935 – La Jolla, California, 2020) was an American mathematician whom the American Mathematical Society credited as one of the principal architects of the rapid worldwide growth of discrete mathematics, the field that studies separate, countable objects such as graphs, integer sequences and ways of arranging elements. He is best known for Graham's number, a quantity so enormous that for years the Guinness Book of Records listed it as the largest number ever used in a mathematical proof, and for his long friendship and collaboration with the Hungarian mathematician Paul Erdős.

Graham's childhood was restless. Born in Taft, in southern California, to a father who worked in oil fields and later in the merchant marine, he moved often between California and Georgia, skipped several school grades and never stayed at one school for more than a year. At fifteen he won a Ford Foundation scholarship to the University of Chicago, where he took up gymnastics but no mathematics. After three years he transferred to the University of California, Berkeley, officially studying electrical engineering but also working on number theory with D. H. Lehmer, who would supervise his doctoral thesis. He joined the US Air Force in 1955, completed a physics degree in 1959 at the University of Alaska Fairbanks, and returned to Berkeley to earn his PhD in mathematics in 1962. The thesis dealt with finite sums of rational numbers, and the topic of Egyptian fractions, which write a quantity as a sum of fractions with numerator one, stayed with him throughout his career.

In 1962 he began working at Bell Labs, the research arm of the telephone company AT&T, in New Jersey. He spent 37 years there and eventually directed its information sciences work. In 1963, at a conference in Colorado, he met Paul Erdős, one of the most prolific mathematicians in history, and the two became close friends and frequent collaborators. A popular story says Erdős beat him at table tennis, prompting Graham to improve enough to become the lab's champion. He popularised the Erdős number, which counts the links of co-authorship between a researcher and Erdős, and wrote about thirty papers with him. Erdős even entrusted Graham with organising his mathematical papers and, reportedly, his finances.

His work spanned several fields. In Ramsey theory, which asks what order must appear in any sufficiently large structure, he published in 1971 with Bruce Rothschild a theorem about words and combinatorial cubes. While trying to bound one case, he proposed the number that bears his name, so large that ordinary notation cannot express it. With Henry Pollak, in papers from 1971 and 1972, he showed that splitting the edges of a complete graph on n vertices into complete bipartite subgraphs requires at least n−1 of them, and their proof relies on linear algebra. In scheduling, his early work on assigning tasks to several machines introduced worst-case performance ratios into approximation algorithms, and with Edward Coffman he defined a method that is optimal for two machines. In computational geometry he devised the Graham scan, published in 1972, which computes the convex hull of a set of points, and he studied the largest-area polygon for a given diameter, whose optimal shape turned out not always to be regular. His book Concrete Mathematics, written with Donald Knuth and Oren Patashnik, is among the best known texts for students of computing.

In 1977 he co-wrote with Persi Diaconis a paper on nonparametric statistics comparing orderings of items. From 1993 to 1994 he served as president of the American Mathematical Society. In 1999 he retired from AT&T and moved to the University of California, San Diego, where he held the Irwin and Joan Jacobs chair and was chief scientist of the California Institute for Telecommunications and Information Technology. He was married to the mathematician Fan Chung, with whom he produced many joint papers. His fame reached popular culture too: he was featured in Ripley's Believe It or Not! both as a mathematician and as an accomplished trampolinist and juggler, and he led the International Jugglers' Association. He received the Steele Prize of the American Mathematical Society for lifetime achievement in 2003. He died in La Jolla at the age of 84 on 6 July 2020.

His legacy lies in the problems he posed and the tools he left behind, from scheduling algorithms to the theory of quasirandom graphs, which studies graphs that look random in their properties. Many results carry his name, and they continue to drive research in discrete mathematics.

Main contributions

  • 1971Graham–Rothschild theorem: a Ramsey theory result on words and combinatorial cubes, published with Bruce Rothschild.
  • 1971Graham–Pollak theorem: the minimum number of complete bipartite subgraphs needed to partition a complete graph on n vertices is n−1.
  • 1972Graham scan: a method for computing the convex hull of a set of points in the plane.
  • 1972Coffman–Graham algorithm: an optimal procedure for scheduling tasks on two machines, and an approximate one for more machines.
  • 1979Graham notation: a three-part system for classifying scheduling problems by machines, tasks and the measure to optimise.
  • 1980Old and new results in combinatorial number theory, a book with Paul Erdős collecting open problems in number theory.
  • 1989Fundamental theorem of quasirandom graphs, obtained with Fan Chung and R. M. Wilson, showing that several definitions of these graphs are equivalent.
  • 1989Concrete Mathematics, a book with Donald Knuth and Oren Patashnik, a foundation text for computer science.

Teachers and students

Studied under:

Derrick Henry Lehmer

Taught:

Glenn Howland HurlbertBharti P. TemkinJoshua N. CooperDavid Jacob WildstromJia MaoNan ZangEric TresslerAndy ParrishJay Cummings

See their academic family tree →

Trivia and anecdotes

Graham's number

It arose while bounding a case of a Ramsey theory theorem and was listed in the Guinness Book of Records as the largest number used in a proof. Larger numbers, such as TREE(3), are now known to exceed it.

A juggling mathematician

He performed as a trampolinist in a circus while a graduate student and later presided over the International Jugglers' Association, which led to an appearance on Ripley's Believe It or Not!.

Their contemporaries

While Ronald Graham was alive (1935–2020)…

Alive at the same time

Discovered or invented in those years

  • 1945
    ComputerA programmable machine that takes in data, processes it by following stored instructions, and produces results, able to switch tasks simply by running different software.
  • 1957
    Artificial satelliteAn artificial satellite is a human-made object placed in orbit around a celestial body, usually Earth, to collect information, relay signals, or carry out a specific task.
  • 1969
    InternetA global network of interconnected computer networks that communicate using the TCP/IP protocol suite.
  • 1971
    EmailA network service that lets users send and receive digital messages through addressed mailboxes, much like postal mail but electronic.
  • 1973
    Mobile phoneA handheld wireless phone that lets people make and receive calls while moving across a cellular network area.
  • 1989
    World Wide WebA system of linked documents and resources, connected by hyperlinks and accessed over the Internet with web browsers.

See this life on the timeline →

More people in Mathematics