View source for Ronald Graham

{{Short description|American mathematician (1935–2020)}}
{{Other people}}
{{good article}}
{{Use mdy dates|date=February 2021}}
{{Infobox scientist
| image             = ronald graham writing.jpg
| caption           = Graham in 1998
| birth_name        = Ronald Lewis Graham
| birth_date        = {{birth date|1935|10|31}}
| birth_place       = [[Taft, California]], U.S.
| death_date        = {{Death date and age|2020|7|6|1935|10|31}}
| death_place       = [[San Diego]], California, U.S.
| known_for         = {{Plainlist|
* [[Coffman–Graham algorithm]]
* [[Erdős–Graham problem]]
* [[Graham's number]]
* [[Graham scan]]
* [[Graham–Pollak theorem]]
* [[Optimal job scheduling]] notation
}}
| alma_mater        = {{plainlist|1=
* [[University of Alaska Fairbanks]] ([[Bachelor of Science|BS]])
* [[University of California, Berkeley]] ([[PhD]])
}}
| fields            = {{plainlist|1=
* [[Mathematics]]
* [[Computer science]]
}}
| doctoral_advisor  = [[Derrick Henry Lehmer]]
| thesis_title      = On Finite Sums of Rational Numbers
| thesis_year       = 1962
| workplaces        = {{Plainlist|
* [[Bell Labs]]
* [[AT&T Labs]]
* [[California Institute for Telecommunications and Information Technology|Cal-(IT)<sup>2</sup>]]
* [[University of California, San Diego|UCSD]]
}}
| spouse            = {{marriage|[[Fan Chung]]|1983}}
| awards            = {{plainlist|1=<!-- too many to list them all; please only list the most significant honors -->
* [[George Pólya Prize (SIAM)|Pólya Prize]] (1971)
* [[National Academy of Sciences|Nat. Acad. Sci.]] (1985)
* [[Leroy P. Steele Prize|Steele Prize]] (2003)
}}
}}

'''Ronald Lewis Graham''' (October 31, 1935{{Snd}}July 6, 2020)<ref name="MacTutor">{{MacTutor Biography|id=Graham|mode=cs1}}</ref> 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".<ref name="AMS-200304">{{cite magazine |url=http://www.ams.org/notices/200304/comm-steele.pdf |access-date=July 2, 2014 |title=2003 Steele Prizes |magazine=[[Notices of the American Mathematical Society]] |volume=50 |issue=4 |pages=462{{ndash}}467 |date=April 2003 |url-status=dead |archive-url=https://web.archive.org/web/20110206205557/http://www.ams.org/notices/200304/comm-steele.pdf |archive-date=February 6, 2011 }}</ref>  He was president of both the American Mathematical Society and the [[Mathematical Association of America]], and his honors included the [[Leroy P. Steele Prize]] for lifetime achievement and election to the [[National Academy of Sciences]].

After graduate study at the [[University of California, Berkeley]], Graham worked for many years at [[Bell Labs]] and later at the [[University of California, San Diego]]. He did important work in [[scheduling algorithm|scheduling theory]], [[computational geometry]], [[Ramsey theory]], and [[quasi-randomness]],<ref name="Horgan">{{cite journal |first=John |last=Horgan |author-link=John Horgan (journalist) |date=March 1997 |title=Profile: Ronald L. Graham{{Snd}} Juggling Act |journal=[[Scientific American]] |volume=276 |issue=3 |pages=28{{ndash}}30 |doi=10.1038/scientificamerican0397-28 |url=http://www.cix.co.uk/~solipsys/new/SciAmProfileOfRonGraham.html |access-date=July 8, 2020 |archive-date=July 17, 2020 |archive-url=https://web.archive.org/web/20200717204533/http://www.cix.co.uk/~solipsys/new/SciAmProfileOfRonGraham.html |url-status=dead }}</ref> and many topics in mathematics are named after him. 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]].

Graham has been featured in ''[[Ripley's Believe It or Not!]]'' for being not only "one of the world's foremost mathematicians", but also an accomplished trampolinist and juggler. He served as president of the [[International Jugglers' Association]].<ref name="Horgan" /><ref name=jugObit>{{cite web|url=https://www.juggle.org/ron-graham-obituary/|title=Ron Graham Obituary|publisher=International Jugglers' Association|date=July 9, 2020|access-date=July 13, 2020}}</ref><ref name="Calit2" />

==Biography==
Graham was born in [[Taft, California]], on October 31, 1935;<ref name="MAA-20200707">{{cite web |title=Ronald Lewis Graham, 2003–2004 MAA President |url=https://www.maa.org/about-maa/governance/maa-presidents/ronald-lewis-graham-2003-2004-maa-president |website=[[Mathematical Association of America]] |access-date=July 7, 2020 |date=July 7, 2020 |archive-date=July 7, 2020 |archive-url=https://web.archive.org/web/20200707233651/https://www.maa.org/about-maa/governance/maa-presidents/ronald-lewis-graham-2003-2004-maa-president |url-status=dead }}</ref> his father was an oil field worker and later merchant marine. Despite Graham's later interest in gymnastics, he was small and non-athletic.<ref name=nice>{{cite journal|last=Albers|first=Donald J.|date=November 1996|doi=10.1080/10724117.1996.11974993|issue=2|journal=Math Horizons|jstor=25678089|pages=18–23|title=A Nice Genius|volume=4}}</ref> He grew up moving frequently between California and Georgia, skipping several grades of school in these moves, and never staying at any one school longer than a year.<ref name="MacTutor"/><ref name=nice/> As a teenager, he moved to Florida with his then-divorced mother, where he went to but did not finish high school. 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.<ref name="MacTutor"/>

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]],<ref name="MacTutor"/> and winning a title as California state trampoline champion.<ref name=nice/> He enlisted in the [[United States Air Force]] in 1955, when he reached the age of eligibility,<ref name="SDUT"/> 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]].<ref name="MacTutor"/> Returning to Berkeley for graduate study, he received his Ph.D. in mathematics in 1962. His dissertation, supervised by Lehmer, was ''On Finite Sums of Rational Numbers''.<ref name=mg/> While a graduate student, he supported himself by performing on trampoline in a circus,<ref name="SDUT"/> and married Nancy Young, an undergraduate mathematics student at Berkeley; they had two children.<ref name="MacTutor"/>

[[File:Ronald graham couple with erdos 1986.jpg|thumb|left|upright|Ronald Graham, his wife [[Fan Chung]], and [[Paul Erdős]], Japan 1986]]
After completing his doctorate, Graham went to work in 1962 at [[Bell Labs]] and later as Director of Information Sciences at [[AT&T Labs]], both in [[New Jersey]]. In 1963, at a conference in Colorado, he met the Hungarian mathematician [[Paul Erdős]] (1913–1996),<ref name="MacTutor"/> who became a close friend and frequent research collaborator. Graham was chagrined to be beaten in [[ping-pong]] by Erdős, then already middle-aged; he returned to New Jersey determined to improve his game, and eventually became Bell Labs champion and won a state title in the game.<ref name="MacTutor"/> Graham later popularized the concept of the [[Erdős number]], a measure of distance from Erdős in the collaboration network of mathematicians;<ref name="Erdos">{{cite book|title=The man who loved only numbers: the story of Paul Erdős and the search for mathematical truth|first=Paul|last=Hoffman|publisher=Hyperion|year=1998|isbn=978-0-7868-6362-4|pages=[https://archive.org/details/manwholovedonlyn00hoff/page/109 109{{ndash}}110]|title-link=The man who loved only numbers}}</ref><ref name="SDUT"/> his many works with Erdős include two books of [[open problem]]s{{ran|B1}}{{ran|B5}} and Erdős's final posthumous paper.{{ran|A15}} Graham divorced in the 1970s; in 1983 he married his Bell Labs colleague and frequent coauthor [[Fan Chung]].<ref name="MacTutor"/>

While at Bell Labs, Graham also took a position at [[Rutgers University]] as University Professor of Mathematical Sciences in 1986, and served as president of the [[American Mathematical Society]] from 1993 to 1994. He became Chief Scientist of the Labs in 1995.<ref name="MacTutor"/> He retired from AT&T in 1999 after 37 years of service,<ref name="UCSD-20200204">{{cite web|url=http://www.math.ucsd.edu/~ronspubs/mis_09_magical_day.pdf|first1=Larry|last1=Rabiner|title=Ron Graham{{Snd}} A Biographical Retrospective|date=February 4, 2000}}</ref> and moved to the [[University of California, San Diego]] (UCSD), as the Irwin and Joan Jacobs Endowed Professor of Computer and Information Science.<ref name="MacTutor"/><ref name="SDUT">{{cite news|url=http://www.math.ucsd.edu/~fan/ron/papers/pro_08_tribune.pdf|title=You can count on him: Math expert coolly juggles scientific puzzles and six or seven balls|first=Bruce V.|last=Bigelow|date=March 18, 2003|newspaper=[[The San Diego Union-Tribune]]}}</ref> At UCSD, he also became chief scientist at the [[California Institute for Telecommunications and Information Technology]].<ref name="SDUT"/><ref name="Calit2">{{cite web |title=Juggling Numbers: UC San Diego Professor Honored for Work in Applied Mathematics and Computational Science |url=http://www.calit2.net/newsroom/release.php?id=1520 |website=[[California Institute for Telecommunications and Information Technology]] |access-date=July 9, 2020 |date=May 4, 2009}}</ref> In 2003–04, he was president of the [[Mathematical Association of America]].<ref name="MacTutor" />

Graham died of [[bronchiectasis]]<ref>{{cite news |last1=Chang |first1=Kenneth |title=Ronald L. Graham, Who Unlocked the Magic of Numbers, Dies at 84 |url=https://nytimes.com/2020/07/23/science/ronald-l-graham-who-unlocked-the-magic-of-numbers-dies-at-84.html |access-date=January 28, 2021 |work=The New York Times |date=July 23, 2020}}</ref> on July 6, 2020, aged 84, in [[La Jolla]], California.<ref name="MAA-20200707"/><ref name="AMS-20200707">{{cite web |title=The Latest: Ronald Graham, 1935–2020 |url=https://www.ams.org/news?news_id=6244 |website=[[American Mathematical Society]] |access-date=July 7, 2020 |date=July 7, 2020}}</ref>

==Contributions==
Graham made important contributions in multiple areas of mathematics and theoretical computer science. He published about 400 papers, a quarter of those with Chung,<ref>[https://www.theguardian.com/science/2020/aug/03/ron-graham-obituary Ron Graham obituary] by Colm Mulcahy, The Guardian, August 3, 2020</ref> and six books, including ''[[Concrete Mathematics]]'' with [[Donald Knuth]] and [[Oren Patashnik]].{{ran|B4}} The Erdős Number Project lists him as having nearly 200 coauthors.<ref>{{cite web|title=Erdos1: coauthors of Paul Erdős, together with their coauthors listed beneath them|work=Erdős Number Project|access-date=July 12, 2020|url=https://oakland.edu/enp/thedata/erdos1/}}</ref> He was the [[doctoral advisor]] of nine students, one each at the [[City University of New York]] and [[Rutgers University]] while he was at Bell Labs, and seven at UC San Diego.<ref name=mg/>

Notable topics in mathematics named after Graham include the [[Erdős–Graham problem]] on [[Egyptian fraction]]s, the [[Graham–Rothschild theorem]] in the [[Ramsey theory]] of [[parameter word]]s and [[Graham's number]] derived from it, the [[Graham–Pollak theorem]] and [[Graham's pebbling conjecture]] in [[graph theory]], the [[Coffman–Graham algorithm]] for approximate scheduling and graph drawing, and the [[Graham scan]] algorithm for [[convex hull]]s. He also began the study of [[primefree sequence]]s, the [[Boolean Pythagorean triples problem]], the [[biggest little polygon]], and [[square packing in a square]].

Graham was one of the contributors to the publications of [[G. W. Peck]], a pseudonymous mathematical collaboration named for the initials of its members, with Graham as the "G".<ref>{{cite journal|last=Peck|first=G. W.|doi=10.1016/S0012-365X(02)00595-2|mr=1935723|issue=2–3|journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]|pages=193–224|title=Kleitman and combinatorics: a celebration|volume=257|year=2002|doi-access=free}} See in particular Section 4, "The mysterious G. W. Peck", pp. 216–219.</ref> Graham also wrote a paper on the Erdős number, pseudonymously, as Tom Odda.<ref name="TomOdda">{{cite journal | last=Odda | first=Tom | title=ON PROPERTIES OF A WELL-KNOWN GRAPH OR WHAT IS YOUR RAMSEY NUMBER? | journal=Annals of the New York Academy of Sciences | volume=328 | issue=1 | date=1979 | issn=0077-8923 | doi=10.1111/j.1749-6632.1979.tb17777.x | pages=166–172 | bibcode=1979NYASA.328..166O | url=https://nyaspubs.onlinelibrary.wiley.com/doi/10.1111/j.1749-6632.1979.tb17777.x | access-date=2025-05-22| url-access=subscription }}</ref><ref name="RGbiblio">{{cite book | last=Butler | first=Steve | title=Number Theory and Combinatorics | chapter=A selected bibliography of Ron Graham | publisher=De Gruyter | date=2022-04-19 | isbn=978-3-11-075421-6 | doi=10.1515/9783110754216-022 | url=https://www.degruyter.com/document/doi/10.1515/9783110754216-022/html | access-date=2025-05-23 | pages=355–362}}</ref>

===Number theory===
Graham's doctoral dissertation was in [[number theory]], on [[Egyptian fraction]]s,<ref name=nice/><ref name=mg>{{MathGenealogy |id=6175}}</ref> as is the [[Erdős–Graham problem]] on whether, for every partition of the integers into finitely many classes, one of these classes has a finite subclass whose reciprocals sum to one. A proof was published by [[Ernie Croot]] in 2003.<ref>{{cite journal
 | last = Croot | first= Ernest S. III
 | year = 2003
 | title = On a coloring conjecture about unit fractions
 | journal = [[Annals of Mathematics]]
 | volume = 157
 | issue = 2
 | pages = 545–556
 | arxiv = math.NT/0311421
 | doi = 10.4007/annals.2003.157.545
 | bibcode = 2003math.....11421C
 | mr = 1973054| s2cid = 13514070
 }}</ref> Another of Graham's papers on Egyptian fractions was published in 2015 with [[Steve Butler (mathematician)|Steve Butler]] and (nearly 20 years posthumously) Erdős; it was the last of Erdős's papers to be published, making Butler his 512th coauthor.{{ran|A15}}<ref>{{cite web|url=https://www.simonsfoundation.org/2015/12/10/new-erdos-paper-solves-egyptian-fraction-problem/|title=New Erdős Paper Solves Egyptian Fraction Problem|first=Siobhan|last=Roberts|author-link=Siobhan Roberts|publisher=Simons Foundation|date=December 10, 2015}}</ref>

In a 1964 paper, Graham began the study of [[primefree sequence]]s by observing that there exist sequences of numbers, defined by the same [[recurrence relation]] as the [[Fibonacci number]]s, in which none of the sequence elements is prime.{{ran|A64}} The challenge of constructing more such sequences was later taken up by [[Donald Knuth]] and others.<ref>{{cite journal
 | doi = 10.2307/2691504
 | author = Knuth, Donald E.
 | author-link = Donald Knuth
 | title = A Fibonacci-like sequence of composite numbers
 | journal = Mathematics Magazine
 | volume = 63
 | issue = 1
 | pages = 21–25
 | year = 1990
 |mr=1042933
 | jstor = 2691504}}</ref> Graham's 1980 book with Erdős, ''Old and new results in combinatorial number theory,'' provides a collection of [[open problem]]s from a broad range of subareas within number theory.{{ran|B1}}

===Ramsey theory===
The [[Graham–Rothschild theorem]] in [[Ramsey theory]] was published by Graham and [[Bruce Lee Rothschild|Bruce Rothschild]] in 1971, and applies Ramsey theory to [[combinatorial cube]]s in [[combinatorics on words]].{{ran|A71a}} Graham gave a [[large number]] as an upper bound for an instance of this theorem, now known as [[Graham's number]], which was listed in the ''[[Guinness Book of Records]]'' as the largest number ever used in a mathematical proof,<ref name="Guiness">{{cite book |title=Guinness Book of World Records |date=1980 |publisher=[[Sterling Publishing]] |isbn=0806901683 |page=193 |edition=Rev. American |url=http://math.ucsd.edu/~fan/ron/images/record.jpg}}</ref> although it has since then been surpassed by even larger numbers such as [[Kruskal's tree theorem#TREE(3)|TREE(3)]].<ref name="PM-20171020">{{cite web |last1=Bennett |first1=Jay |title=The Enormity of the Number TREE(3) Is Beyond Comprehension |url=https://www.popularmechanics.com/science/math/a28725/number-tree3 |website=Popular Mechanics |access-date=July 9, 2020 |date=October 20, 2017}}</ref>

Graham offered a monetary prize for solving the [[Boolean Pythagorean triples problem]], another problem in Ramsey theory; the prize was claimed in 2016.<ref>{{Cite journal|last=Lamb|first=Evelyn|date=May 26, 2016|title=Two-hundred-terabyte maths proof is largest ever|journal=Nature|doi=10.1038/nature.2016.19990|volume=534|issue=7605|pages=17–18|pmid=27251254|bibcode=2016Natur.534...17L|doi-access=free}}</ref>
Graham also published two books on Ramsey theory.{{ran|B2}}{{ran|B3}}

===Graph theory===
[[File:Graham–Pollak partition.svg|thumb|upright|Partition of the edges of the [[complete graph]] <math>K_6</math> into five complete bipartite subgraphs, according to the [[Graham–Pollak theorem]]]]
The [[Graham–Pollak theorem]], which Graham published with [[Henry O. Pollak]] in two papers in 1971 and 1972,{{ran|A71b}}{{ran|A72a}} states that if the edges of an <math>n</math>-vertex [[complete graph]] are partitioned into [[complete bipartite graph|complete bipartite subgraphs]], then at least <math>n-1</math> subgraphs are needed. Graham and Pollak provided a simple proof using [[linear algebra]]; despite the combinatorial nature of the statement and multiple publications of alternative proofs since their work, all known proofs require linear algebra.<ref>{{cite book|last1=Aigner|first1=Martin|author1-link=Martin Aigner|last2=Ziegler|first2=Günter M.|author2-link=Günter M. Ziegler|doi=10.1007/978-3-662-57265-8|edition=6th|isbn=978-3-662-57265-8|pages=79–80|publisher=Springer|title=Proofs from THE BOOK|title-link=Proofs from THE BOOK |year=2018}}</ref>

Soon after research in [[quasi-random graph]]s began with the work of Andrew Thomason, Graham published in 1989 a result with Chung and [[R. M. Wilson]] that has been called the "fundamental theorem of quasi-random graphs", stating that many different definitions of these graphs are equivalent.{{ran|A89a}}<ref>{{cite journal|last=Shapira|first=Asaf|doi=10.1007/s00493-008-2375-0|issue=6|journal=Combinatorica|mr=2488748|pages=735–745|title=Quasi-randomness and the distribution of copies of a fixed graph|volume=28|year=2008|s2cid=3212684}}</ref>

[[Graham's pebbling conjecture]], appearing in a 1989 paper by Chung,<ref name="Chung Pebbling in Hypercubes">{{cite journal | last=Chung | first=Fan R. K. | title=Pebbling in hypercubes | journal=[[SIAM Journal on Discrete Mathematics]] | volume=2 | issue=4 | year=1989 | doi=10.1137/0402041 | pages=467–472}}</ref> is an [[open problem]] on the [[pebbling number]] of [[Cartesian product of graphs|Cartesian products of graphs]].<ref>{{cite journal|last=Pleanmani|first=Nopparat|doi=10.1142/s179383091950068x|issue=6|journal=Discrete Mathematics, Algorithms and Applications|mr=4044549|pages=1950068, 7|title=Graham's pebbling conjecture holds for the product of a graph and a sufficiently large complete bipartite graph|volume=11|year=2019|s2cid=204207428}}</ref>

===Packing, scheduling, and approximation algorithms===
Graham's early work on [[job shop scheduling]]{{ran|A66}}{{ran|A69}} introduced the worst-case [[approximation ratio]] into the study of [[approximation algorithm]]s, and laid the foundations for the later development of [[Competitive analysis (online algorithm)|competitive analysis]] of [[online algorithm]]s.<ref>{{cite book|last=Albers|first=Susanne|author-link=Susanne Albers|editor-last=Grötschel|editor-first=Martin|mr=2991486|pages=239–245|series=Documenta Mathematica|title=Ronald Graham: laying the foundations of online optimization|url=https://www.emis.de/journals/DMJDMV/vol-ismp/39_albers-susanne.html|year=2012}}</ref> This work was later recognized to be important also for the theory of [[bin packing]],<ref>{{cite book|last1=Garey|first1=M. R.|author1-link=Michael Garey|last2=Johnson|first2=D. S.|author2-link=David S. Johnson|editor1-last=Ausiello|editor1-first=G.|editor2-last=Lucertini|editor2-first=M.|contribution=Approximation Algorithms for Bin Packing Problems: A Survey|doi=10.1007/978-3-7091-2748-3_8|location=Vienna|pages=147–172|publisher=Springer|series=Courses and Lectures of the International Centre for Mechanical Sciences|title=Analysis and Design of Algorithms in Combinatorial Optimization|volume=266|year=1981|isbn=978-3-211-81626-4 }}</ref> an area that Graham later worked in more explicitly.{{ran|A74}}

The [[Coffman–Graham algorithm]], which Graham published with [[Edward G. Coffman Jr.]] in 1972,{{ran|A72b}} provides an optimal algorithm for two-machine scheduling, and a guaranteed [[approximation algorithm]] for larger numbers of machines. It has also been applied in [[layered graph drawing]].<ref>{{cite book|contribution=Layered drawings of digraphs|first1=Oliver|last1=Bastert|first2=Christian|last2=Matuszewski|title=Drawing Graphs: Methods and Models|editor1-first=Michael|editor1-last=Kaufmann|editor2-first=Dorothea|editor2-last=Wagner|editor2-link=Dorothea Wagner|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=2025|year=2001|pages=87–120|doi=10.1007/3-540-44969-8_5|isbn=978-3-540-42062-0 }}</ref>

In a survey article on scheduling algorithms published in 1979, Graham and his coauthors introduced a [[Notation for theoretic scheduling problems|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.{{ran|A79}} This classification has sometimes been called "Graham notation" or "Graham's notation".<ref>For a recent example, see e.g. {{cite journal|last1=Cygan|first1=Marek|last2=Pilipczuk|first2=Marcin|last3=Pilipczuk|first3=Michał|last4=Wojtaszczyk|first4=Jakub Onufry|doi=10.1007/s00453-012-9694-7|issue=3|journal=Algorithmica|mr=3160651|pages=692–714|title=Scheduling partially ordered jobs faster than <math>2^n</math>|volume=68|year=2014|doi-access=free|arxiv=1108.0810}}</ref>

===Discrete and computational geometry===
[[File:GrahamScanDemo.gif|thumb|upright=0.65|The [[Graham scan]] algorithm for [[convex hull]]s]]
[[Graham scan]] is a widely used and practical algorithm for [[convex hull]]s of two-dimensional point sets, based on [[sorting]] the points and then inserting them into the hull in sorted order.<ref>{{Cite book
  | last1 = De Berg
  | first1 = Mark
  | last2 = Cheong
  | first2 = Otfried
  | last3 = Van Kreveld
  | first3 = Marc
  | last4 = Overmars
  | first4 = Mark
  | title = Computational Geometry: Algorithms and Applications
  | url = https://archive.org/details/computationalgeo00berg_122
  | url-access = limited
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = Berlin
  | year = 2008
  | pages = [https://archive.org/details/computationalgeo00berg_122/page/n12 2]–14
  | doi = 10.1007/978-3-540-77974-2
  | isbn = 978-3-540-77973-5 }}</ref> Graham published the algorithm in 1972.{{ran|A72c}}

The [[biggest little polygon]] problem asks for the polygon of largest area for a given diameter. Surprisingly, as Graham observed, the answer is not always a [[regular polygon]].{{ran|A75a}} Graham's 1975 conjecture on the shape of these polygons was finally proven in 2007.<ref>{{cite journal
 | last1 = Foster | first1 = Jim
 | last2 = Szabo | first2 = Tamas
 | doi = 10.1016/j.jcta.2007.02.006
 | issue = 8
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 2360684
 | pages = 1515–1525
 | series = Series A
 | title = Diameter graphs of polygons and the proof of a conjecture of Graham
 | volume = 114
 | year = 2007| doi-access = free
 }}.</ref>

In another 1975 publication, Graham and Erdős observed that for [[Square packing in a square|packing unit squares into a larger square]] with non-integer side lengths, one can use tilted squares to leave an uncovered area that is sublinear in the side length of the larger square, unlike the obvious packing with axis-aligned squares.{{ran|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.<ref>{{cite book|last1=Brass|first1=Peter|last2=Moser|first2=William|last3=Pach|first3=János|author3-link=János Pach|isbn=978-0387-23815-9|mr=2163782|page=45|publisher=Springer|location=New York|title=Research Problems in Discrete Geometry|url=https://books.google.com/books?id=WehCspo0Qa0C&pg=PA45|year=2005}}</ref>

===Probability and statistics===
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 [[permutation]]s by summing, over each item, the distance between the positions of the item in the two permutations.{{ran|A77}}
They compared this measure to other rank correlation methods, resulting in the "Diaconis–Graham inequalities"
:<math>I+E\le D\le 2I</math>
where <math>D</math> is Spearman's footrule, <math>I</math> is the number of [[Inversion (discrete mathematics)|inversions]] between the two permutations (a non-normalized version of the [[Kendall rank correlation coefficient]]), and <math>E</math> is the minimum number of two-element swaps needed to obtain one permutation from the other.<ref>{{cite journal|last1=Hadjicostas|first1=Petros|last2=Monico|first2=Chris|journal=The Australasian Journal of Combinatorics|mr=3403376|pages=226–245|title=A new inequality related to the Diaconis-Graham inequalities and a new characterisation of the dihedral group|volume=63|year=2015}}</ref>

The [[Chung–Diaconis–Graham random process]] is a [[random walk]] on the integers modulo an odd integer <math>p</math>, in which at each step one doubles the previous number and then randomly adds zero, <math>1</math>, or <math>-1</math> (modulo <math>p</math>). In a 1987 paper, Chung, Diaconis, and Graham studied the [[Markov chain mixing time|mixing time]] of this process, motivated by the study of [[pseudorandom number generator]]s.{{ran|A87|}}<ref>{{cite journal|last=Hildebrand|first=Martin|doi=10.1016/j.spl.2019.04.020|journal=Statistics & Probability Letters|mr=3953053|pages=121–125|title=On a lower bound for the Chung-Diaconis-Graham random process|volume=152|year=2019|s2cid=164932860}}</ref>

===Juggling===
[[File:Ronald graham juggling.jpg|right|thumb|upright|Ronald Graham juggling a four-ball [[fountain (juggling)|fountain]] (1986)]]
Graham became a capable juggler beginning at age 15, and was practiced in juggling up to six balls.<ref name=jugObit/> (Although a published photo shows him juggling twelve balls,<ref name="Calit2" /> it is a manipulated image.<ref name=Horgan/>) He taught [[Steve Mills (juggler)|Steve Mills]], a repeat winner of the International Jugglers' Association championships, how to juggle, and his work with Mills helped inspire Mills to develop the [[Mills' Mess]] juggling pattern. As well, Graham made significant contributions to the theory of juggling, including a sequence of publications on [[siteswap]]s. In 1972 he was elected president of the [[International Jugglers' Association]].<ref name=jugObit/>

==Awards and honors==
In 2003, Graham won the [[American Mathematical Society]]'s annual [[Leroy P. Steele Prize]] for Lifetime Achievement. The prize cited his contributions to [[discrete mathematics]], his popularization of mathematics through his talks and writing, his leadership at [[Bell Labs]], and his service as president of the society.<ref name="AMS-200304"/> 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 theory|Ramsey theorists]] Klaus Leeb, [[Bruce Lee Rothschild|Bruce Rothschild]], [[Alfred W. Hales|Alfred Hales]], and Robert I. Jewett.<ref>{{cite web|url=https://www.siam.org/prizes-recognition/major-prizes-lectures/detail/george-polya-prize-applied-combinatorics|title=George Pólya Prize in Applied Combinatorics|publisher=[[Society for Industrial and Applied Mathematics]]|access-date=July 11, 2020}}</ref> 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]].<ref>{{cite web|url=http://combinatoricsinstitute.blogspot.com/2019/10/dr-ronald-graham-awarded-1993-euler.html|title=Dr Ronald Graham awarded the 1993 Euler Medal of the ICA|date=October 3, 2019|publisher=[[Institute of Combinatorics and its Applications]]|access-date=July 11, 2020}}</ref>

Graham was elected to the [[National Academy of Sciences]] in 1985.<ref>{{cite web|url=http://www.nasonline.org/member-directory/members/3000103.html|title=Ronald Graham|work=Member directory|publisher=[[National Academy of Sciences]]|access-date=July 11, 2020}}</ref> In 1999 he was inducted as an [[ACM Fellow]] "for seminal contributions to the analysis of algorithms, in particular the worst-case analysis of heuristics, the theory of scheduling, and computational geometry".<ref>{{cite web|title=Ronald L. Graham|publisher=Association for Computing Machinery|work=ACM Fellows|url=https://awards.acm.org/award_winners/graham_2060168|access-date=July 12, 2020}}</ref> He became a Fellow of the [[Society for Industrial and Applied Mathematics]] in 2009; the fellow award cited his "contributions to discrete mathematics and its applications".<ref>{{cite web|url=https://www.siam.org/prizes-recognition/fellows-program/all-siam-fellows/g|title=SIAM Fellows|publisher=[[Society for Industrial and Applied Mathematics]]|access-date=July 11, 2020}}</ref> In 2012 he became a fellow of the [[American Mathematical Society]].<ref name="AMS-Fellows">{{cite web |url=http://www.ams.org/profession/fellows-list |title=List of Fellows of the American Mathematical Society |website=[[American Mathematical Society]] |access-date=July 9, 2020}}</ref>

Graham was an invited speaker at the 1982 [[International Congress of Mathematicians]] (held 1983 in Warsaw),<ref name="AMS-20200707"/> speaking on "Recent developments in Ramsey theory".{{ran|A84}} He was twice [[Josiah Willard Gibbs Lectureship|Josiah Willard Gibbs Lecturer]], in 2001 and 2015.<ref name="AMS-20200707"/>
The [[Mathematical Association of America]] awarded him both the [[Carl B. Allendoerfer|Carl Allendoerfer Prize]] for his paper "Steiner Trees on a Checkerboard" with Chung and [[Martin Gardner]] in ''[[Mathematics Magazine]]'' (1989),{{ran|A89b}}<ref name="MAA-2013">{{cite web |url=https://www.maa.org/programs-and-communities/member-communities/maa-awards/writing-awards/carl-b-allendoerfer-awards |title=Allendoerfer Award |work=MAA Awards |publisher=[[Mathematical Association of America]] |access-date=July 9, 2020 |archive-date=July 22, 2020 |archive-url=https://web.archive.org/web/20200722154753/https://www.maa.org/programs-and-communities/member-communities/maa-awards/writing-awards/carl-b-allendoerfer-awards |url-status=dead }}</ref> and the [[Paul R. Halmos – Lester R. Ford Award|Lester R. Ford Award]] for his paper "A whirlwind tour of computational geometry" with [[Frances Yao]] in the ''[[American Mathematical Monthly]]'' (1990).{{ran|A90}}<ref>{{cite web |url=https://www.maa.org/programs-and-communities/member-communities/maa-awards/writing-awards/paul-halmos-lester-ford-awards |access-date=July 9, 2020 |title=Paul R. Halmos – Lester R. Ford Awards |work=MAA Awards |publisher=[[Mathematical Association of America]] |archive-date=June 26, 2017 |archive-url=https://web.archive.org/web/20170626200452/http://www.maa.org/programs/maa-awards/writing-awards/paul-halmos-lester-ford-awards |url-status=dead }}</ref> His book ''Magical Mathematics'' with [[Persi Diaconis]]{{ran|B6}} won the [[Euler Book Prize]].<ref>{{cite journal|title=Euler Book Prize|department=MAA Prizes Awarded in San Diego|journal=Notices of the American Mathematical Society|pages=613–614|date=May 2013|volume=60|issue=5|url=http://www.ams.org/notices/201305/rnoti-p611.pdf}}</ref>

The proceedings of the ''Integers 2005'' conference was published as a [[festschrift]] for Ron Graham's 70th birthday.<ref>{{cite conference|mr=2395797|publisher=Integers|location=Carrollton, GA|title=Proceedings of the Integers Conference 2005 in honor of Ron Graham's 70th birthday|year=2007}}</ref> Another festschrift, stemming from a conference held in 2015 in honor of Graham's 80th birthday, was published in 2018 as the book ''Connections in discrete mathematics: a celebration of the work of Ron Graham''.<ref>{{cite book|title=Connections in discrete mathematics: a celebration of the work of Ron Graham|isbn=978-1-316-60788-6|publisher=Cambridge University Press|year=2018|editor1-first=Steve|editor1-last=Butler|editor2-first=Joshua|editor2-last=Cooper|editor3-first=Glenn|editor3-last=Hurlbert}} Reviews: {{cite journal|last=Hopkins|first=David|date=June 2019|doi=10.1017/mag.2019.82|issue=557|journal=The Mathematical Gazette|pages=374–375|title=none|volume=103|s2cid=241732634}} {{cite journal|first=Daniel|last=Kleitman|author-link=Daniel Kleitman|journal=Inferences|title=Only connect|volume=5|issue=1|url=https://inference-review.com/article/only-connect|date=December 2019}}</ref>

==Selected publications==
===Books===
{{rma|B1|''Old and new results in combinatorial number theory.'' With [[Paul Erdős]]. Monographie 28, L'Enseignement Mathématique, 1980.<ref name="ronp">Review of ''Old and new problems and results in combinatorial number theory'':
* {{cite journal|title=none|journal=[[Mathematical Reviews]]|first=L. C.|last=Eggan|year=1982|mr=0592420}}</ref>}}

{{rma|B2|''Ramsey Theory.'' With [[Bruce Lee Rothschild|Bruce Rothschild]] and [[Joel Spencer]]. Wiley, 1980; 2nd ed., ISBN 978-0-471-05997-4, 1990.<ref>Reviews of ''Ramsey Theory'':
* {{cite journal|last=Li|first=Ko-Wei|journal=[[zbMATH]]|title=none|zbl=0455.05002}} Updated for 2nd ed., {{zbl|0705.05061}}.
* {{cite journal|last=Hindman|first=Neil|author-link=Neil Hindman|date=September–October 1981|issue=5|journal=[[American Scientist]]|jstor=27850688|page=572|title=none|volume=69}}
* {{cite journal|last=Graver|first=J. E.|journal=[[Mathematical Reviews]]|mr=0591457|title=none|year=1982}}
* {{cite journal|last=Faudree|first=Ralph|author-link=Ralph Faudree|date=January 1982|doi=10.1090/s0273-0979-1982-14982-5|issue=1|journal=[[Bulletin of the American Mathematical Society]]|pages=113–117|title=none|volume=6|doi-access=free}}
* {{cite journal|last=Vestal|first=Donald L.|date=December 2006|journal=MAA Reviews|publisher=[[Mathematical Association of America]]|title=Review|url=https://www.maa.org/press/maa-reviews/ramsey-theory-0}}</ref>}}

{{rma|B3|''Rudiments of Ramsey Theory.'' American Mathematical Society, 1981; 2nd ed., with [[Steve Butler (mathematician)|Steve Butler]], 2015, ISBN 978-0821841563.<ref>Reviews of ''Rudiments of Ramsey Theory'':
* {{cite journal|title=none|journal=[[Mathematical Reviews]]|first=N.|last=Hindman|year=1982|mr=0608630}}
* {{cite journal|title=none|journal=[[zbMATH]]|first=W.|last=Trotter|author-link=William T. Trotter|zbl=0458.05043}}
* {{cite journal|last=Vaseršteĭn|first=L. N.|author-link=Leonid Vaseršteĭn|date=September 1982|doi=10.1112/blms/14.5.458|issue=5|journal=[[Bulletin of the London Mathematical Society]]|pages=458–460|title=none|volume=14}}
* {{cite journal|last=Lacey|first=H. E.|author-link=Howard Elton Lacey|date=September–October 1982|issue=5|journal=[[American Scientist]]|jstor=27851705|pages=546–547|title=none|volume=70}}
* {{cite journal|journal=MAA Reviews|title=Review|publisher=[[Mathematical Association of America]]|first=Allen|last=Stenger|date=June 2016|url=https://www.maa.org/press/maa-reviews/rudiments-of-ramsey-theory}}
* {{cite journal|title=none|journal=[[Mathematical Reviews]]|first=Jerrold W.|last=Grossman|mr=3409216}}</ref>}}

{{rma|B4|''[[Concrete Mathematics|Concrete Mathematics: a foundation for computer science]].'' With [[Donald Knuth]] and [[Oren Patashnik]]. Addison-Wesley, 1989; 2nd ed., 1994, ISBN 978-0201558029.<ref>Reviews of ''Concrete Mathematics'':
* {{cite journal|last=Bressoud|first=David M.|author-link=David Bressoud|journal=[[zbMATH]]|title=none|zbl=0668.00003}} Review of 2nd ed, {{zbl|0836.00001}}.
* {{cite journal|last=Liu|first=Stanley|date=September–October 1989|doi=10.1063/1.4822863|issue=5|journal=Computers in Physics|page=106|title=From the discrete to the continuous|volume=3|url=http://www.gbv.de/dms/ilmenau/toc/513752366graha.PDF }}
* {{cite journal|last=van Lint|first=J. H.|author-link=Jack van Wijk|issue=1|journal=Zentralblatt für Didaktik der Mathematik|pages=4–5|title=Review|url=https://research.tue.nl/en/publications/concrete-mathematics-a-foundation-for-computer-science-rl-graham-|volume=90|year=1990}}
* {{cite journal|last=Strehl|first=Volker|journal=[[Mathematical Reviews]]|mr=1001562|title=none|year=1991}} Review of 2nd ed (1997), {{MR|1397498}}.
* {{cite journal|last=Pokhodzei|first=B. B.|issue=1|journal=Diskretnaya Matematika|language=ru|pages=155–156|title=Review|url=http://mi.mathnet.ru/eng/dm949|volume=3|year=1991}}
* {{cite journal|last=Jelliss|first=G. P.|date=March 1991|doi=10.2307/3619021|issue=471|journal=[[The Mathematical Gazette]]|jstor=3619021|page=117|title=none|volume=75|s2cid=65053942 }}
* {{cite journal|last=Bender|first=Edward A.|date=October 1991|doi=10.2307/2324448|issue=8|journal=[[American Mathematical Monthly]]|jstor=2324448|mr=1541984|pages=779–780|title=none|volume=98}}
* {{cite journal|last=Stenger|first=Allan|date=November 2010|journal=MAA Reviews|publisher=[[Mathematical Association of America]]|title=Review|url=https://www.maa.org/press/maa-reviews/concrete-mathematics-a-foundation-for-computer-science}}</ref>}}

{{rma|B5|''[[Erdős on Graphs|Erdős on Graphs. His legacy of unsolved problems]].'' With [[Fan Chung]]. A K Peters, 1998, ISBN 978-1568810799.<ref>Reviews of ''Erdős on Graphs'':
* {{cite journal|last=Faudree|first=R.|author-link=Ralph Faudree|journal=[[zbMATH]]|title=none|zbl=0890.05049|ref=none}}
* {{cite journal|last=Schelp|first=R. H.|author-link=Richard Schelp|journal=[[Mathematical Reviews]]|mr=1601954|title=none|year=1999|ref=none}}
* {{cite journal|last=Beezer|first=Robert A.|date=March 2000|issue=1|journal=[[SIAM Review]]|jstor=2653387|pages=143–145|title=none|volume=42|ref=none}}
* {{cite journal|last=Tutte|first=W. T.|author-link=W. T. Tutte|date=September 2000|issue=3|journal=[[SIAM Review]]|jstor=2653326|pages=548–549|title=none|volume=42|ref=none}}
* {{cite journal|last=Hobbs|first=Arthur M.|author-link=Arthur Hobbs (mathematician)|date=April 2001|doi=10.2307/2695262|issue=4|journal=[[American Mathematical Monthly]]|jstor=2695262|pages=379–381|title=none|volume=108|ref=none}}
* {{cite journal|last=Crilly|first=Tony|date=July 2001|doi=10.2307/3622075|issue=503|journal=[[The Mathematical Gazette]]|jstor=3622075|pages=375–377|title=none|volume=85|s2cid=171483616|ref=none}}</ref>}}

{{rma|B6|''Magical Mathematics: the mathematical ideas that animate great magic tricks.'' With [[Persi Diaconis]]. Princeton University Press, 2011, ISBN 978-0691151649.<ref>Reviews of ''Magical Mathematics'':
* {{cite journal|last=Rogovchenko|first=Yuri V.|journal=[[zbMATH]]|title=none|zbl=1230.00009}}
* {{cite news|last=Young|first=Jeffrey R.|date=October 16, 2011|newspaper=The Chronicle of Higher Education|title=The magical mind of Persi Diaconis|url=https://www.chronicle.com/article/The-Magical-Mind-of-Persi/129404/}}
* {{cite journal|last=Cook|first=John D.|date=November 2011|journal=MAA Reviews|publisher=[[Mathematical Association of America]]|title=Review|url=https://www.maa.org/press/maa-reviews/magical-mathematics-the-mathematical-ideas-that-animate-great-magic-tricks}}
* {{cite news|last=Howls|first=C. J.|date=November 23, 2011|newspaper=[[Times Higher Education]]|title=To create illusions, Fibonacci and algorithms are as important as sleight of hand|url=https://www.timeshighereducation.com/books/magical-mathematics-the-mathematical-ideas-that-animate-great-magic-tricks/418428.article}}
* {{cite news|last=Stone|first=Alex|date=December 10, 2011|newspaper=[[The Wall Street Journal]]|title=Pick a card, any card|url=https://www.wsj.com/articles/SB10001424052970204826704577074501731476934}}
* {{cite journal|last=Benjamin|first=Arthur|author-link=Arthur T. Benjamin|doi=10.1137/120973238|issue=3|journal=[[SIAM Review]]|jstor=41642632|mr=2985718|pages=609–612|title=Featured review|url=https://math.hmc.edu/benjamin/wp-content/uploads/sites/5/2019/06/Magical-Mathematics.pdf|volume=54|year=2012}}
* {{cite journal|last=Wiseman|first=Richard|date=February 2012|doi=10.1038/nphys2225|issue=2|journal=[[Nature Physics]]|pages=104–105|title=Just like that|volume=8|bibcode=2012NatPh...8..104W|s2cid=120357097 }}
* {{cite news|last=Davis|first=Philip J.|author-link=Philip J. Davis|date=March 18, 2012|newspaper=SIAM News|title=Tricky mathematics|url=https://archive.siam.org/news/news.php?id=1959}}
* {{cite journal|last=Ó Cairbre|first=Fiacre|date=Summer 2012|journal=Irish Mathematical Society Bulletin|pages=60–62|title=Review|url=https://www.maths.tcd.ie/pub/ims/bull69/FOC.pdf|volume=69}}
* {{cite journal|last=Castrillón López|first=Marco|date=July 2012|journal=EMS Reviews|publisher=European Mathematical Society|title=Review|url=https://euro-math-soc.eu/review/magical-mathematics}}
* {{cite journal|last=Van Osdol|first=Donovan H.|date=August 2012|doi=10.1090/noti875|issue=7|journal=[[Notices of the American Mathematical Society]]|pages=960–961|title=none|volume=59|doi-access=free}}
* {{cite journal|last=Bledsoe|first=Christie|date=April 2013|doi=10.5951/mathteacher.106.8.0637|issue=8|journal=The Mathematics Teacher|jstor=10.5951/mathteacher.106.8.0637|page=637|title=none|volume=106}}
* {{cite journal|last=Robert|first=Christian|date=April 2013|doi=10.1080/09332480.2013.794620|issue=2|journal=Chance|pages=50–51|title=none|volume=26|s2cid=60760932}}
* {{cite journal|last=Scarrabelotti|first=Jack|issue=1|journal=Australian Mathematics Teacher|page=29|title=Review|url=https://go.gale.com/ps/anonymous?id=GALE%7CA370030974|volume=70|year=2014}}
* {{cite journal|last=Brown|first=Jill|issue=2|journal=Australian Senior Mathematics Journal|page=62|title=Review|url=https://go.gale.com/ps/anonymous?id=GALE%7CA438627504|volume=29|year=2015}}</ref>}}

===Edited volumes===
{{rma|V1|''Handbook of Combinatorics.'' Edited with [[Martin Grötschel]] and [[László Lovász]]. MIT Press, 1995, ISBN 978-0-262-07170-3.<ref>Reviews of ''Handbook of Combinatorics'':
* {{cite journal|last=Wilf|first=Herbert S.|author-link=Herbert Wilf|date=March 1997|doi=10.1007/bf03024438|issue=2|journal=[[The Mathematical Intelligencer]]|pages=68–69|title=none|volume=19}}
* {{cite journal|last=Gasarch|first=William|author-link=William Gasarch|date=June 1999|doi=10.1145/568547.568551|issue=2|journal=[[ACM SIGACT News]]|pages=7|title=Review|url=https://www.cs.umd.edu/~gasarch/bookrev/30-2.pdf|volume=30|s2cid=3200815}}</ref>}}

{{rma|V2|''The mathematics of Paul Erdős.'' Edited with [[Jaroslav Nešetřil]]. 2 volumes. Springer, 1997; 2nd ed., 2013.<ref>Reviews of ''The Mathematics of Paul Erdős'':
* {{cite journal|title=none|journal=[[zbMATH]]|first=A.|last=Soifer|author-link=Alexander Soifer|zbl=0916.01022}}
* {{cite journal|title=Review|journal=MAA Reviews|publisher=[[Mathematical Association of America]]|first=Craig P.|last=Bauer|date=December 2013|url=https://old.maa.org/press/maa-reviews/the-mathematics-of-paul-erd-s-ii}}</ref>}}

===Articles===
{{reflist|group=pub}}

{{rma|A64|tw=2.5em|{{cite journal|doi=10.2307/2689243|author=Graham, Ronald L.|author-link=Ronald Graham|title=A Fibonacci-like sequence of composite numbers|journal=[[Mathematics Magazine]]|volume=37|year=1964|issue=5|url=http://www.math.ucsd.edu/~ronspubs/64_06_fibonacci.pdf|pages=322–324|jstor=2689243|mr=1571455|zbl=0125.02103
}}}}

{{rma|A66|tw=2.5em|{{cite journal|last=Graham|first=R. L.|doi=10.1002/j.1538-7305.1966.tb01709.x|issue=9|journal=[[Bell System Technical Journal]]|pages=1563–1581|title=Bounds for certain multiprocessing anomalies|url=http://www.math.ucsd.edu/~ronspubs/66_04_multiprocessing.pdf|volume=45|year=1966|zbl=0168.40703}}}}

{{rma|A69|tw=2.5em|{{cite journal|last=Graham|first=R. L.|doi=10.1137/0117039|journal=[[SIAM Journal on Applied Mathematics]]|mr=249214|pages=416–429|title=Bounds on multiprocessing timing anomalies|url=https://www.math.ucsd.edu/~ronspubs/69_02_multiprocessing.pdf|volume=17|year=1969|issue=2|zbl=0188.23101}}}}

{{rma|A71a|tw=2.5em|{{cite journal|last1=Graham|first1=R. L. |last2=Rothschild|first2= B. L. |author2-link=Bruce Lee Rothschild|title=Ramsey's theorem for {{mvar|n}}-parameter sets |journal=[[Transactions of the American Mathematical Society]]|volume=159 |pages=257–292 |year=1971 |doi=10.1090/S0002-9947-1971-0284352-8 |url=http://www.math.ucsd.edu/~ronspubs/71_04_n_ramsey.pdf|jstor=1996010|mr=0284352|zbl=0233.05003|doi-access=free}}}}

{{rma|A71b|tw=2.5em|{{cite journal|last1=Graham|first1=R. L.|last2=Pollak|first2=H. O.|author2-link=Henry O. Pollak|doi=10.1002/j.1538-7305.1971.tb02618.x|journal=[[Bell System Technical Journal]]|mr=289210|pages=2495–2519|title=On the addressing problem for loop switching|url=http://www.math.ucsd.edu/~ronspubs/71_05_loop_switching.pdf|volume=50|year=1971|issue=8|zbl=0228.94020}}}}

{{rma|A72a|tw=2.5em|{{cite conference|last1=Graham|first1=R. L.|last2=Pollak|first2=H. O.|author2-link=Henry O. Pollak|contribution=On embedding graphs in squashed cubes|mr=0332576|pages=99–110|series=Lecture Notes in Mathematics|title=Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs)|url=http://www.math.ucsd.edu/~ronspubs/72_02_squashed.pdf|volume=303|year=1972|zbl=0251.05123}}}}

{{rma|A72b|tw=2.5em|{{cite journal|last1=Coffman|first1=E. G. Jr.|author1-link=Edward G. Coffman Jr.|last2=Graham|first2=R. L.|author2-link=Ronald Graham|mr=0334913|journal=[[Acta Informatica]]|pages=200–213|title=Optimal scheduling for two-processor systems|url=http://www.math.ucsd.edu/~ronspubs/72_04_two_processors.pdf|volume=1|year=1972|issue=3|doi=10.1007/bf00288685|s2cid=40603807|zbl=0248.68023}}}}

{{rma|A72c|tw=2.5em|{{cite journal | last1 = Graham | first1 = R. L. | year = 1972 | title = An efficient algorithm for determining the convex hull of a finite planar set | url = http://www.math.ucsd.edu/~ronspubs/72_10_convex_hull.pdf | journal = [[Information Processing Letters]] | volume = 1 | issue = 4| pages = 132–133 | doi=10.1016/0020-0190(72)90045-2|zbl=0236.68013}}}}

{{rma|A74|tw=2.5em|{{cite journal|last1=Johnson|first1=D. S.|author1-link=David S. Johnson|last2=Demers|first2=A.|last3=Ullman|first3=J. D.|author3-link=Jeffrey Ullman|last4=Garey|first4=M. R.|author4-link=Michael Garey|last5=Graham|first5=R. L.|doi=10.1137/0203025|journal=[[SIAM Journal on Computing]]|mr=434396|pages=299–325|title=Worst-case performance bounds for simple one-dimensional packing algorithms|url=https://www.math.ucsd.edu/~ronspubs/74_04_one_dimensional_packing.pdf|volume=3|year=1974|issue=4|zbl=0297.68028}}}}

{{rma|A75a|tw=2.5em|{{cite journal|last=Graham|first=R. L.|author-link=Ronald Graham|title=The largest small hexagon|journal=[[Journal of Combinatorial Theory]]|series=Series A|volume=18|pages=165–170|year=1975|issue=2|url=http://www.math.ucsd.edu/~ronspubs/75_02_hexagon.pdf|doi=10.1016/0097-3165(75)90004-7|mr=0360353|zbl=0299.52006|doi-access=free}}}}

{{rma|A75b|tw=2.5em|{{cite journal|last1=Erdős|first1=P.|author1-link=Paul Erdős|last2=Graham|first2=R. L.|doi=10.1016/0097-3165(75)90099-0|journal=[[Journal of Combinatorial Theory]]|mr=0370368|pages=119–123|series=Series A|title=On packing squares with equal squares|url=http://www.math.ucsd.edu/~ronspubs/75_06_squares.pdf|volume=19|year=1975|zbl=0324.05018|doi-access=free}}}}

{{rma|A77|tw=2.5em|{{cite journal|last1=Diaconis|first1=Persi|author1-link=Persi Diaconis|last2=Graham|first2=R. L.|doi=10.1111/j.2517-6161.1977.tb01624.x|issue=2|journal=[[Journal of the Royal Statistical Society]]|jstor=2984804|mr=652736|pages=262–268|title=Spearman's footrule as a measure of disarray|volume=39|year=1977|zbl=0375.62045}}}}

{{rma|A79|tw=2.5em|{{cite journal|last1=Graham|first1=R. L.|last2=Lawler|first2=E. L.|author2-link=Eugene Lawler|last3=Lenstra|first3=J. K.|author3-link=Jan Karel Lenstra|last4=Rinnooy Kan|first4=A. H. G.|author4-link=Alexander Rinnooy Kan|journal=Annals of Discrete Mathematics|mr=558574|pages=287–326|title=Optimization and approximation in deterministic sequencing and scheduling: a survey|url=http://www.math.ucsd.edu/~ronspubs/79_03_scheduling_survey.pdf|volume=5|year=1979|doi=10.1016/S0167-5060(08)70356-X|isbn=9780080867670|zbl=0411.90044}}}}

{{rma|A84|tw=2.5em|{{cite book|last=Graham|first=R. L.|contribution=Recent developments in Ramsey theory|contribution-url=https://www.math.ucsd.edu/~ronspubs/83_01_recent_ramsey.pdf|location=Warsaw|mr=804796|pages=1555–1567|publisher=PWN|title=Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Warsaw, 1983)|year=1984|zbl=0572.05009}}}}

{{rma|A87|tw=2.5em|{{cite journal|last1=Chung|first1=F. R. K.|author1-link=Fan Chung|last2=Diaconis|first2=Persi|author2-link=Persi Diaconis|last3=Graham|first3=R. L.|issue=3|journal=[[Annals of Probability]]|jstor=2244046|mr=893921|pages=1148–1165|title=Random walks arising in random number generation|url=http://www.math.ucsd.edu/~ronspubs/87_05_random_walks.pdf|volume=15|year=1987|doi=10.1214/aop/1176992088|zbl=0622.60016|doi-access=free}}}}

{{rma|A89a|tw=2.5em|{{cite journal|last1=Chung|first1=F. R. K.|author1-link=Fan Chung|last2=Graham|first2=R. L.|last3=Wilson|first3=R. M.|author3-link=R. M. Wilson|doi=10.1007/BF02125347|issue=4|journal=[[Combinatorica]]|mr=1054011|pages=345–362|title=Quasi-random graphs|url=http://www.math.ucsd.edu/~ronspubs/89_05_quasi_graphs.pdf|volume=9|year=1989|s2cid=17166765|zbl=0715.05057}}}}

{{rma|A89b|tw=2.5em|{{cite journal|last1=Chung|first1=Fan|author1-link=Fan Chung|last2=Gardner|first2=Martin|author2-link=Martin Gardner|last3=Graham|first3=Ron|doi=10.2307/2690388|issue=2|journal=[[Mathematics Magazine]]|jstor=2690388|mr=991536|pages=83–96|title=Steiner trees on a checkerboard|url=http://www.math.ucsd.edu/~ronspubs/89_02_steiner.pdf|volume=62|year=1989|zbl=0681.05018}}}}

{{rma|A90|tw=2.5em|{{cite journal|last1=Graham|first1=Ron|last2=Yao|first2=Frances|author2-link=Frances Yao|doi=10.2307/2324575|issue=8|journal=[[American Mathematical Monthly]]|jstor=2324575|mr=1072812|pages=687–701|title=A whirlwind tour of computational geometry|url=http://www.math.ucsd.edu/~ronspubs/90_08_whirlwind.pdf|volume=97|year=1990|zbl=0712.68097}}}}

{{rma|A15|tw=2.5em|{{cite journal|last1=Butler|first1=Steve|author1-link=Steve Butler (mathematician)|last2=Erdős|first2=Paul|author2-link=Paul Erdős|last3=Graham|first3=Ron|journal=Integers|mr=3437526|page=A51|title=Egyptian fractions with each denominator having three distinct prime divisors|url=http://www.math.ucsd.edu/~ronspubs/15_04_egyptian.pdf|volume=15|year=2015|zbl=1393.11030}}}}

==References==
{{Reflist}}

==External links==
* [http://www.jacobsschool.ucsd.edu/faculty/faculty_bios/findprofile.sfe?department=cse&fmp_recid=108 Graham's UCSD Faculty Research Profile]
* [http://www.math.ucsd.edu/~ronspubs/ Papers of Ron Graham]{{Snd}} a comprehensive archive of the papers written by Ron Graham
* [http://math.ucsd.edu/~fan/ron/ About Ron Graham]{{Snd}} a page summarizing some aspects of Graham's life and mathematics{{Snd}} part of [http://www.math.ucsd.edu/~fan/ Fan Chung's website]
* {{cite web| title=Simons Foundation: Ronald Graham (1935–2020)|url=https://www.simonsfoundation.org/2016/01/11/ronald-graham/| date=January 11, 2016 | publisher=Simons Foundation}} – Extended video interview.
* [https://www.newyorker.com/culture/annals-of-inquiry/three-mathematicians-we-lost-in-2020 "Three Mathematicians We Lost in 2020: John Conway, Ronald Graham, and Freeman Dyson all explored the world with their minds"] Rockmore, Dan. (December 31, 2020) ''The New Yorker''.
*{{cite journal |last1=Buhler|first1=Joe|last2=Butler|first2=Steve|last3=Spencer|first3=Joel|date=December 2021 | title = Ronald Lewis Graham (1935–2020) | journal = [[Notices of the American Mathematical Society]] | volume = 68 | issue = 11| pages = 1931–1950| doi = 10.1090/noti2382 | url = https://www.ams.org/journals/notices/202111/rnoti-p1931.pdf?adat=December%202021&trk=2382&cat=interest&galt=none&_zs=kq3BH1&_zl=5vfV6 | doi-access = free }}
* {{Google Scholar id}}

{{Juggling}}
{{AMS Presidents|state=collapsed}}
{{Authority control}}

{{DEFAULTSORT:Graham, Ronald}}
[[Category:1935 births]]
[[Category:2020 deaths]]
[[Category:20th-century American mathematicians]]
[[Category:21st-century American mathematicians]]
[[Category:Fellows of the American Mathematical Society]]
[[Category:1999 fellows of the Association for Computing Machinery]]
[[Category:Fellows of the Society for Industrial and Applied Mathematics]]
[[Category:Graph theorists]]
[[Category:Mathematicians from California]]
[[Category:Mathematics popularizers]]
[[Category:Members of the United States National Academy of Sciences]]
[[Category:People from Taft, California]]
[[Category:Presidents of the American Mathematical Society]]
[[Category:Presidents of the Mathematical Association of America]]
[[Category:Researchers in geometric algorithms]]
[[Category:Scientists at Bell Labs]]
[[Category:University of Alaska Fairbanks alumni]]
[[Category:University of California, Berkeley alumni]]
[[Category:Rutgers University faculty]]
[[Category:University of California, San Diego faculty]]
[[Category:Deaths from lung disease]]