Ronald Graham: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
Early scheduling work
packing
Line 106: Line 106:
[[Graham's pebbling conjecture]], appearing in a 1989 paper by [[Fan Chung]], concerns the [[pebbling number]] of [[Cartesian product of graphs|Cartesian products of graphs]]. {{as of|2019}}, it remains unsolved.<ref>{{cite journal|last=Pleanmani|first=Nopparat|doi=10.1142/s179383091950068x|issue=6|journal=Discrete Mathematics, Algorithms and Applications|mr=4044549|page=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}}</ref>
[[Graham's pebbling conjecture]], appearing in a 1989 paper by [[Fan Chung]], concerns the [[pebbling number]] of [[Cartesian product of graphs|Cartesian products of graphs]]. {{as of|2019}}, it remains unsolved.<ref>{{cite journal|last=Pleanmani|first=Nopparat|doi=10.1142/s179383091950068x|issue=6|journal=Discrete Mathematics, Algorithms and Applications|mr=4044549|page=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}}</ref>


===Scheduling and approximation algorithms===
===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>
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}}</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}}</ref>
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}}</ref>
Line 246: Line 246:


{{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}}}}
{{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}}}}

{{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}}}}


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

Revision as of 22:14, 15 July 2020

For other people named Ron Graham, see Ron Graham (disambiguation).

Ronald Graham
Ronald Graham in 1998
Born
Ronald Lewis Graham

(1935-10-31)October 31, 1935
Taft, California, U.S.
DiedJuly 6, 2020(2020-07-06) (aged 84)
San Diego, California, U.S.
Alma mater
Known for
SpouseFan Chung
Awards
Scientific career
Fields
Institutions
Thesis On Finite Sums of Rational Numbers  (1962)
Doctoral advisorDerrick Henry Lehmer

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".[2]

He did important work in scheduling theory, computational geometry, Ramsey theory, and quasi-randomness.[3] He worked for many years at Bell Labs and later at the University of California, San Diego, and was president of both the American Mathematical Society and the Mathematical Association of America.

Ronald Graham juggling a four-ball fountain (1986)

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, and in 1972 was elected president of the International Jugglers' Association.[4][5][3]

Biography

Graham was born in Taft, California, on October 31, 1935,[6] the son of an oil field worker and later merchant marine. Despite his later interest in gymnastics, he was small and non-athletic.[7] 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.[1][7] As a teenager, he moved to Florida with his now-divorced mother, where he went to but did not finish high school. Instead, at the age of 15 he won a scholarship to the University of Chicago, where he learned gymnastics but no mathematics. 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 Derrick Henry Lehmer,[1] and winning a title as California state trampoline champion.[7] He left Berkeley without a degree a year later in 1955 to join the United States Air Force, and was stationed in Fairbanks, Alaska, where he finally completed a bachelor's degree in physics in 1959 at the University of Alaska Fairbanks.[1] Returning to the University of California, 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.[8] While a graduate student, he married Nancy Young, an undergraduate mathematics student at Berkeley; they had two children.[1]

Ronald Graham, his wife Fan Chung, and Paul Erdős, Japan 1986

After completing his doctorate, Graham began working in 1962 at Bell Labs and (as it later became) AT&T Labs, in New Jersey, as Director of Information Sciences. In 1963, at a conference in Colorado, he met the prolific Hungarian mathematician Paul Erdős (1913−1996),[1] who became a close friend and frequent research collaborator. (Graham later popularized the concept of the Erdős number, a measure of distance from Erdős in the collaboration network of mathematicians.)[9] 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. He divorced in the 1970s; in 1983 he married his Bell Labs colleague and frequent coauthor Fan Chung.[1]

While at Bell Labs, Graham also took a position at Rutgers University as University Professor of Mathematical Sciences in 1986, and served a term as president of the American Mathematical Society from 1993 to 1994. He became Chief Scientist of the labs in 1995.[1] He retired from AT&T in 1999 after 37 years of service there,[10] and moved to the University of California, San Diego (UCSD), as the Irwin and Joan Jacobs Endowed Professor of Computer and Information Science.[1] At UCSD, he also became chief scientist at the California Institute for Telecommunications and Information Technology.[5] In 2003−04, he was president of the Mathematical Association of America.[1]

