Ronald Graham

Ronald Lewis Graham (October 31, 1935 – July 6, 2020)[1] was an American mathematician credited by the American Mathematical Society as "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years".

He published six books and about 400 papers, and had nearly 200 co-authors, including many collaborative works with his wife Fan Chung and with Paul Erdős.

[3][4][5] Graham was born in Taft, California, on October 31, 1935;[6] his father was an oil field worker and later merchant marine.

Instead, at the age of 15, he won a Ford Foundation scholarship to the University of Chicago, where he learned gymnastics but took no mathematics courses.

[1] After three years, when his scholarship expired, he moved to the University of California, Berkeley, officially as a student of electrical engineering but also studying number theory under D. H. Lehmer,[1] and winning a title as California state trampoline champion.

[7] He enlisted in the United States Air Force in 1955, when he reached the age of eligibility,[8] left Berkeley without a degree, and was stationed in Fairbanks, Alaska, where he finally completed a bachelor's degree in physics in 1959 at the University of Alaska Fairbanks.

In 1963, at a conference in Colorado, he met the Hungarian mathematician Paul Erdős (1913–1996),[1] who became a close friend and frequent research collaborator.

[A15] Graham divorced in the 1970s; in 1983 he married his Bell Labs colleague and frequent coauthor Fan Chung.

[1] He retired from AT&T in 1999 after 37 years of service,[11] and moved to the University of California, San Diego (UCSD), as the Irwin and Joan Jacobs Endowed Professor of Computer and Information Science.

[6][13] Graham made important contributions in multiple areas of mathematics and theoretical computer science.

He published about 400 papers, a quarter of those with Chung,[14] and six books, including Concrete Mathematics with Donald Knuth and Oren Patashnik.

[26] Graham's early work on job shop scheduling[A66][A69] introduced the worst-case approximation ratio into the study of approximation algorithms, and laid the foundations for the later development of competitive analysis of online algorithms.

[29] In a survey article on scheduling algorithms published in 1979, Graham and his coauthors introduced a three-symbol notation for classifying theoretical scheduling problems according to the system of machines they are to run on, the characteristics of the tasks and resources such as requirements for synchronization or non-interruption, and the performance measure to be optimized.

[A75b] Klaus Roth and Bob Vaughan proved that uncovered area at least proportional to the square root of the side length may sometimes be needed; proving a tight bound on the uncovered area remains an open problem.

[33] In nonparametric statistics, a 1977 paper by Persi Diaconis and Graham studied the statistical properties of Spearman's footrule, a measure of rank correlation that compares two permutations by summing, over each item, the distance between the positions of the item in the two permutations.

is the number of inversions between the two permutations (a non-normalized version of the Kendall rank correlation coefficient), and

As well, Graham made significant contributions to the theory of juggling, including a sequence of publications on siteswaps.

[4] In 2003, Graham won the American Mathematical Society's annual Leroy P. Steele Prize for Lifetime Achievement.

[2] He was one of five inaugural winners of the George Pólya Prize of the Society for Industrial and Applied Mathematics, sharing it with fellow Ramsey theorists Klaus Leeb, Bruce Rothschild, Alfred Hales, and Robert I.

[36] He was also one of two inaugural winners of the Euler Medal of the Institute of Combinatorics and its Applications, the other being Claude Berge.

[41] Graham was an invited speaker at the 1982 International Congress of Mathematicians (held 1983 in Warsaw),[13] speaking on "Recent developments in Ramsey theory".

[44] The proceedings of the Integers 2005 conference was published as a festschrift for Ron Graham's 70th birthday.

Ronald Graham, his wife Fan Chung , and Paul Erdős , Japan 1986
Partition of the edges of the complete graph into five complete bipartite subgraphs, according to the Graham–Pollak theorem
Ronald Graham juggling a four-ball fountain (1986)