Notices of the American Mathematical Society
Welcome to the Notices of the American Mathematical Society.
With support from AMS membership, we are pleased to share the journal with the global mathematical community.
PDFLINK |
Ronald Lewis Graham (1935–2020)
Communicated by Notices Associate Editor Emilie Purvine
Ron Graham.
Ronald Lewis Graham, known to everyone as Ron, was born on October 31, 1935, in Taft, California. After an itinerant childhood, his obvious academic talent in his early teens led to admission to a special program at the University of Chicago at 15, where he finished his high school education and started his college studies. After three years at Chicago he transferred to the University of California at Berkeley, where after one year he opted to enlist in the Air Force. Much of his service was spent stationed in Alaska. He could not be a pilot, because he was colorblind, so he was assigned work staffing communication lines at night. During the day he continued his education, receiving a degree in physics from the University of Alaska Fairbanks before returning to Berkeley at the end of his Air Force stint. He entered the graduate program in mathematics and received a PhD in 1962 with a dissertation in combinatorial number theory under the direction of Derrick H. Lehmer.
Ron was recruited to work at AT&T Research Labs in its Mathematics Research Center. Over the years (and corporate breakups and restructurings), Ron occupied a number of leadership positions, including “Chief Scientist.” While managing the Labs he assembled an extraordinary group of researchers that was at times the premier discrete mathematics research department in the world.
In 1999, Ron retired from Bell Labs and joined the Department of Computer Science and Engineering at the University of California, San Diego. For a while he chaired the department, and was also a key figure in the creation and administration of Calit2 (California Institute for Telecommunications and Information Technology). He enjoyed teaching immensely, and was voted “Teacher of the Year” by the students in the department in 2015, when he was 79.
Ron was married to Nancy Young for 19 years, with whom he had two children. In 1984 he married Fan Chung, also a mathematician. Their joint research spanned 45 years and produced more than 100 papers, making them one of the most productive pair of collaborators in discrete mathematics.Footnote1
The 1960s were something of an inflection point for (1) the emergence of computer science as an important field, going well beyond its origins in engineering and mathematics, with vast potential applicability, and (2) the emergence of combinatorics from being something of a mathematical backwater to a vibrant field with strong interconnections to other areas of mathematics and deep underlying theory. Ron had a hand in both of these developments.
Ron wrote a number of seminal papers in computer science while he was at Bell Labs. For example, he wrote a paper with Ed Coffman on job scheduling that used an algorithm for usefully sequencing a partially ordered set, two papers with Henry Pollak on partitioning graphs, with applications to telephone switching, and a paper on a fast algorithm for finding the convex hull of a set of points in the plane in time . (All three of these topics have Wikipedia pages, under “Coffman-Graham,” “Graham-Pollack,” and “Graham-Scan.”) However, one of his most important contributions was surely his forceful “cheerleading” at Bell Labs and elsewhere for computer science as an important field that deserved all sorts of resources and recognition.
In combinatorics, Ron played a critical role in nurturing its growing depth and breadth, and finding many applications. The two most frequent substantive words in the titles of his 400 papers (spanning 60 years) are “Ramsey” and “graph” (each occurring about 50 times!). These certainly indicate the core of his mathematical interests. However, the secondary words (occurring about 10 or more times) encode the striking breadth of his interests, e.g.: “Steiner,” “Scheduling,” “Codes,” “Juggling,” “Euclidean,” “Packing,” “Universal,” “Appollonian,” and “Erdős.” Most of these have strong connections to combinatorics or adjacent areas of mathematics and its applications.
Two of us have special fondness for his papers on juggling and origami (full disclosure: most had one or the other of us as a coauthor) and one of us is especially fond of “The largest small hexagon” (describing the hexagon of largest area with diameter —which is not the regular hexagon!) because he built a sandbox in that shape.
The list of honors that Ron received includes (among others) the Steele prize, the Pólya prize, and six honorary doctorates. He played leadership roles in many national organizations, e.g., being the Treasurer of the National Academy of Sciences for two terms, and President of the AMS, MAA, and the International Juggling Association. His hobbies were legion, including trampolining (professionally), table tennis (at one time he was the number one ranked player at Bell Labs), gymnastics (including one-armed handstands until later in life), learning Chinese (to near native fluency), throwing boomerangs, running, and, of course, magic and juggling.
The individual contributions below will capture many more aspects of Ron. We would like to close with three general themes.
First, many of the things for which Ron is known for grew out of his extraordinary social skills. This striking ability to interact pleasantly with almost anyone surely underlies his teaching success, his ability to promote mathematical ideas both within the field and to the general public, his ability to discover and nurture talent, and his success at the interface of mathematics and many other disciplines and pursuits. His social skills also allowed him to provide sparks and inspiration to many young mathematicians, support Paul Erdős’s itinerant lifestyle over many years, and connect Martin Gardner with numerous mathematicians.
Second, in addition to having fun with games and various diversions, Ron also approached some of them with memorable mathematical intensity. His attachment to juggling (“a physical form of mathematics” in his view) included not only the skill itself, but also being one of the originators of studying the mathematics of juggling patterns. One of the most striking aspects of this connection is that it is of deep interest to both parties: jugglers find that this perspective organizes their perception of, and development of, new juggling patterns, and mathematicians find that the analysis of juggling patterns is interesting in its own right and raises many fundamentally mathematical questions (“why are there site swaps with period and fewer than juggling balls?”). The same thing can be said for Ron’s interest in magic; his book Magical Mathematics written with Persi Diaconis DG12 took many years to write (due to the demanding schedules of its authors and the many tantalizing questions they faced and were uncovering in their writing), and is a truly beautiful collection of ideas with roots in disparate and vibrant disciplines.
Finally, Ron had a habit of pushing people (including himself) out of their comfort zones. He would describe what appeared to be an impossibly difficult question and, with a twinkle in his eye, say “How hard could it really be?” by which he meant that he obviously expected the listener to think about it. His curiosity seemed to have no bounds.
Ron Graham was an incredible colleague, friend, and mentor. He was amazingly generous with his time and talents, and had a great sense of humor. When you had a chance to talk with Ron, he would regale you with stories and anecdotes or casually reach into his bag to pull out an amazing toy or contraption. We were all extraordinarily lucky to have known him.
Phone Calls with Ron
Ron Graham, Persi Diaconis, and Ricky Jay working on juggling.
There is an old saw: “All integers are interesting; indeed, suppose not: then there is a smallest uninteresting number, and that would be pretty interesting.” Of course, this argument stinks. I was visiting Bell Labs in 1986 and had an office next door to the great Ed Gilbert (the Gilbert bound for codes, coinventor of random graphs, the Gilbert–Shannon–Reeds model for riffle shuffling, …). Ed had a file of cards, one for each integer from one to one hundred with facts about each integer on their respective card. Okay, one is interesting, two is the only even prime, three is the first odd prime, four the first square, five is a sum of two squares, …. The first uninteresting number was 38.
This is good enough for dinner-table conversation and, returning to Cambridge, I tried it out. The hostess burst into tears: “I’m turning 38 tomorrow. I knew this was going to be a nothing year and now you’ve proved it!” The search was on: beat the mathematical bushes for properties of 38. My way of solving such problems was to phone Ron.
“Hey, is there anything interesting to say about 38?”
“Sure,” he says. “It’s why we all have finite Einstein numbers.”
Readers surely know about Erdős numbers: if you have a joint paper with Erdős, your Erdős number is 1. A joint paper with someone having an Erdős number of 1 gives you a 2, and so on. At the time, the largest (non-infinite) Erdős number was 17. For many years, the Erdős connectivity graph was maintained by Ron; it’s currently the Erdős Number Project at Oakland University. Ernst Straus, an all-around terrific mathematician, was a longtime collaborator of Erdős and he was Einstein’s assistant at Princeton. Einstein gave him a paper to check, and in reading carefully, Straus found a 76 that should have been a 38. Einstein put him on the paper; so thousands of us have finite Einstein numbers. This seemed to assuage my hostess at the next dinner.
Cut to a week before Ron died. He was mostly bed-ridden and living with an oxygen machine. My job was to help keep him distracted with phone calls. I collect old books, and noticed a scientific bookseller offering a reprint of the Einstein–Straus paper (unsigned) for $520. This seemed a possible topic and I phoned Ron to kid him about buying it.
“Hey, did you ever have a joint paper with Straus?”
“Sure,” he says, and proceeds with the following.
“Can you put three points in the plane and have all interpoint distances be one?” Ron insisted I actually answer; he didn’t want me to just “play the nod,” so let me ask you to think for a second and actually answer before reading on.
“Sure,” says I. “The vertices of an equilateral triangle will work.”
“Good. Can you have four points?”
Turns out that the answer is no. Similarly, in three dimensions you can only find four points with distances one. What if you relax the condition to all distances an odd integer? Nope, in the plane it’s still three; in three dimensions, it’s still four, but in fourteen dimensions you can find sixteen points with all distances odd (and that’s best possible). Amazingly, in dimensions, you can find points with all distances odd if and only if GRS74.
“You know,” Ron said, “I told you this before.”
“No way—I’ll never forget .”
The day before he died he asked, “14?”
“Mod 16.”
I talked to Ron more or less every day for the past 47 years. Sure, some days we’d miss a call, but many days it was two or three calls; so about once a day seems right. The calls were gossipy, but usually mathematical. Even at the end he never complained, but tried to help both of us get through the day. For another report of Ron’s calls, see my “Probabilizing Fibonacci numbers” in BCH18.
Persi Diaconis is a professor of statistics at Stanford University. His email address is diaconis@math.stanford.edu.
Ron Graham at Bell Labs
Ron’s efforts at Bell Labs was some of the best mathematical modeling that I have ever known and in the outpouring of appreciations for Ron it is good to remember this part of his talent and contributions.
The problems that people in the Labs worked on often didn’t come in the form of mathematical questions. Rather, they were about how to minimize the cost of synthesizing a network, how to efficiently get a signal from point to point , how to help the Bell system be more efficient and more profitable. But in Ron’s hands, modeling these problems often led to new and exciting discoveries in discrete mathematics, in three major areas in particular: machine-scheduling, shortest networks, and loop switching.
Bomber detection
In the days before the breakup of AT&T in 1982 (into regional telephone companies), work at Bell Labs could be financed either directly by AT&T or by Western Electric (the company that manufactured telephones and associated equipment). If a branch of government wished Bell Labs to work on something, it wrote a contract with Western Electric.
In the late 1950s, Western Electric was given the contract to plan the Ballistic Missile Early Warning System to detect Soviet missiles that might come over the North Pole toward the US. There would be precious little time to prepare defenses once such missiles were detected by radar, so determining their paths in the shortest time possible was a priority. As time went on, the project tried several approaches, including the addition of more computers and varying the order and times for the different tasks. But they soon discovered anomalies: these approaches could surprisingly lead to a longer time to determine a trajectory. What was going on? They turned to Western Electric, which turned to Bell Labs.
Ron worked on this problem soon after joining the Labs in 1962. Much of this work was first published in the Bell System Technical Journal in the mid-1960s, but in 1978 the main results were popularized in Scientific American, as well as in Mathematics Today Gra78—both pieces being remarkable examples of mathematical exposition.
The Dogpatch solution
In the early 1960s, Delta Airlines had three main reservation centers, in New York, Chicago, and Atlanta. Delta wanted a private-line network connecting these centers at the lowest cost. Surprisingly, it turned out that adding a fourth dummy center (which they called “Dogpatch”) led to a more efficient and less costly system! Since 1956, mathematics researchers at Bell Labs have worked on various models of shortest connecting networks, particularly:
- •
a minimal spanning tree among given vertices that uses only the given vertices, and
- •
a Steiner minimal tree that uses the given vertices plus additional junctions whose use shortens the network.
Ron and collaborators made many contributions to understanding Steiner minimal trees. Ron and Fan Chung studied when and how the largest possible would be used. Ron, Mike Garey, and David Johnson showed in the early 1970s that the Steiner minimal tree problem was NP-complete, and Ron and Fan Chung found a series of bounds on how much shorter a Steiner tree could be than a minimal spanning tree.
It was typical of Ron Graham’s work that mathematical models led to exciting mathematical contributions that went well beyond the original question. Ron was also a co-author of several papers on the histories of both minimal spanning trees and Steiner trees.
Messages broken up and reassembled
To describe the third problem, we need to go back to a time that younger readers may not remember, when the charge for a long-distance phone call was based on the length of the call (with a minimum charge, for three minutes) and the distance between the speakers. The logic was that it could take up to three minutes to find an open route for the call to go through.
While this cost basis seemed acceptable for person-to-person calls, businesses felt it was an overcharge when dealing with computer-to-computer communication that might need only seconds. Although all of this became moot once new technologies such as communication satellites were introduced, in the mid-1960s it was a serious concern.
One formulation of the problem was as a series of intersecting loops—some local, some regional, and some national—with messages broken up into numbered pieces sent from one location to another along these loops and then reconstructed at the final destination. It was Ron who recognized that these loops could be condensed into vertices on a graph. We designed a system of labeling the vertices with -tuples made up of the symbols , , and (that stood for “Don’t care”), so that a message could move along the graph as long as the Hamming distance between labels was decreasing. This led to rich graph-theoretic results GP71, with the remaining open problems resolved by Peter Winkler.
Ron Graham with Nancy Young, with whom he was married for 19 years, and their two children Cheryl (Ché) and Marc in 1968.
Conclusion
Ron worked under me at Bell Labs from 1962 until the breakup of Bell Labs in 1983. I then went on to become one of the heads of research at Bellcore (Bell Communications Research) and Ron took over my position as head of mathematics and statistics research at Bell Labs. Throughout his time at the Labs, Ron was able to attract some of the finest mathematicians in the world to work with him. There is little doubt that throughout the 1970s, Bell Labs had the best discrete mathematics research department in the world.
Certainly, Ron will be remembered for his many contributions to mathematical research. But Ron was also a premier mathematical modeler, expositor, and educator, and his contributions to modeling and to education should be recognized and lauded along with all of his other many outstanding achievements.
Adapted from “Ron Graham at Bell Labs: Stories related by Henry Pollak,” The UMAP Journal 41 (2020), no. 3, 337–341.
Henry Pollak is the former head of Bell Labs.
Solomon A. Garfunkel is the executive director of Comap, Inc. His email address is s.garfunkel@comap.com.
Ron Graham and the Cultures of Mathematics and Bell Labs
Ron liked to say that he put people first, mathematics second, and institutions third. And he did! He did it with integrity as well as great skill, to the benefit of all three. This brief note has a few remarks about how he did it, and how that affected and reflected the culture of Bell Labs, and of mathematics.
I will not discuss Ron’s many remarkable technical achievements, which are covered by several other pieces in this collection. Nor will I write about my personal interactions with Ron. I first met him during a summer internship at Bell Labs in 1972. And I had the privilege and pleasure of chatting with him over coffee in December 2019, half a year before his unfortunate passing. He influenced my life and career to a great extent over the intervening almost half a century. But I will leave reminiscences of those interactions aside, except to say that I gained much from them, and only wish I had paid more attention to his sage advice over the decades.
It is impossible to fully appreciate Ron’s life and career without discussing his connection to Bell Labs. (In the interests of brevity, when I say Bell Labs, I will also mean AT&T Labs-Research). The AT&T trivestiture of 1995–96 led to about half of the researchers in the information, computing, and mathematical sciences areas of Bell Labs Research moving to the newly created AT&T Labs-Research. Ron played a key role in establishing this new lab, which maintained the culture, spirit, and operating procedures of the old Bell Labs. Most of his career was spent there, and he leveraged the opportunities he found there.
A key reason for Ron’s achievements and prominence was his people skills. Many mathematicians are less socially adept than other professionals, are less interested in building collaborative efforts and in publicizing their work, and are less proficient in figuring out how to select research directions for maximal effectiveness. Ron, on the other hand, excelled at all these activities. And he used his skills to help the mathematical profession, for example in gaining press coverage for mathematical breakthroughs, or gaining the attention of funding agencies. But most of all, he was extremely effective at stimulating research, by bringing people together, and by bringing interesting and relevant problems to the attention of researchers who were positioned to attack them. As part of this activity, he mentored an impressive collection of young people, many of them women and minorities.
Ron Graham greeting Jiang Zemin, the president of China, during a visit to AT&T in October 1997.
What is difficult to determine (but might be possible, by interviewing some of the old-timers while they are still around) is the extent to which Ron’s people skills were developed through interaction with the culture of Bell Labs. That culture encouraged collaboration. For example, after I joined Bell Labs as a full-time researcher, I heard from colleagues that in the annual performance reviews, each participant in a joint project received 70% of the credit. After I was promoted to department head and started taking part in these reviews, I discovered that this was not far from the truth, and was a conscious policy choice. (And I got to join in the amused chuckles when we saw how much credit various individuals took for their collaborative efforts in their reports. I also learned that there was no precise rule on credit assignment, just a strong bias towards rewarding joint work, especially when it involved other areas.) The Bell Labs culture also tolerated, and even encouraged, eccentricities, and many researchers who would likely have had difficulties dealing with the academic environment found productive niches. But these people usually needed to be nudged towards promising projects, which required a deft touch by either their colleagues or their managers. Ron excelled at these types of roles, which were not visible to the outside.
One can easily argue that even at Bell Labs, Ron was a primus inter pares in his ability to deal with the human element of research. But that ability was almost surely honed by practice in an environment that valued and rewarded such skills. And that helped Ron himself, other people, mathematics as a whole, and all the institutions he was associated with.
Andrew Odlyzko is a professor of mathematics at the University of Minnesota. His email address is odlyzko@umn.edu.
Bell Labs Days
I am profoundly grateful to Ron Graham; to have had the chance to know such a remarkable person and to be one of his friends.
Ron was a student of Derrick Henry Lehmer at UC Berkeley, finishing his PhD in 1962. His thesis was in combinatorial number theory: “Finite sums of rational numbers,” including problems on Egyptian fractions. Ron went directly from graduate school to Bell Laboratories in Murray Hill, New Jersey, joining the Mathematical Sciences Research Center. The mathematics in the center included coding theory, queueing theory, and information and communication theory, all fields started at Bell Labs. It also had discrete mathematics, statistics, optimization, and later theoretical computer science, algorithms, and complexity. Ron achieved success in modeling various practical problems, including bounding the magnitude of multiprocessor scheduling anomalies, as described in the contribution of Henry Pollak. He became a supervisor, and later head of the Discrete Mathematics department. The fields of discrete mathematics, graphs, and networks assumed increasing prominence, as AT&T switched from analog to digital transmission.
I was hired at Bell Labs at Murray Hill in 1974 in a development area, the Business Analysis Systems Center. My first day at work, the US government filed an antitrust suit against AT&T. It was then a vertical monopoly, with manufacturing (Western Electric), local phone service (Bell Operating Companies, serving 80 percent of the US population), long-distance service (AT&T Long Lines), and research and development (Bell Labs). It had one million employees. I was told: “Someday that antitrust suit will be a problem, but not for a while.”
I hoped to get into the math center. In 1975, Andrew Odlyzko joined Ron Graham’s department in the Mathematics and Statistics Research Center. In the period 1975–1980, I wrote quite a few papers with Andrew in analytic and computational number theory, while also doing independent work. I internally reviewed a paper of Ron’s with Paul Erdős; for external release, papers required independent review by a separate area of Bell Laboratories.
I was very fortunate to be able to transfer to Ron Graham’s department in the Math Research Center in 1980. It was the best thing that ever happened to me. It brought opportunities to work on important problems, including complexity problems in theoretical computer science, new methods in mathematical programming and optimization, and the development of Ingrid Daubechies’s wavelets in signal analysis. For a problem solver, it was paradise. In the Math Center, Henry Landau ran a math seminar that brought in speakers from inside and outside Bell Labs that had terrific math problems. Neil Sloane organized a course on Lie Algebras, needed for his work with John Conway. It had wonderful summer visitors: Ron recruited talented graduate students from MIT, and outstanding undergraduates as summer interns.
Ron was key to making this environment what it was. He was able to be playful and light, in the middle of more serious things. Early on, I attended a party for a visiting speaker at Ron’s house. The house, on the skyline of the first Watchung mountain, had an incredible view for many miles to the south. Ron had a large trampoline set up in the backyard at the edge of a very steep hill, with ten foot high string netting surrounding it. The house had an Olympic-sized indoor swimming pool, put in by the previous owner. Ron had a large set of file cabinets organizing all the projects he was working on, the house was extremely neat. Like everything else about Ron, it had style.
Ron mentored me professionally. He gave me many opportunities, and if I succeeded he gave me more opportunities. He got me appointed to serve on various AMS committees and the MAA governing board as a representative from industry, and to help run part of an AMS Research Conference. He asked me to mentor visiting graduate students. In the 1980’s, these included Johan Håstad and Günter Ziegler. Later, I mentored summer interns, including Jim Propp, Eric Rains, Chris Skinner, Kannan Soundarajan.
In 1982, the antitrust suit against AT&T was settled, with AT&T agreeing to be broken up. The long-distance and manufacturing parts were split off from the Bell Operating Companies. The mathematicians were split: many went to the new operating companies version of Bell Labs, named Bellcore, in Morristown, NJ, including Henry Pollak, who moved to head up the new mathematics group there; Fan Chung moved to Bellcore as a manager.
Ron Graham served as Director of the Mathematics and Statistics Research Center from 1983 to1988. He then moved to an adjunct director position which was created for him. Under Ron’s direction, the Center was a happy place where several major discoveries occurred, including Narendra Karmarkar’s interior-point linear programming algorithm and work of Shepp, Vardi, and Kaufmann on the EM algorithm for Positron Emission Tomography.
Ron deftly used publicity. He had contacts with Martin Gardner at Scientific American and with science reporters at the L.A. Times and the New York Times. The appearance of the Karmarkar Algorithm on the front page of the New York Times (below the fold) on November 19, 1984, drew the attention of AT&T senior management. I went with Ron to report on these developments to Arno Penzias, the vice president for research, to evaluate their possible patentability (patent attorneys were present). Patent law had recently been broadened to include algorithms, applied to a specific technical purpose or process. I wrote some of the patent applications, leading to three patents granted in the period 1988–1990.
One of Ron’s achievements at Bell Labs was to create an international community and a central location for discrete mathematics. Part of it was based on his wide circle of friends in computer science (Don Knuth), in combinatorics (Richard Stanley), and in statistics (Persi Diaconis). Part of it was based on the web of connections around Paul Erdős. Ron did a great service to mathematics in collecting Paul’s vast list of unsolved problems, adding some of his own, recorded during Paul’s many visits. He and Paul wrote the book Old and New Problems and Results in Combinatorial Number Theory in 1980. He and Fan Chung wrote Erdős on Graphs: His Legacy of Unsolved Problems in 1998.
Ron arranged for Bell Laboratories to be a way station where Paul Erdős was always welcome. Before 1971, Paul traveled with his mother, staying in a boardinghouse near the Labs during his visits. After Erdős’s mother died, Ron supplied a supportive structure that helped Paul maintain his extraordinary life during this difficult period. Ron kept a collection of Paul’s papers and maintained a bank account for Paul to deposit honoraria, pay expenses, and give out prizes to solvers of his problems. He also helped manage Paul’s large correspondence. He kept a room in his home in Watchung for Paul to stay and do mathematics, along with Fan Chung.
Ron Graham with Fan Chung in China.
In 1995, AT&T made a second divestiture, exiting the computer business, retaining the long-distance and wireless part as AT&T, and splitting off the manufacturing part as Lucent Technologies. Lucent retained Bell Laboratories as its research and development part, and the AT&T part opened a small research facility named “AT&T Labs-Research,” which initially rented space at Murray Hill, and later moved to Florham Park, New Jersey, a few miles away. Both sides wanted all of the mathematicians, and Ron helped manage the division of groups.
Ron headed the group moving to AT&T Labs-Research, taking many of the well-known people to establish an initial reputation for the new research lab. Important developments under Ron’s watch at AT&T Labs included space-time codes for wireless developed by Vahid Tarokh, Nambi Seshadri, and Rob Calderbank, and good error correcting codes for quantum computation found by Rob Calderbank, Eric Rains, Peter Shor, and Neil J. A. Sloane.
At the end of his time at AT&T Labs-Research, Ron became Chief Scientist, and had more time for research. A project on Apollonian circle packings which involved geometry and number theory was started by the statisticians Colin Mallows and Allan Wilks. I joined them, Ron, and his summer visitor Catherine Yan. This work eventually expanded into four large joint papers.
Only after I left Bell Labs did I fully appreciate how exceptional and wonderful an environment it was. As a mentor, Ron had a coaxing style of talking which encouraged people. He would tease me for lack of initiative, saying: “I used to think I was indecisive, but now I am not so sure.” He also told me “Life is juggling.” I watched Ron’s actions, and he always seemed to do good things for others, and for the profession of mathematics.
Jeffrey C. Lagarias is a professor of mathematics at the University of Michigan. His email address is lagarias@umich.edu.
A Concrete Friendship
I first met Ron Graham at the SIAM 1967 fall meeting in Santa Barbara, where he was one of the invited speakers. We happened to be sitting next to each other during one of the early talks. I was multitasking, not only listening to the speaker but also starting to read some galley proofs that I’d just received, because I guess I didn’t find the particular topic especially compelling. It turned out that Ron was into multitasking too. Furthermore he was a much better proofreader than I: looking over my shoulder, he caught a big error that I had missed—my name had been misspelled! We’ve been good friends ever since, seeing each other dozens of times.
One particularly memorable occasion, early on, was in the spring of 1972 when he visited Stanford. I was hosting a weekly combinatorial seminar at my home, and Ron was the featured speaker on April 17. He spoke first about his joint work with Henry Pollak on address labels for loop switching GP71, now known as the Graham–Pollak theorem, and then came a special treat: he had brought dozens and dozens of lacrosse balls with him, and he gave everybody a hands-on lesson about how to keep three balls in the air! We captured some of this activity on film, and you can watch it today, because our home movie has now been permanently archived.Footnote2
The authors of Concrete Mathematics GKP94, Donald Knuth, Ron Graham, and Oren Patashnik, in 1999.
Ron came to Stanford for longer stays in 1979 and 1981, in order to teach Concrete Mathematics, a course that I had introduced in 1970. (His visit gave me some much-needed time off to get TeX up and running.) His lectures turned out to be enormously popular—so much so that the students decided to have annual reunions for several years afterwards. Later, when Oren Patashnik’s lecture notes had been made into a book (Concrete Mathematics GKP94), Ron taught the material at Princeton and San Diego, and everybody now has an opportunity to experience his magic touch by reading those notes.
Speaking of magic, I often saw him together with Persi Diaconis; but I’ll let Persi write about that. We continued to discuss beautiful mathematics with him right up until he passed away.
Ron was a universal combinatorialist and a great communicator and networker. Since he worked for the telephone company, he would often phone me to discuss problems of mutual interest. In this way he must have multiplied the productivity of hundreds of other mathematicians.
It was indeed a special privilege to have known Ron Graham, and to have learned from him time and again how to proceed when I was stuck on a problem.
Donald E. Knuth is a professor emeritus of computer science at Stanford University.
A Love for Numbers
Ron Graham with Paul Erdős, Fan Chung, and Richard Kadison.
One of Ron Graham’s favorite topics concerned unit fractions, popularly known as Egyptian fractions. These are numbers of the form , where is a positive integer. The game is to represent a given rational as the sum of distinct unit fractions. It has been known since Fibonacci that the greedy algorithm (of choosing the largest unit fraction not already used keeping the running sum at most equal to the target) always terminates. It has been asked if the same holds if we have a rational with an odd denominator and one uses the greedy algorithm with unit fractions of odd denominator. Ron proved that at least there is some representation with odd denominators. Ron also gave a necessary and sufficient condition for a representation to exist with square denominators: any rational can be so represented provided it is in . Elementary number theory has an ancient history including many problems (and the topic of unit fractions may hold the record for its antiquity) which have fallen askance from the grand arbiters of mathematical taste. Ron used to gently quote André Weil who dismissed unit fractions as somehow being a wrong turn in the development of number theory. Nevertheless, even without official blessings from on high, the subject has flourished.
Ron worked on many number-theoretic problems, most with a combinatorial flavor. For example, Apollonian circle packings GLM03, Beatty sequences, and Ramsey-type problems (such as Szemerédi’s theorem), just to drop a few names. His extensive 1980 monograph with Paul Erdős Old and New Problems and Results in Combinatorial Number Theory EG80 is both exalting and exhausting. Open it to any page and attractive problems come to life begging to be investigated. In this way it resembles Richard Guy’s Unsolved Problems in Number Theory; Guy is another wonderful mathematician that we lost in 2020.
In his career at AT&T Bell Labs, Ron built the finest discrete math group in the country. Among the famous number theorists there were Jeff Lagarias, Andrew Odlyzko, Peter Shor, Neil Sloane, and many others. Ron provided instrumental advice in getting the journal Integers off the ground and was an original board member of the Number Theory Foundation, active in this until his death. In the preface for the festschrift for Ron’s 80th birthday BCH18, the editors quoted Ron on how he accomplishes so much: “There are twenty-four hours in the day, and if that’s not enough, there are also the nights.”
Carl Pomerance is a professor of mathematics at Dartmouth College. His email address is carl.pomerance@dartmouth.edu.
Ron Graham’s AMS Service
Ronald L. Graham was the 52nd president of the American Mathematical Society, just after Michael Artin and just before Cathleen Morawetz. He ran as a candidate in the first contested AMS presidential election in 1991. (Stephen Smale was the other candidate.) In his 1991 Notices nomination article, Gian-Carlo Rota wrote,
Graham’s characteristic quality is an indefatigable activity, both in the cause of mathematics, and on behalf of its applications. …Graham is one of the few mathematicians whose influence and leadership are acknowledged and appreciated in the scientific community at large, as well as among mathematicians.
Graham’s involvement with the Society started well before he became president. He was elected to the AMS Council in 1978, to its Executive Committee (EC) in 1980, and to two terms on the Board of Trustees (BT), serving 1982–1991.
During Graham’s time as Trustee, one concern of AMS leadership was to make the Notices more mathematically relevant. In Allyn Jackson’s 2005 article, “Ten Years of the “New” Notices,” she wrote:
During the 1980s, the Notices initiated a series of so-called “Special Articles,” with Ronald Graham as editor; later on Jeffrey Lagarias took over. These were expository mathematical articles, and the series featured some real gems.
In 1984, the Long Range Planning Committee (LRPC) was created as an advisory committee to the EC and BT. One of its first charges was to “suggest a number of different management plans to improve the operation of the Society.” Graham served on the original LRPC (chaired by Melvin Hochster) and many of the recommendations in their initial report were adopted immediately.
It was also during Graham’s time as Trustee that the Journal of the AMS was planned as the premiere research outlet of the Society. It launched in 1988, the Centennial of the AMS, with Michael Artin as Chief Editor and Graham among the Associate Editors.
Later, the period 1992–1995 during which Graham served as President Elect, President, and then Past President was a time of action and change for the Society. As he wrote in his candidate’s statement in 1991,
In recent years the activities of the AMS have begun to expand beyond their traditional boundaries, moving from an earlier, almost exclusive, focus on considerations of mathematical scholarship and research into a broad spectrum of current issues.
During the years 1992–1995 the Council instituted the policy committee structure to handle its expanding focus on Science Policy, Education, Publications, Meetings and Conferences, and the Profession; the Notices was completely redesigned to include high-quality exposition of frontiers of mathematical research; JMM 1995 was moved from Denver in protest after Colorado’s passage of an anti-gay rights amendment in 1991; the Council drafted and adopted a set of ethical guidelines and endorsed a statement against sexual harassment.
After his presidency, Graham continued serving on AMS committees for prizes, speakers, and other activities. Respected for his contributions by both the math research and math education communities, Graham became president of the Mathematical Association of America in 2003, the same year he was awarded the Steele Prize for Lifetime Achievement by the AMS.
I met Ron Graham in 1979 at the first conference I ever attended and at many more over the years. It was certain that if he and Fan were at a meeting, it was going to be interesting. I finally got a chance to collaborate with Ron in 2019 when an email arrived during my summer vacation: he thought he knew how to settle a question in a paper Juan Auli and I had posted, related to work Ron had done with Fan. Juan and I had the great pleasure of corresponding with him about it over the next few months.
My favorite story is from JMM 2015 in San Antonio, in the afternoon of the first day of the conference. The prestigious Gibbs Lecture was scheduled for 8:00 p.m. that night. But the speaker had suddenly taken ill. What to do, cancel the lecture? David Vogan (president then) noted that Ron Graham was at the meeting and he’d given a Gibbs Lecture in 2001, so perhaps he’d do it again? You can’t ask someone to give a Gibbs Lecture at the last minute. But David asked and Ron agreed and, not surprisingly, his second Gibbs Lecture, “Mathematics and computers: problems and prospects,” was a hit.
Carla Savage is a professor emerita of computer science at North Carolina State University. Her email address is savage@ncsu.edu.
Hungarian Connections
Remembering Ron, there are many things I could and perhaps should talk about. We worked in almost the same field, and so our paths crossed often, even intertwined a few times. It would definitely be appropriate to talk about our joint research (in particular, in the style of Paul Erdős and Ron Graham, about the problems and conjectures that remained open); but I don’t want to go into mathematics. I could talk about our editorial work on the Handbook of Combinatorics GGL95 (with Martin Grötschel as a third member of the team), where his excellent taste, the breadth of his mathematics, and his familiarity with virtually all persons in the mathematical community were an invaluable basis of our work.
What I want to describe here is one commitment of his life, which is perhaps less known; nevertheless, this may be of math-historical significance. This is his support of mathematical research behind the Iron Curtain, in particular in Hungary.
Hungarian mathematics and Ron Graham were connected in the first line by Paul Erdős, who was often called the “ambassador at large” of the Hungarian mathematical community. Ron handled Paul’s finances, correspondence, and bureaucratic chores. Paul stayed with Ron quite often, producing many important joint papers.
But Ron was a great promoter of all Hungarian mathematicians working in combinatorics and related areas. I have benefited from his help enormously. He arranged research invitations for many of us, short term and long term, and organized lecture tours. During my first stay in the US as a postdoc at Vanderbilt University, he organized a car trip for me and my family to California and back, stopping to give a talk at as many math departments as was reasonable. Needless to say how important (even overwhelming) it was to meet many of the mathematicians whom I have known by fame, and to see the famous campuses of UCLA, Berkeley, and other universities (not to speak about the beautiful landscapes).
He was very understanding and helpful in solving personal problems for several Hungarian mathematicians, and often hosted us in his home during shorter visits at Bell or at nearby universities. At one occasion I remember, six Hungarians stayed under his roof (including me and my family).
He was one of the founding editors of Combinatorica, a journal of the Bolyai Society (now jointly owned with Springer), edited and printed in Hungary. This was launched back in 1980, during the Cold War, and such a journal provided a very important bridge between science in the East and West. Ron’s role as an Advisory Editor was instrumental in establishing the authenticity of Combinatorica in the US and elsewhere in the West.
At one of his visits in Budapest, perhaps in 1977, he brought programmable calculators as presents for some of us. At that time, they were very new and amazing, and of course not available in Hungary at all (I think even in the US they were more than just ordinary presents). I am not sure if I ever told him this, but it is true: half a year later this little calculator did provide significant help in my research.
Ron’s influence on Hungarian mathematicians went way beyond professional interactions. At a small party during his first visit in Hungary, in 1969, he took out several juggling balls from his bag and began to teach us to juggle. I remember what an excellent teacher he was, breaking down the difficult movements into simple steps. Myself, I never could learn to stably juggle more than three balls (maybe because he left Budapest the next morning, not offering more guidance), but some of the Hungarian mathematicians became professional-level jugglers due to a fashion started by Ron.
Let me conclude with a very personal memory. Ron visited me in Szeged, and he stayed in our small apartment for a night. My second daughter, perhaps four years old at the time, offered him a deal: if he shows a one-hand stand, she shows a somersault in return. A fair deal, accepted and performed.
Ron Graham demonstrating a one-armed handstand.
László Lovász is a professor of mathematics at the Alfréd Rényi Institute of Mathematics. His email address is lovasz@caesar.elte.hu.
Ron and Ramsey
It was high summer of 1973 in Keszthely, Hungary. An unusually large meeting “Finite and Infinite Sets” was held there in Hotel Helikon from June 25 till July 1, on the occasion of Paul Erdős’s 60th birthday. It was an excellent meeting by any standards then and today too. It is instructive to page through its three-volume proceedings HRS75: totaling 1550 pages, containing papers by Rado, Tutte, de Bruijn, Straus, Berge, Galvin, Rudin, Guy, Selfridge, Hilton, McKenzie, Kleitman, Kunen, Milner, and Neumann-Lara, to name just a few. Twelve papers coauthored by Erdős (including a joint paper with Lovász which inaugurated the Lovász Local Lemma), three papers by Shelah, four papers by Hajnal, and three papers by Laver, to list just a few contributions. And also three papers by Ron Graham all related to Ramsey with a total of more than twenty papers dealing with Ramsey-type problems.
This was the meeting which for many years set high standards for universal combinatorial conferences which were held in the 70s and 80s in France, Czechoslovakia, Hungary, Canada, and elsewhere. It was the event of the year.
One of my strong memories of the meeting is a tall athletic man who excelled at everything. His name was known to me as well as some of his work (even in that pre-email and pre-internet age). But there he was: running, juggling, tossing frisbees, and showing tricks in everything from photography to magically handling an overhead projector (as far as I remember there wasn’t a trampoline there). This was Ron Graham at his best, legendary already at that time. There we met for the first time.
My memory is vivid even now years later, when in many meetings and collaborations I have seen that this youthful engaged style was Ron Graham’s modus operandi. And later we all learned that many of these activities were not mere hobbies but professional-level acts. What seemed to be easy and what Ron liked to display in his laid-back style was in fact hard learned and hardcore. I believe this was symptomatic of his mathematics too. Ron aimed for substantial and hard, yet concrete, problems. He was a problem killer with an easy style. I still hear his “take it easy Jarik”—how helpful this was! He surrounded himself with very good people and aimed for depth and quality. In fact he was a very concrete mathematician in the style of the famous textbook GKP94.
I have been fortunate to work with Ron on papers and books mostly related to Ramsey’s Theorem and its variations. Ramsey’s Theorem is a universal mathematical principle often summarized by Ron as “complete disorder is impossible.” This was perhaps Ron’s favourite, if not key, area. In fact during his time, Ramsey theory emerged as a “theory” from a mere particular collection of statements of “Ramsey-type” (due to van den Waerden, Schur, Hilbert, Rado, and others). In this development, the above Keszthely meeting had an important crystallizing role and Ron Graham’s influence was pivotal. This was particularly true for structural Ramsey theory where the starting group of researchers was small. See the preface and the selection of topics covered by GRS90, the book which became a standard reference for this emerging field.
In this development a particular place was assumed by the Hales–Jewett Theorem HJ63 and the Graham–Rothschild Theorem GR71. These are strong statements which found many applications and serve as a tool for proving many Ramsey-type statements. In particular, they led to a solution of Rota’s conjecture (which is the analog of Ramsey’s Theorem for finite vector spaces) by Graham, Leeb, and Rothschild GLR72. All five people involved in these early results received the inaugural Pólya Prize in 1971.
These results led to many papers since and blossomed into a whole theory. Today we seem to be witnessing a renaissance of the field in the context of topological dynamics, functional analysis, model theory, and, of course, combinatorics. In 2016, there was even a meeting celebrating 50 years of the Hales–Jewett Theorem in Bellingham.
I cannot resist the temptation to try to outline the mathematical meaning of these results. Ramsey’s Theorem guarantees certain regularity in large structures. For graphs this regularity is a complete graph or an empty graph. Ramsey’s Theorem is in fact a general combinatorial principle which is useful across mathematics and the theory of computing. Some 50 years later Hales–Jewett and Graham–Rothschild found another such principle, this time both combinatorial and geometrical. It is possible to sketch it as follows.
Think of a finite set as an alphabet, for example . The product set is then just a set of vectors with each . Alternatively we may view as a geometric object: is the -dimensional cube (or rather -cube) with sides indexed by . Thus is like the popular Rubik’s cube, is a square lattice like in the game tic-tac-toe. In this way may be viewed as a board for a -dimensional version of this game. In fact this was one of the motivations of the original paper HJ63. As in tic-tac-toe, we are looking for lines, horizontal, vertical, diagonal, and this may be defined for any -dimensional cube and more generally we can speak about -dimensional subcubes of an -dimensional cube. One can express lines and -dimensional subcubes concisely as parameter words (a term coined by Graham–Rothschild) where parameters indicate which coordinates are “moving.” (In a square grid the lines have the form , and for the diagonal.) The exact definition is a bit technical but it confirms the above intuition. And this is all that is needed in order to state the result of Graham and Rothschild GR71.
For every choice of alphabet and positive integers there exists such that whenever the set of all -dimensional subcubes of is partitioned in two parts then one of the parts has to contain an -dimensional -subcube with all its -dimensional -subcubes belonging to one of the classes of the partition.
(Recall that Ramsey’s Theorem speaks about subsets instead of subcubes. The Hales–Jewett Theorem corresponds to , .)
Ron Graham juggling in his office in 1988.
It is perhaps surprising that such a seemingly technical result plays such an important role. But this is like Ramsey’s Theorem itself: it is a combinatorial principle which fits in diverse situations and assumptions. The Graham–Rothschild Theorem is a far-reaching generalization of Ramsey’s Theorem, providing a proper setting for van der Waerden’s Theorem and, as was realized later, it yields a “dual” form of Ramsey’s Theorem. This inspiration lives on.
The mathematics of Ron Graham is important and it spans many diverse areas. But still I think that Ramsey theory was closest to his heart. It was also the topic of Ron’s invited lecture at ICM 82 (held in Warsaw 1983) Gra84. Ramsey theory was also dear to Paul Erdős as witnessed by the 2-volume set Mathematics of Paul Erdős where it occupies a whole chapter (GNB13; see also GN97). In fact these volumes, which were assembled under the guidance of Paul Erdős himself, contain many pages written by the editors reflecting a long experience of collaboration with Erdős.
Ron was a public figure and a well-known mathematician, often representing mathematics as a whole. This was nicely documented recently by an article in The New Yorker.Footnote3 But I want to add yet another aspect of Ron’s personality. I believe Ron Graham was a patriot, in a very good and decent sense. He liked Bell Labs very much; he liked his country. Perhaps this was one of the factors in why he had such a keen interest in the development of friendship on the other side of the Iron Curtain. This interest was of course motivated by mathematics and it was forged by P. Erdős and the excellence of Hungarian combinatorics. But there was much more on a personal and, yes, human level—he really tried to be helpful. He encouraged us and served as a bridge to the world. And this was in those times when there were not many bridges at all, and it needed courage. It would take too long to illustrate this. Let us just mention that he helped to establish DIMATIA (as a “European DIMACS”), steadily invited people to Bell Labs, communicated about chances and possibilities, and simply spread information and books.
There were no obstacles or curtains for Ron. In this he is a great role model, and this is the lasting legacy of his personality. He is and will be remembered by many.
Jaroslav Nešetřil is a professor of mathematics at Charles University. His email address is nesetril@iuuk.mff.cuni.cz.
A $1000 Challenge
Ron Graham’s indirect influence on my mathematical life has been enormous, since he had a profound influence on the whole of combinatorics. But he had a more direct influence in at least three ways.
The first of these was through the book Ramsey Theory GRS90, or as many combinatorialists think of it, Graham-Rothschild-Spencer. Many results (and associated problems) that were to become lifelong interests, such as van der Waerden’s Theorem, Szemerédi’s Theorem, the Hales-Jewett Theorem, and Hindman’s Theorem, and more importantly the techniques of proof that were associated with them, which I first learned of from this book as a PhD student. The book played an important role in turning Ramsey theory from a collection of isolated pretty results into a more coherent whole. There is a suggestion in the book that it was with the Hales-Jewett Theorem that Ramsey theory became Ramsey theory and not just a collection of Ramseyian theorems, but a strong case could be made for saying that it was this book that played that role.
Ron Graham demonstrating a large Rubik’s cube to C. K. Cheng, Joel Spencer, and Kevin Milans at the Connections in Discrete Mathematics conference in 2015.
The second direct influence was through his paper “Quasi-random graphs,” written with Fan Chung and Richard Wilson CGW89, which defined several different notions of quasirandomness for graphs (similar to Andrew Thomason’s notion of “jumbled” graphs), and proved that they were all equivalent. This was useful for all sorts of reasons. Sometimes it was for the reason that any equivalence is useful: one may wish to use one property but find that it is easier to verify a different, equivalent property. Here, for example, one property is that all small induced subgraphs have roughly the same density, which on the face of it would take an exponential amount of time to verify, but an equivalent condition is that the second largest eigenvalue of the adjacency matrix is small, which can be verified with an efficient algorithm. It was also useful because graphs that arise in deterministic contexts are often quasirandom, and the theory of quasirandomness immediately gives us a great deal of information about any such graph. Finally, there are now several proofs that use a two-case argument: either a structure is quasirandom, in which case we can analyse it as though it were random, or it is not, in which case we can exploit some kind of “bias.”
As that last sentence suggests, the theory of quasirandomness has been extended to several other combinatorial structures, which brings me to the third influence that Ron Graham had on me. One of my cherished memories is of walking up to receive a cheque for $1000 from him for obtaining a quintuply exponential bound for the van der Waerden number (the money had been offered for a tower-type bound or better), which followed from bounds I had recently obtained for Szemerédi’s Theorem. The occasion was the Erdős memorial conference in 1999 in Budapest. I had understood that the etiquette was that one did not cash such cheques, so to Ron’s surprise (as I later learned) I never did. An essential part of my proof was the formulation of a suitable notion of quasirandomness for sets of integers. There was already such a notion, due to Chung and Graham, suitable for the case of progressions of length 3, so I did not need to start from scratch: rather, my task was to find a suitable generalization that would allow me to deal with longer progressions. Ever since then, the notion of quasirandomness, in one form or another, has been central to my research.
I have talked here about Ron’s mathematical influence. I did not meet him all that often, but he was always extremely friendly when I did, and always keen to talk mathematics and share the latest problems that interested him. The last occasion that this happened was at the Joint Mathematics Meeting in Seattle in 2016. He was a towering figure in combinatorics and will be greatly missed, both mathematically and personally.
Tim Gowers is a professor of combinatorics at the Collège de France. His email address is W.T.Gowers@dpmms.cam.ac.uk.
Ron and the Magic of Math
Most Americans have heard of the parlor game “Six Degrees of Kevin Bacon,” which begins with the premise that everyone who is anyone in Hollywood can be linked to the actor Kevin Bacon in six or fewer personal connections. But few are aware that the game grew out of a paper that Ron wrote in 1979 Odd79, popularizing “the Erdős number,” a concept attributed to the mathematician Casper Goffman 10 years before.
Ron was a chief sponsor in the US of the world-renowned, nomadic Hungarian mathematician Paul Erdős, who died in 1996. Erdős effectively founded the field of discrete mathematics, the underpinning of computer science, and wrote at least 1,525 papers by one published count. Ron observed that nearly 500 people had co-authored papers with Erdős, making them one degree of separation away (Erdős number 1). The number of mathematicians who in turn had written papers with number 1’s was 10 greater, making them Erdős number 2’s, and so on. Within 15 years, the Erdős number had morphed into Kevin Bacon. I’m sure Ron laughed about it for years, for he could find humor in anything.
Ron Graham, Bruce Rothschild, Al Hales, and Robert Jewett. Four of the inaugural recipients of the Pólya prize reunited in 2015.
He held many professional honors, including being one of the first awardees of the Pólya Prize, a recipient of the Lester R. Ford Award from the Mathematical Association of America, as well as president of the American Mathematical Society, and president of the International Jugglers Association. Ron could juggle half a dozen balls effortlessly while carrying on a conversation, but he seemed to have trouble making bogey on a hole with a single golf ball. “Golf is always a challenge,” he once confessed to me on the links. Ron loved challenges. A tall, trim man 62 in height, he could do a triple somersault on a trampoline into his 60s. “The best way to crack a complex problem, whether a triple somersault or a conundrum in graph theory,” he told John Horgan for a March 1997 profile in Scientific American, “is to break it down into component parts, learn each of the parts and learn how the parts go together.”
I got to know Ron as a mentor and teacher when I was a summer graduate student at Bell Labs, where he worked for 37 years leading one of the greatest teams of innovators in US corporate history. We shared a childhood interest in the Twin Prime Conjecture, stating that there are infinitely many pairs of prime numbers separated by (the numbers and , for example), although neither of us was ever successful in proving it. Later, at MIT, I taught students from his book, Magical Mathematics DG12. Like Ron himself, it made math accessible and exposed its magic and beauty to a wide audience.
In awarding him the prestigious Steele Prize for Lifetime Achievement in 2003, the American Mathematical Society called Ron “one of the principal architects of the rapid development worldwide of discrete mathematics in recent years. He has made many important research contributions to this subject, including the development, with Fan Chung, of the theory of quasirandom combinatorial and graphical families, Ramsey theory, the theory of packing and covering, etc., as well as to the theory of numbers, and seminal contributions to approximation algorithms and computational geometry (the ‘Graham scan’). Furthermore, his talks and his writings have done much to shape the positive public image of mathematical research in the USA, as well as to inspire young people to enter the subject. He was chief scientist at Bell Labs for many years and built it into a world-class center for research in discrete mathematics and theoretical computer science.”
As an editor on the boards of 40 mathematics and computer journals at the same time, Ron’s energy was indefatigable. He was a professor at the University of California San Diego, where he held the Chair of Computer and Information Science, and was Chief Scientist of the California Institute for Telecommunications and Information Technology, created to fund research related to the next generation of internet technologies. He served for two years on a National Research Council committee on cryptography. He joined the Akamai board in 2001, just before the tragedy of September 11 struck Akamai hard. Lending his organizational and technical gravitas, Ron dug in with us and helped to guide our three-year-old company through our worst nightmare. He also worked with us to establish the Akamai Foundation and its focus on supporting STEM education in collaboration with the MAA. With shares in Akamai that he earned as a director, he endowed the Akamai Professor in Internet Mathematics at UC San Diego (now the Paul Erdős Professor).
In The Man Who Loved Only Numbers Hof98, Paul Hoffman’s biography of Erdős, the legendary nomad, Fan said of her husband, Ron: “Many mathematicians would hate to marry someone in the profession. They fear their relationship would be too competitive. In our case, not only are we both mathematicians, we both do work in the same areas. So we can understand and appreciate what the other is working on, and we can work on things together and sometimes make good progress.”
Ron contributed to a lot of progress. The world of mathematics, the field of computer science, and Akamai, are indebted to him. And we will all miss him greatly.
Tom Leighton is a professor of applied mathematics at the Massachusetts Institute of Technology. His email address is ftl@math.mit.edu.
My Celebrity
If it is true that everyone knows one celebrity, Ron Graham was mine. Handsome, athletic, talented, and ever entertaining, he was irresistible. Ron could talk with equal ease to politicians, actors, college presidents, and the likes of Paul Erdős. Ron’s lectures were legendary: he regaled packed rooms with everything from deep Ramsey theory to the collaboration graph, laid out on a giant roll of transparent plastic. Sometimes he wheeled out a slide that seemed to be backward, or maybe upside down, but couldn’t be righted; then he’d walk across the stage while the shadow of his thumb remained on the slide. After one such talk at Emory University, to which he had brought an attache case that he never opened, he asked me and my colleagues to bring him to a big field. When we did so, he finally opened the case to reveal a stack of boomerangs, which he taught us all how to throw.
I met Ron shortly after I was introduced to combinatorics (my PhD thesis was in logic). I came with my Emory colleagues to a Southeastern Combinatorial Conference in Baton Rouge, Louisiana, and to my delight, found myself in a conversation with famous people, namely Ron, Fan Chung, Paul Erdős, and Brooks Reid, about embeddings of graphs in metric spaces. At some point something they said got me thinking, and when I resurfaced they seemed to be talking about a mathematician named Ellen Finnity. (In my defense, I once had a childhood friend named Annie Finnity.) I actually listened for a minute, but in the grip of an idée fixe, eventually asked who Ellen Finnity was. Ron managed, with some difficulty, to not crack up laughing, and never even teased me about it. My hero!
My first big break was solving a problem of Ron and Henry Pollak’s (the “squashed cube conjecture”). That resulted in a new winter coat for my wife (the problem carried a $250 bounty) and eventually to jobs at Bellcore, working for Fan, and at Bell Labs. Over the years Ron taught me how to juggle three balls, bounce safely on a trampoline, and ride on a side-by-side bicycle for two (with Fan!). He introduced me and my wife to the acrobats after a Cirque du Soleil performance, and after he left Bell Labs for academia, gave me a fabulous art/history tour of the UCSD campus.
Ron lived in a wider world than the rest of us. Once I suggested sending a shortish joint paper to the Journal of Graph Theory; said Ron, “I have another idea, let me handle it.” I said “sure,” and the next thing I knew, it was in the Proceedings of the National Academy of Science. This was long before outreach became a “thing.” Ron instinctively understood the value of bringing mathematics to the public. He was a major figure in discrete mathematics, but became much more than that: a representative of all of mathematics to the world. We mathematicians could hardly have asked for a better emissary than Ron. He was larger than life, and it’s hard to think about a world without him. For sure, there’ll never be another like Ron Graham.
Peter Winkler is a professor of mathematics and computer science at Dartmouth College. His email address is peter.winkler@dartmouth.edu.
My Role Model
I first met Ron in 1998, when I was a Courant Instructor at New York University and visited him at AT&T Labs during the summer. Since then we have kept a good relationship, met in many occasions, visited each other, and worked on several projects. He has been my research mentor, career advisor, long-term collaborator, and a good family friend. With his unforgettable smile, affectionate personality, and deep passion and appreciation for mathematics, Ron is the greatest mentor one can imagine and has had a lasting impact on my life and career.
At AT&T Labs, Ron introduced me to the fascinating world of Apollonian circle packings. He showed me a beautiful picture of the Apollonian circle packing with root quadruple , which has mutually tangent circles of radius , , and inscribed inside a unit circle, and then smaller circles are repeatedly inscribed into all the curvilinear triangles. Surprisingly, for each circle in the packing the reciprocal of its radius is an integer. Our initial project was to investigate the number-theoretic properties of the integers that occur in such packings. Working with Ron was such an enjoyable experience. He had a creative mind full of brilliant ideas, constantly asking questions and probing new directions, and never afraid of unfamiliar territory. Before we knew it, the project evolved into a comprehensive one intertwined with discrete geometry, fractals, group theory, number theory, and higher dimension extensions. The depth and scope are far beyond my graduate training in combinatorics. When I was frustrated, it was Ron’s encouragement and guidance that helped me through. He introduced me to many of his colleagues, discussing our progress, exchanging ideas, and seeking out references. Soon the work became a major collaboration with other experts at AT&T Labs, including Jeff Lagarias, Colin Mallows, and Allan Wilks GLM03. Later Ron and I had several other projects. A basic thing I learned from the very first experience with Ron is to keep one’s curiosity and do not be afraid. Put in Ron’s words, “If you encounter something new, just learn it.”
Working with Ron was full of fun, surprises, and laughter. With his broad interests and knowledge, he could put seemingly unrelated things together. Everyday he would suggest new connections or find new references, sometimes from literature, poems, or magazines. His mind was jumping all over the place, finding the beauty of mathematics in every corner. Amid our discussions, he would often pick up something randomly from a table—a box of ballpoint pens, a deck of cards, or several rubber balls—and the discussion would become a magic show or juggling performance, which was, of course, always accompanied with a gentle revelation of the “insider’s secret.”
Ron was a natural leader who had the magic to connect to other people. He was generous, warm-hearted, and energetic, willing to share his time with people at all levels. No matter who you are, being with Ron would make you feel important and taken care of. Over the past years, I have seen Ron in numerous conferences. During the breaks he was always the most favorite person, surrounded by students and junior faculty. He would ask their needs, give valuable suggestions, and share with them anecdotes about the math community. His generosity and wittiness won him love and respect from generations of young researchers.
Several years ago I visited him at UCSD and stayed in his house, together with Steve Butler. At almost eighty years old, Ron still worked assiduously. Every morning before I got up, he was already out exercising and working in a Starbucks. His daily schedule was always full with meetings or conference calls even in the late evening. But whenever he had time, we three would be together and talk about mathematics, discussing a new model of parking functions and the properties of juggling sequences. On a table at his house I saw a sign with the words “NEVER NEVER NEVER GIVE UP.” This was Ron Graham, a mentor, a guide, a colleague, and a friend of mine. But most importantly, he was always my role model, someone I will look up to and remember forever.
Catherine Yan is a professor of mathematics at Texas A&M University. Her email address is cyan@math.tamu.edu.
My Research Mentor
Ron Graham with four of his PhD students, Jake Wildstrom (2007), Joshua Cooper (2003), Glenn Hurlbert (1990), and Jay Cummings (2016).
My connection to Ron begins with Joel Spencer who was my Master’s advisor at Stony Brook. In my first year, 1985–1986, János Pach and Vera Sós were both visitors, Paul Erdős stopped by, and Béla Bollobás came up from LSU. I guess that was my introduction to the Hungarian Mathia. I think Joel ran the colloquium that year, because it was a non-stop parade of combinatorics giants: Herb Wilf, Dan Kleitman, Curtis Greene, Richard Stanley, …, and Ron Graham. How could anyone resist such a lure? I remember that Ron gave his talk with a wry smile and a twinkle in his eye, like he was hiding a secret. I would come to appreciate that facial expression for years to come. That summer I read Graham-Rothschild-Spencer GRS90 on the beach, attracting all sorts of comments from my family (“he’s learning how to invite people to a party where everyone knows each other”).
When Joel moved to NYU, he suggested that I consider Rutgers, to work with Ron, who had just become affiliated with Rutgers because of the birth of DIMACS. I first met Ron in his new and completely barren office at Rutgers. He opened the desk drawer and was surprised to see two small balls, which he began to bounce on the desk. He said he had heard about some balls that run out of bounces after a while. Sure enough, one of them landed like a thud, with no bounce. I immediately realized that I was in for some fun, and I’d better stay on my toes.
Typically, Ron and I met about every two weeks at Bell Labs rather than Rutgers, and my 30–40-minute drive from New Brunswick to Murray Hill was filled with anticipation, wondering what circus-like environment I would encounter next. Usually, “circus-like” is metaphorical but, with Ron, it was sometimes literal. One time I walked into his office and there were coins of every type scattered all over the floor, desk, chairs, shelves, etc. I asked what happened and he said that Penn & Teller just left, and that he was teaching them a new trick (which involved balancing a coin on the tip of a coat hanger and spinning the hanger around your finger without the coin falling off). For a long time, we tried to see how many times you could bounce a pen off the wall in one throw. We could get three hits pretty consistently, but never four. Once he came to work very excited to tell me that one of the physicists at the Labs proved that, with a perfect cylinder and frictionless surface, four was impossible. I said, “okay, give me a perfect cylinder and frictionless surface”—then off we went to look for imbalanced pens with some grip. One of our more semidangerous adventures involved throwing a lacrosse ball down three floors in the center of one of their stairwells. Normal throwing spins the ball, forcing it to bounce toward anyone walking up the stairs, while it is difficult to throw a knuckle ball hard enough to return to the third floor. Ron was just insatiably curious about everything all the time. This was the kind of stuff that used to get me into so much trouble in high school.
But we did some math, too. With the breadth of interests and sheer numbers of people coming and going at Bell Labs, Rutgers, and DIMACS, I felt lucky to be exposed to every nook and cranny of discrete math. Of course, you could ask Ron anything, and he’d likely know who has the latest result and what the open questions were. Thus it was difficult to think about which of all these wonderful directions to go in. I did have some success with a question of Ed Scheinerman on the dimension of circle containment orders that resulted in my first paper. But then Ron got me hooked on universal cycles, which he and Fan Chung and Persi Diaconis were just getting off the ground, and which became my thesis topic. That was exciting to be a part of, since it was new and everything was open. But it was also challenging because it was new, and techniques were few. Interestingly, that’s one topic Ron and I rarely discussed, outside of me informing him of my progress, or lack thereof. He wanted to make sure that people knew that what I produced was mine, and not his. It certainly made my results more self-satisfying, and probably did help land my first job at Arizona State (although I think Tom Trotter, who hired me, was likely more interested in my poset result!).
I will mention that I did get good at the hanger trick, and also learned the universal cycle card trick that Persi invented, which one can read about in their book DG12. I felt that, in one’s thesis defense, one should exhibit what they learned from their advisor that they might not have been able to learn elsewhere, and so I performed both. I guess that’s the one thing I could do better than Ron — of all the crazy, impossible-looking things he could do, he never really learned the perfect shuffle.
It was in those years that graph pebbling was born. I remember sitting with Fan, Dan Kleitman, and Dan Ullman, having lunch in a little café near George Washington University during the 1989 Capital City Conference on Combinatorics, while Fan described this fascinating little puzzle on the -cube. We went through lots of napkins that day, to no avail. Of course, Fan solved it a few weeks later and wrote the first paper on the topic. Contained in it was an unassuming little gem: Graham’s Conjecture.Footnote4 Thirty years later, we’re still plugging away at it.
The pebbling number of the Cartesian product of two graphs is at most the product of the individual pebbling numbers.
✖I’m grateful for learning site-swap juggling from Ron. It’s a great mental and physical diversion, of course, but it’s also a sneaky way to introduce young people to some very lovely mathematics, and to the notion that mathematics is everywhere, if only you will look. I’m satisfied to have discovered two universal cycle-related juggling patterns, and , and learned to perform them. It’s even more fulfilling, though, to have gone into K–12 classrooms and shared these things with young, eager minds. Juggling, card tricks, integer sequences, sorting networks, secret codes, puzzles, combinatorial games, tilings, Rubik’s cubes, etc. I’ve been doing this for over 20 years (we call it Crazy Math Day), inspired by Ron’s inviting, infectious, and encouraging manner, his constant sharing of interesting, curious, and surprising things, and his ability to present the simplest, irresistibly intriguing question that hides within it a larger theory. So, there’s a sense in which I’ve introduced Ron to thousands of kids, who hopefully now associate math with fun.
As so many can attest to, Ron’s concern for people went well beyond mathematics. He was well known for putting people first, ahead of professional and institutional concerns. He certainly shared professional and administrative advice with me throughout my career and, more importantly, touched the lives of my wife and family in meaningful ways, including inviting my son to the Gathering for Gardner conference because of his Rubik’s cube interest. Since Ron’s passing they have learned to unicycle in his honor.
I imagine that he and Uncle Paul are thumbing through The BOOK these days, smiling about the beautiful proofs the rest of us have yet to discover. Have fun, Ron. Know that we miss you.
Glenn Hurlbert is a professor of mathematics at Virginia Commonwealth University. His email address is ghurlbert@vcu.edu.
Farewell, My Favorite Coauthor
Ron Graham with Fan Chung in 2019, married since 1984.
I was surprised when I was told (by Steve Butler) that Ron and I have 101 joint papers. That is far more than I expected. I was so delighted to gain an extra digit, and I know exactly what Ron would say, “101 is a great number. It is a prime.” His love for numbers was perpetual. He could find interesting facts for any number that he came across. He remembered mundane phone numbers and always found funny facts in license plates. In fact, his car had the license plate “NUMBER.” The well-known “Graham’s number” is the largest number which, to that time, appeared in a mathematical proof.
After Ron left, there are too many things that I miss about him—his mischievous deeds, crazy new ideas, hilarious jokes, and, most of all, his unwavering support even under various stressful situations. Such scenarios included losing my purse on the train (among other places), forgetting to bring my passport (multiple times), car accidents (my fault), while he was particularly charming and calm. Among the numerous things that are hard to part with, the one I miss most is talking math with Ron. It was very hard to say goodbye to my favorite coauthor.
When we worked together, our success rate was amazingly high. Come to think about it, we rarely failed in our joint projects. The reasons were quite simple. We complemented each other and the math got better. Some of the problems that we previously worked on would never bear fruit if only one of us was taking it on. It is the exceptional case of “one plus one is more than two.” One of the main reasons for success was tenacity. On the shelf beside our big working table, there was a sign saying “Never, never, never give up” that Ron acquired a long time ago. When we struggled with a problem, usually one of us would not let it die. Some of the equations or polynomials were so monstrous, one person alone would surely have run out of energy. Most of the time though, it was advantageous that we had different views and approaches. Ron was extremely good at detecting patterns in chaos. It was his job to check if the conjecture could be false or should be modified either by examples or computation. It was my job to pull together the strategies or methods to prove the conjecture. It was his job to find those hard-to-find references (in the days without Google Scholar). It was my job to chew through the references. We shared the exhilarating moments of having new ideas, finding alternative directions, using new methods, or solving problems, and we also enjoyed the process of struggling for uncovering the truth.
Now and then we had coauthors’ spats, mostly about writing. We argued about what should be in the abstracts since it was the most important part of the article. For our joint papers, I usually wrote the first draft. Then Ron wrote the second draft and then we alternated. In the early days of our collaboration, that could mean total rewrites. For our first paper, I rewrote it eight times. (Later on when I told Henry Pollak the story of rewrites, he told me his first paper was rewritten 24 times.) As years went by, in some cases I would be so happy when Ron made very few changes of my draft. I distinctly remember about the joint paper by Ron, Martin Gardner, and myself on Steiner grids. After I wrote up the whole paper, it was sent to Martin for comments. Martin wrote back saying, “I couldn’t find a single word to change.” That was one of my greatest achievements. Later on the additional surprise was the Allendoerfer Award given by MAA for this joint paper.
In remembrance of my favorite coauthor, I here relate what is in a webpage I prepared about RonFootnote5 which includes many related links about Ron.
On the day before Ron left, he talked over the phone with Steve Butler and Persi Diaconis about their work in progress concerning certain random walks on . Ron pointed out that the behavior was very different for versus and he suggested various ways to get computational data.
Later in the day Ron exchanged email with Sam Spiro about their joint paper (with Persi and others on card guessing) which is near completion. He wrote email to Judith Ng including the photo of kayaks and a photo of me in the kitchen looking back at him through the Google Nest Cam.
On the wall in Ron’s office, he hung a poster of squares arranged in 90 lines each consisting of 52 little squares. Later on he modified it so it contains 100 lines. (He sometimes joked that his grandma lived to 99 and then was hit by a truck.) The rule is to fill one square each week. Thus, one can see how many squares are left and how finite and precious life is. He only used 84 lines but every square was gloriously filled.
Fan Chung is a professor emerita of mathematics and computer science at the University of California, San Diego. Her email address is fan@ucsd.edu.
References
- [BCH18]
- Steve Butler, Joshua Cooper, and Glenn Hurlbert (eds.), Connections in discrete mathematics: A celebration of the work of Ron Graham, Cambridge University Press, Cambridge, 2018. MR3793656Show rawAMSref
\bib{MR3793656}{collection}{ title={Connections in discrete mathematics}, editor={Butler, Steve}, editor={Cooper, Joshua}, editor={Hurlbert, Glenn}, subtitle={A celebration of the work of Ron Graham}, publisher={Cambridge University Press, Cambridge}, date={2018}, pages={xii+352}, isbn={978-1-107-15398-1}, isbn={978-1-316-60788-6}, review={\MR {3793656}}, }Close amsref.✖ - [CGW89]
- F. R. K. Chung, R. L. Graham, and R. M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), no. 4, 345–362, DOI 10.1007/BF02125347. MR1054011Show rawAMSref
\bib{MR1054011}{article}{ author={Chung, F. R. K.}, author={Graham, R. L.}, author={Wilson, R. M.}, title={Quasi-random graphs}, journal={Combinatorica}, volume={9}, date={1989}, number={4}, pages={345--362}, issn={0209-9683}, review={\MR {1054011}}, doi={10.1007/BF02125347}, }Close amsref.✖ - [DG12]
- Persi Diaconis and Ron Graham, Magical mathematics: The mathematical ideas that animate great magic tricks, Princeton University Press, Princeton, NJ, 2012. With a foreword by Martin Gardner. MR2858033Show rawAMSref
\bib{MR2858033}{book}{ author={Diaconis, Persi}, author={Graham, Ron}, title={Magical mathematics}, subtitle={The mathematical ideas that animate great magic tricks}, note={With a foreword by Martin Gardner}, publisher={Princeton University Press, Princeton, NJ}, date={2012}, pages={xiv+244}, isbn={978-0-691-15164-9}, review={\MR {2858033}}, }Close amsref.✖ - [EG80]
- P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de L’Enseignement Mathématique [Monographs of L’Enseignement Mathématique], vol. 28, Université de Genève, L’Enseignement Mathématique, Geneva, 1980. MR592420Show rawAMSref
\bib{MR592420}{book}{ author={Erd\H {o}s, P.}, author={Graham, R. L.}, title={Old and new problems and results in combinatorial number theory}, series={Monographies de L'Enseignement Math\'{e}matique [Monographs of L'Enseignement Math\'{e}matique]}, volume={28}, publisher={Universit\'{e} de Gen\`eve, L'Enseignement Math\'{e}matique, Geneva}, date={1980}, pages={128}, review={\MR {592420}}, }Close amsref.✖ - [Gra84]
- R. L. Graham, Recent developments in Ramsey theory, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Warsaw, 1983), PWN, Warsaw, 1984, pp. 1555–1567. MR804796Show rawAMSref
\bib{MR804796}{article}{ author={Graham, R. L.}, title={Recent developments in Ramsey theory}, conference={ title={Proceedings of the International Congress of Mathematicians, Vol. 1, 2}, address={Warsaw}, date={1983}, }, book={ publisher={PWN, Warsaw}, }, date={1984}, pages={1555--1567}, review={\MR {804796}}, }Close amsref.✖ - [GGL95]
- R. L. Graham, M. Grötschel, and L. Lovász (eds.), Handbook of combinatorics. Vol. 1, 2, Elsevier Science B.V., Amsterdam; MIT Press, Cambridge, MA, 1995. MR1373655
- [GLR72]
- R. L. Graham, K. Leeb, and B. L. Rothschild, Ramsey’s theorem for a class of categories, Advances in Math. 8 (1972), 417–433, DOI 10.1016/0001-8708(72)90005-9. MR306010Show rawAMSref
\bib{MR306010}{article}{ author={Graham, R. L.}, author={Leeb, K.}, author={Rothschild, B. L.}, title={Ramsey's theorem for a class of categories}, journal={Advances in Math.}, volume={8}, date={1972}, pages={417--433}, issn={0001-8708}, review={\MR {306010}}, doi={10.1016/0001-8708(72)90005-9}, }Close amsref.✖ - [GN97]
- R. L. Graham and J. Nešetřil, Ramsey theory in the work of Paul Erdős, The mathematics of Paul Erdős, II, Algorithms Combin., vol. 14, Springer, Berlin, 1997, pp. 193–209, DOI 10.1007/978-3-642-60406-5_16. MR1425213Show rawAMSref
\bib{MR1425213}{article}{ author={Graham, R. L.}, author={Ne\v {s}et\v {r}il, J.}, title={Ramsey theory in the work of Paul Erd\H {o}s}, conference={ title={The mathematics of Paul Erd\H {o}s, II}, }, book={ series={Algorithms Combin.}, volume={14}, publisher={Springer, Berlin}, }, date={1997}, pages={193--209}, review={\MR {1425213}}, doi={10.1007/978-3-642-60406-5\_16}, }Close amsref.✖ - [GP71]
- R. L. Graham and H. O. Pollak, On the addressing problem for loop switching, Bell System Tech. J. 50 (1971), 2495–2519, DOI 10.1002/j.1538-7305.1971.tb02618.x. MR289210Show rawAMSref
\bib{MR289210}{article}{ author={Graham, R. L.}, author={Pollak, H. O.}, title={On the addressing problem for loop switching}, journal={Bell System Tech. J.}, volume={50}, date={1971}, pages={2495--2519}, issn={0005-8580}, review={\MR {289210}}, doi={10.1002/j.1538-7305.1971.tb02618.x}, }Close amsref.✖ - [GR71]
- R. L. Graham and B. L. Rothschild, Ramsey’s theorem for -parameter sets, Trans. Amer. Math. Soc. 159 (1971), 257–292, DOI 10.2307/1996010. MR284352Show rawAMSref
\bib{MR284352}{article}{ author={Graham, R. L.}, author={Rothschild, B. L.}, title={Ramsey's theorem for $n$-parameter sets}, journal={Trans. Amer. Math. Soc.}, volume={159}, date={1971}, pages={257--292}, issn={0002-9947}, review={\MR {284352}}, doi={10.2307/1996010}, }Close amsref.✖ - [GRS74]
- R. L. Graham, B. L. Rothschild, and E. G. Straus, Are there points in with odd integral distances?, Amer. Math. Monthly 81 (1974), 21–25, DOI 10.2307/2318906. MR332698Show rawAMSref
\bib{MR332698}{article}{ author={Graham, R. L.}, author={Rothschild, B. L.}, author={Straus, E. G.}, title={Are there $n+2$ points in $E^{n}$ with odd integral distances?}, journal={Amer. Math. Monthly}, volume={81}, date={1974}, pages={21--25}, issn={0002-9890}, review={\MR {332698}}, doi={10.2307/2318906}, }Close amsref.✖ - [Gra78]
- Ronald L. Graham, Combinatorial scheduling theory, Mathematics today: Twelve informal essays (1978), 183–211.
- [GKP94]
- Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathematics: A foundation for computer science, 2nd ed., Addison-Wesley Publishing Company, Reading, MA, 1994. MR1397498Show rawAMSref
\bib{MR1397498}{book}{ author={Graham, Ronald L.}, author={Knuth, Donald E.}, author={Patashnik, Oren}, title={Concrete mathematics}, edition={2}, subtitle={A foundation for computer science}, publisher={Addison-Wesley Publishing Company, Reading, MA}, date={1994}, pages={xiv+657}, isbn={0-201-55802-5}, review={\MR {1397498}}, }Close amsref.✖ - [GLM03]
- Ronald L. Graham, Jeffrey C. Lagarias, Colin L. Mallows, Allan R. Wilks, and Catherine H. Yan, Apollonian circle packings: number theory, J. Number Theory 100 (2003), no. 1, 1–45, DOI 10.1016/S0022-314X(03)00015-5. MR1971245Show rawAMSref
\bib{MR1971245}{article}{ author={Graham, Ronald L.}, author={Lagarias, Jeffrey C.}, author={Mallows, Colin L.}, author={Wilks, Allan R.}, author={Yan, Catherine H.}, title={Apollonian circle packings: number theory}, journal={J. Number Theory}, volume={100}, date={2003}, number={1}, pages={1--45}, issn={0022-314X}, review={\MR {1971245}}, doi={10.1016/S0022-314X(03)00015-5}, }Close amsref.✖ - [GNB13]
- Ronald L. Graham, Jaroslav Nešetřil, and Steve Butler (eds.), The mathematics of Paul Erdős. I, second ed., Springer, New York, 2013, Including two new papers, Some of the papers in the first edition have been updated. MR3202530
- [GRS90]
- Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey theory, 2nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1990. A Wiley-Interscience Publication. MR1044995Show rawAMSref
\bib{MR1044995}{book}{ author={Graham, Ronald L.}, author={Rothschild, Bruce L.}, author={Spencer, Joel H.}, title={Ramsey theory}, series={Wiley-Interscience Series in Discrete Mathematics and Optimization}, edition={2}, note={A Wiley-Interscience Publication}, publisher={John Wiley \& Sons, Inc., New York}, date={1990}, pages={xii+196}, isbn={0-471-50046-1}, review={\MR {1044995}}, }Close amsref.✖ - [HRS75]
- A. Hajnal, R. Rado, and Vera T. Sós (eds.), Infinite and finite sets. Vols. I, II, III, Colloquia Mathematica Societatis János Bolyai, Vol. 10, North-Holland Publishing Co., Amsterdam-London; János Bolyai Mathematical Society, Budapest, 1975. Dedicated to Paul Erdős on his 60th birthday. MR0360076Show rawAMSref
\bib{MR0360076}{collection}{ title={Infinite and finite sets. Vols. I, II, III}, series={Colloquia Mathematica Societatis J\'{a}nos Bolyai, Vol. 10}, booktitle={Proceedings of a Colloquium held at Keszthely, June 25--July 1, 1973}, editor={Hajnal, A.}, editor={Rado, R.}, editor={S\'{o}s, Vera T.}, note={Dedicated to Paul Erd\H {o}s on his 60th birthday}, publisher={North-Holland Publishing Co., Amsterdam-London; J\'{a}nos Bolyai Mathematical Society, Budapest}, date={1975}, pages={Vol. I: 604 pp. Vol. II: pp. 605--1080. Vol. III: pp. 1081--1555}, review={\MR {0360076}}, }Close amsref.✖ - [HJ63]
- A. W. Hales and R. I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222–229, DOI 10.2307/1993764. MR143712Show rawAMSref
\bib{MR143712}{article}{ author={Hales, A. W.}, author={Jewett, R. I.}, title={Regularity and positional games}, journal={Trans. Amer. Math. Soc.}, volume={106}, date={1963}, pages={222--229}, issn={0002-9947}, review={\MR {143712}}, doi={10.2307/1993764}, }Close amsref.✖ - [Hof98]
- Paul Hoffman, The man who loved only numbers: The story of Paul Erdős and the search for mathematical truth, Hyperion Books, New York, 1998. MR1666054Show rawAMSref
\bib{MR1666054}{book}{ author={Hoffman, Paul}, title={The man who loved only numbers}, subtitle={The story of Paul Erd\H {o}s and the search for mathematical truth}, publisher={Hyperion Books, New York}, date={1998}, pages={viii+302}, isbn={0-7868-6362-5}, review={\MR {1666054}}, }Close amsref.✖ - [Odd79]
- Tom Odda, On properties of a well-known graph or what is your Ramsey number?, Topics in graph theory (New York, 1977), Ann. New York Acad. Sci., vol. 328, New York Acad. Sci., New York, 1979, pp. 166–172. MR557896Show rawAMSref
\bib{MR557896}{article}{ author={Odda, Tom}, title={On properties of a well-known graph or what is your Ramsey number?}, conference={ title={Topics in graph theory}, address={New York}, date={1977}, }, book={ series={Ann. New York Acad. Sci.}, volume={328}, publisher={New York Acad. Sci., New York}, }, date={1979}, pages={166--172}, review={\MR {557896}}, }Close amsref.✖
Credits
Figures 1–4, 8, and 13 are courtesy of Ché Graham.
Figures 5 and 12 are courtesy of Fan Chung.
Figure 6 is courtesy of Donald Knuth.
Figure 7 is courtesy of George Csicery.
Figure 9 is courtesy of Peter Vidor.
Figure 10 is courtesy of Veselin Jungic.
Figure 11 is courtesy of Jozsef Solymosi.