Graham died on July 6, 2020, aged 84, in La Jolla, California.[6][11]

Contributions

Graham made important contributions in multiple areas of mathematics and theoretical computer science. He published over 350 papers[11] and six books, including Concrete Mathematics with Donald Knuth and Oren Patashnik,[B4] and the Erdős Number Project lists him as having nearly 200 coauthors.[12]

Notable topics in mathematics named after Graham include the Erdős–Graham problem on Egyptian fractions, the Graham–Rothschild theorem and Graham's number in Ramsey theory, 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 hulls. He also began the study of primefree sequences, the Boolean Pythagorean triples problem, the biggest little polygon, and square packing in a square.

As well as publishing under his own name, Graham has participated in the publications of G. W. Peck, a pseudonymous mathematical collaboration named for the initials of its members, with Graham as the "G".[13]

Number theory

Graham's doctoral dissertation was in number theory, on Egyptian fractions,[7][8] and the Erdős–Graham problem is closely related. It asked for a proof that, when the integers are partitioned into finitely many classes, one of the classes has a subset whose reciprocals sum to one. A proof was published by Ernie Croot in 2003.[14] Another of Graham's papers on Egyptian fractions was published in 2015 with Steve Butler and (nearly 20 years posthumously) Paul Erdős; it was the last of Erdős's papers to be published, making Butler his 512th coauthor.[A15][15]

In a 1964 paper, Graham began the study of primefree sequences by observing that there exist sequences of numbers, defined by the same recurrence relation as the Fibonacci numbers, in which none of the sequence elements is prime.[A64] The challenge of constructing more such sequences was later taken up by Donald Knuth and others.[16]

Ramsey theory

In connection with the Graham–Rothschild theorem in Ramsey theory, published by Graham and Bruce Rothschild in 1971,[A71a] Graham gave a large number as an upper bound for an instance of this theorem. This number was listed in the Guinness Book of Records as the largest number ever used in a mathematical proof,[17] and is now known as Graham's number, although it has since then been surpassed by even larger numbers such as TREE(3).[18]

Graham offered a monetary prize for solving the Boolean Pythagorean triples problem, claimed in 2016.[19] Graham also published two books on Ramsey theory.[B2][B3]

Graph theory

The Graham–Pollak theorem, which Graham published with Henry O. Pollak in two papers in 1971 and 1972,[A71b][A72a] states that if the edges of an -vertex complete graph are partitioned into complete bipartite subgraphs, then at least subgraphs are needed. Graham and Pollak provided a simple proof using linear algebra, and despite the combinatorial nature of the statement and despite multiple publications of alternative proofs since their work, all known proofs require linear algebra.[20]

Soon after research in quasi-random graphs began with the work of Andrew Thomason, Graham and his coauthors Fan Chung and R. M. Wilson published in 1989 a result that has been called the "fundamental theorem of quasi-random graphs", stating that many different definitions of these graphs are equivalent.[A89a][21]

Graham's pebbling conjecture, appearing in a 1989 paper by Fan Chung, concerns the pebbling number of Cartesian products of graphs. As of 2019, it remains unsolved.[22]

Packing, scheduling, and approximation algorithms

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.[23] This work was later recognized to be important also for the theory of bin packing,[24] an area that Graham later worked in more explicitly.[A74]

The Coffman–Graham algorithm, which Graham published with Edward G. Coffman Jr. in 1972,[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.[25]

In a survey article on scheduling articles 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.[A79] This classification has sometimes been called "Graham notation" or "Graham's notation".[26]

Discrete and computational geometry

The Graham scan algorithm for convex hulls

Graham scan is a widely used and practical algorithm for convex hulls of two-dimensional point sets, based on sorting the points and then inserting them into the hull in sorted order.[27] Graham published the algorithm in 1972.[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.[A75a] Graham's 1975 conjecture on the shape of these polygons was finally proven in 2007.[28]

In another 1975 publication, Graham and Erdős observed that for 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.[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.[29]

Statistics

In nonparametric statistics, a 1977 paper by Persi Diaconis and Graham studied the statistical properties of Pearson'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.[A77] They compared this measure to other rank correlation methods, resulting in the "Diaconis–Graham inequalities"

where is Pearson's footrule, is the number of inversions between the two permutations (a non-normalized version of the Kendall rank correlation coefficient), and is the minimum number of two-element swaps needed to obtain one permutation from the other.[30]

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.[31] 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. Jewett.[32] 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.[33]

Graham was elected to the National Academy of Sciences in 1985.[34] 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".[35] 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".[36] In 2012 he became a fellow of the American Mathematical Society.[37]

Graham was an invited speaker at the 1982 International Congress of Mathematicians (held 1983 in Warsaw),[11] speaking on "Recent developments in Ramsey theory".[A84] He was twice Josiah Willard Gibbs Lecturer, in 2001 and 2015.[11] The Mathematical Association of America awarded him both the Carl Allendoerfer Prize for his paper "Steiner Trees on a Checkerboard" with Fan Chung and Martin Gardner in Mathematics Magazine (1989),[A89b][38] and the Lester R. Ford Award for his paper "A whirlwind tour of computational geometry" with Frances Yao in the American Mathematical Monthly (1990).[A90][39] His book Magical Mathematics with Persi Diaconis[B6] won the Euler Book Prize.[40]

Selected publications

Books

B1.
Old and new results in combinatorial number theory. With Paul Erdős. Monographie 28, L'Enseignement Mathématique, 1980.[41]
B2.
Ramsey Theory. With Bruce Rothschild and Joel Spencer. Wiley, 1980; 2nd ed., 1990.[42]
B3.
Rudiments of Ramsey Theory. American Mathematical Society, 1981; 2nd ed., with Steve Butler, 2015.[43]
B4.
B5.
B6.
Magical Mathematics: the mathematical ideas that animate great magic tricks. With Persi Diaconis. Princeton University Press, 2011.[46]

Edited volumes

V1.
Handbook of Combinatorics. Edited with Martin Grötschel and László Lovász. MIT Press, 1995.[47]
V2.
The mathematics of Paul Erdős. Edited with Jaroslav Nešetřil. 2 volumes. Springer, 1997; 2nd ed., 2013.[48]

Articles

A64.
Graham, Ronald L. (1964). "A Fibonacci-like sequence of composite numbers" (PDF). Mathematics Magazine. 37 (5): 322–324. doi:10.2307/2689243. JSTOR 2689243. MR 1571455.
A66.
A69.
A71a.
A71b.
A72a.
Graham, R. L.; Pollak, H. O. (1972), "On embedding graphs in squashed cubes", Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs) (PDF), Lecture Notes in Mathematics, vol. 303, pp. 99–110, MR 0332576
A72b.
A72c.
A74.
A75a.
A75b.
A77.
Diaconis, Persi; Graham, R. L. (1977). "Spearman's footrule as a measure of disarray". Journal of the Royal Statistical Society. 39 (2): 262–268. doi:10.1111/j.2517-6161.1977.tb01624.x. JSTOR 2984804. MR 0652736.
A79.
A84.
Graham, R. L. (1984). "Recent developments in Ramsey theory" (PDF). Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Warsaw, 1983). Warsaw: PWN. pp. 1555–1567. MR 0804796.
A89a.
A89b.
A90.
A15.

References

  1. ^ a b c d e f g h i j O'Connor, John J.; Robertson, Edmund F., "Ronald Graham", MacTutor History of Mathematics Archive, University of St Andrews
  2. ^ "2003 Steele Prizes" (PDF). Notices of the AMS. Vol. 50, no. 4. American Mathematical Society. April 2003. pp. 462–467. Archived from the original (PDF) on December 26, 2010. Retrieved July 2, 2014.
  3. ^ a b Horgan, John (March 1997). "Profile: Ronald L. Graham – Juggling Act". Scientific American. 276 (3). Nature Publishing Group: 28–30. doi:10.1038/scientificamerican0397-28.
  4. ^ "Ron Graham Obituary". International Jugglers' Association. July 9, 2020. Retrieved July 13, 2020.
  5. ^ a b "Juggling Numbers: UC San Diego Professor Honored for Work in Applied Mathematics and Computational Science". California Institute for Telecommunications and Information Technology. May 4, 2009. Retrieved July 9, 2020.
  6. ^ a b "Ronald Lewis Graham, 2003-2004 MAA President". Mathematical Association of America. July 7, 2020. Retrieved July 7, 2020.
  7. ^ a b c d Albers, Donald J. (November 1996). "A Nice Genius". Math Horizons. 4 (2): 18–23. doi:10.1080/10724117.1996.11974993. JSTOR 25678089.
  8. ^ a b Ronald Graham at the Mathematics Genealogy Project
  9. ^ Hoffman, Paul (1998), The man who loved only numbers: the story of Paul Erdős and the search for mathematical truth, Hyperion, pp. 109–110, ISBN 978-0-7868-6362-4
  10. ^ Rabiner, Larry (February 4, 2000). "Ron Graham – A Biographical Retrospective" (PDF).
  11. ^ a b c d "The Latest: Ronald Graham, 1935–2020". American Mathematical Society. July 7, 2020. Retrieved July 7, 2020.
  12. ^ "Erdos1: coauthors of Paul Erdős, together with their coauthors listed beneath them". Erdős Number Project. Retrieved July 12, 2020.
  13. ^ Peck, G. W. (2002). "Kleitman and combinatorics: a celebration". Discrete Mathematics. 257 (2–3): 193–224. doi:10.1016/S0012-365X(02)00595-2. MR 1935723. See in particular Section 4, "The mysterious G. W. Peck", pp. 216–219.
  14. ^ Croot, Ernest S., III (2003). "On a coloring conjecture about unit fractions". Annals of Mathematics. 157 (2): 545–556. arXiv:math.NT/0311421. doi:10.4007/annals.2003.157.545. MR 1973054.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  15. ^ Roberts, Siobhan (December 10, 2015). "New Erdős Paper Solves Egyptian Fraction Problem". Simons Foundation.
  16. ^ Knuth, Donald E. (1990). "A Fibonacci-like sequence of composite numbers". Mathematics Magazine. 63 (1): 21–25. doi:10.2307/2691504. JSTOR 2691504. MR 1042933.
  17. ^ Guinness Book of World Records (Rev. American ed.). Sterling Publishing. 1980. p. 193. ISBN 0806901683.
  18. ^ Bennett, Jay (October 20, 2017). "The Enormity of the Number TREE(3) Is Beyond Comprehension". Popular Mechanics. Retrieved July 9, 2020.
  19. ^ Lamb, Evelyn (May 26, 2016). "Two-hundred-terabyte maths proof is largest ever". Nature. 534: 17–18. Bibcode:2016Natur.534...17L. doi:10.1038/nature.2016.19990. PMID 27251254.
  20. ^ Aigner, Martin; Ziegler, Günter M. (2018). Proofs from THE BOOK (6th ed.). Springer. pp. 79–80. doi:10.1007/978-3-662-57265-8_15. ISBN 978-3-662-57265-8.
  21. ^ Shapira, Asaf (2008). "Quasi-randomness and the distribution of copies of a fixed graph". Combinatorica. 28 (6): 735–745. doi:10.1007/s00493-008-2375-0. MR 2488748.
  22. ^ Pleanmani, Nopparat (2019). "Graham's pebbling conjecture holds for the product of a graph and a sufficiently large complete bipartite graph". Discrete Mathematics, Algorithms and Applications. 11 (6): 1950068, 7. doi:10.1142/s179383091950068x. MR 4044549.
  23. ^ Albers, Susanne (2012). Grötschel, Martin (ed.). Ronald Graham: laying the foundations of online optimization. Documenta Mathematica. pp. 239–245. MR 2991486.
  24. ^ Garey, M. R.; Johnson, D. S. (1981). "Approximation Algorithms for Bin Packing Problems: A Survey". In Ausiello, G.; Lucertini, M. (eds.). Analysis and Design of Algorithms in Combinatorial Optimization. Courses and Lectures of the International Centre for Mechanical Sciences. Vol. 266. Vienna: Springer. pp. 147–172. doi:10.1007/978-3-7091-2748-3_8.
  25. ^ Bastert, Oliver; Matuszewski, Christian (2001). "Layered drawings of digraphs". In Kaufmann, Michael; Wagner, Dorothea (eds.). Drawing Graphs: Methods and Models. Lecture Notes in Computer Science. Vol. 2025. Springer-Verlag. pp. 87–120. doi:10.1007/3-540-44969-8_5.
  26. ^ For a recent example, see e.g. Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry (2014). "Scheduling partially ordered jobs faster than $2^n$". Algorithmica. 68 (3): 692–714. doi:10.1007/s00453-012-9694-7. MR 3160651.
  27. ^ De Berg, Mark; Cheong, Otfried; Van Kreveld, Marc; Overmars, Mark (2008). Computational Geometry Algorithms and Applications. Berlin: Springer. pp. 2–14. doi:10.1007/978-3-540-77974-2. ISBN 978-3-540-77973-5.
  28. ^ Foster, Jim; Szabo, Tamas (2007). "Diameter graphs of polygons and the proof of a conjecture of Graham". Journal of Combinatorial Theory. Series A. 114 (8): 1515–1525. doi:10.1016/j.jcta.2007.02.006. MR 2360684..
  29. ^ Brass, Peter; Moser, William; Pach, János (2005). Research Problems in Discrete Geometry. New York: Springer. p. 45. ISBN 978-0387-23815-9. MR 2163782.
  30. ^ Hadjicostas, Petros; Monico, Chris (2015). "A new inequality related to the Diaconis-Graham inequalities and a new characterisation of the dihedral group". The Australasian Journal of Combinatorics. 63: 226–245. MR 3403376.
  31. ^ "2003 Steele Prizes" (PDF). Notices of the American Mathematical Society. 50 (4): 462–467. April 2003.
  32. ^ "George Pólya Prize in Applied Combinatorics". Society for Industrial and Applied Mathematics. Retrieved July 11, 2020.
  33. ^ "Dr Ronald Graham awarded the 1993 Euler Medal of the ICA". Institute of Combinatorics and its Applications. October 3, 2019. Retrieved July 11, 2020.
  34. ^ "Ronald Graham". Member directory. National Academy of Sciences. Retrieved July 11, 2020.
  35. ^ "Ronald L. Graham". ACM Fellows. Association for Computing Machinery. Retrieved July 12, 2020.
  36. ^ "SIAM Fellows". Society for Industrial and Applied Mathematics. Retrieved July 11, 2020.
  37. ^ "List of Fellows of the American Mathematical Society". American Mathematical Society. Retrieved July 9, 2020.
  38. ^ "Allendoerfer Award". MAA Awards. Mathematical Association of America. Retrieved July 9, 2020.
  39. ^ "Paul R. Halmos - Lester R. Ford Awards". MAA Awards. Mathematical Association of America. Retrieved July 9, 2020.
  40. ^ "Euler Book Prize" (PDF). MAA Prizes Awarded in San Diego. Notices of the American Mathematical Society. 60 (5): 613–614. May 2013.
  41. ^ Review of Old and new problems and results in combinatorial number theory:
  42. ^ Reviews of Ramsey Theory:
  43. ^ Reviews of Rudiments of Ramsey Theory:
  44. ^ Reviews of Concrete Mathematics:
  45. ^ Reviews of Erdős on Graphs:
  46. ^ Reviews of Magical Mathematics:
  47. ^ Reviews of Handbook of Combinatorics:
  48. ^ Reviews of The Mathematics of Paul Erdős:

External links

Retrieved from "https://en.wikipedia.org/w/index.php?title=Ronald_Graham&oldid=967884083"