葛立恒Ronald Graham

葛立恒大家都叫他罗恩。他出生时，父亲正在塔夫特周围的油田工作，这对住在那里的某人来说并不奇怪，因为该镇的存在正是由于两侧的两个加利福尼亚大油田。然而，他父亲做同一份工作的时间并不长，随着罗恩长大，由于罗恩的父亲从事各种与油田和造船相关的工作，全家在佐治亚州和加利福尼亚州之间来回搬迁。由于不断搬家，罗恩在各种各样的学校上学，没有一所学校待超过十八个月。1941年，随着美国加入第二次世界大战，罗恩的父亲加入了商船队。

转学让这个极其聪明的男孩能够进入一所新学校，就读比他的年龄通常所对应的年级更高的班级。这意味着他进步很快，跳过了几个年级。由于比同班同学年纪更小，因此个子也更小，他此时的兴趣往往偏向学业而非体育。他最初真正着迷的是天文学，但很快他就爱上了数学。在五年级时，一位老师教他如何开平方根，他立刻想知道自己能否将这个方法推广以求出立方根，尽管他很久都无法解决自己提出的这个问题，但在尝试的过程中他学到了许多高等数学。他十一岁时，他的数学老师⟦N1⟧先生给了他一个他无法解决的问题[2]：——

我懂代数和三角学，以为自己能解决给我的任何问题。但有一天，⟦N1⟧先生给了我一个我解不出来的问题。问题是：如果已知老鼠的死亡率与种群规模成正比，求老鼠种群的大小。解决它需要微分方程的知识。然后他给了我一本书，并告诉我，等我读完这本书就能解决这个问题。那本书是⟦N2⟧、⟦N3⟧和⟦N4⟧合著的《微积分》。他说得没错。到那个学期末，我读完了那本书，并得到了一个解法。他还挑选我加入了学校国际象棋队。

葛立恒加入商船队后很少见到父亲，最终他的父母离婚了。他的母亲随后去了佛罗里达州居住，葛立恒不得不再次适应一所新学校。15岁时，他获得了莱斯特·佛特基金会奖学金，进入芝加哥大学，没有从高中毕业就开始了大学生活。他在芝加哥大学度过了三年，由于他在奖学金考试中的数学水平，他没有再修数学课程，但他学习了体操，尤其精通杂耍和蹦床。他的奖学金持续了三年，之后他在1954-55学年去了加利福尼亚大学乔治·伯克利分校，主修电气工程。然而，他选修了德里克·亨利·莱默[1]讲授的数论课程：-

在伯克利读本科时，德里克·亨利·莱默讲授的一门为期一年的数论课程激发了我对这个学科的兴趣……虽然我再也没有选修过德里克·亨利·莱默的课，但他教会了我独立思考的价值以及对数学中算法问题的鉴赏力。

葛立恒决定入伍美国空军，而不是等着被征召。他在空军服役了四年，其中三年在阿拉斯加的费尔班克斯度过。他渴望继续学业，于是注册进入阿拉斯加大学，在履行空军职责的同时进行学习，并于1959年获得物理学学士学位。在空军服役满四年后，他回到加利福尼亚大学伯克利分校，并于1961年获得硕士学位。随后，他在德里克·亨利·莱默的指导下攻读博士学位，德里克·亨利·莱默是他的学位论文导师[13]：——

在那里期间，他和另外两名学生组建了一个职业蹦床表演团，通过在学校、超市开业典礼甚至马戏团表演来赚钱。

他于1962年因学位论文On Finite Sums of Rational Numbers获得博士学位。在攻读博士学位期间，葛立恒与南希·杨结婚，后者是伯克利的数学专业学生；他们有两个孩子谢丽尔和马克。获得博士学位后，他搬到新泽西州，加入了贝尔电话实验室的工作人员队伍。很快他就发表了与他的博士论文相关的论文。两年内，他发表了八篇论文： On a theorem of Uspensky（1963）；A combinatorial theorem for partial sums（1963）；A theorem on partitions（1963）；On quadruples of consecutive kth power residues（1964）；On finite sums of reciprocals of distinct nth powers（1964）；On finite sums of unit fractions（1964）；Complete sequences of polynomial values（1964）；以及On a conjecture of Erdős in additive number theory（1964）。

为了了解这些论文的风貌，我们给出威廉·勒维克对A theorem on partitions的摘要：-

首先证明每个大于77的整数都可以划分为不同的正整数，其倒数之和为1。这依赖于一个关于78到333之间整数的此类划分表，以及一对变换，通过它们可以递归地扩展这个表。利用这个结果和一个进一步的引理，然后证明如果$a$和$b$是正有理数，则存在一个$r = r(a, b)$，使得如果$n > r$，则存在将$n$划分为大于$b$的整数，其倒数之和为$a$。

1963年在科罗拉多州博尔德举行了一次数论会议。葛立恒和埃尔德什都参加了会议，两位数学家首次见面。葛立恒回忆道[2]：-

我看到这个相当资深的50岁家伙，已经相当有名，在一次休息时打乒乓球。他问我是否想玩，我同意了。他彻底打败了我！我打过休闲乒乓球，但我无法相信这个老家伙打败了我。……我回到新泽西……我买了一张球桌，加入了一个俱乐部，开始在贝尔实验室打球，并参加了州联赛。我最终成为贝尔实验室的乒乓球冠军，并赢得了一个新泽西州的头衔。

葛立恒也开始与埃尔德什合作，总共发表了30篇联合论文（许多还有额外的合著者）。这些论文的例子有：On sums of Fibonnaci numbers （1972）；On a linear diophantine problem of Frobenius（1972）；On packing squares with equal squares（1975）；On products of factorials（1976）；以及Maximal anti-Ramsey graphs and the strong chromatic number（1989）。唐纳德·阿尔伯斯写道[2]：-

随着埃尔德什年事渐高，葛立恒帮他处理一些生活琐事——缴税、买衣服等。葛立恒甚至在他家里布置了一间埃尔德什室。直到1996年9月去世前，埃尔德什经常住在葛立恒那里……

葛立恒被迫成为汇率专家，因为埃尔德什讲课的酬金是以各种各样的货币支付的。葛立恒说：——

我在支票上签上他的名字然后存入银行。我这样做的时间太长了，我怀疑如果他自己背书，银行恐怕都不会兑现。

在这一点上，我们还应提到葛立恒与埃尔德什之间的另一个联系。几乎每一位职业数学家都知道自己的“埃尔德什数”——即通过论文构成的最短链条中的环节数，相邻论文有共同作者，最终通向埃尔德什。例如，我的[EFR]埃尔德什数是2，因为我与一位数学家合写过一篇论文，而这位数学家又与埃尔德什合写过一篇论文；我的[JOC]数是3，因为我与EFR合写过一篇论文。这一概念（现已成为MathSciNet的一部分）源自葛立恒1979年的一篇论文On properties of a well-known graph or what is your Ramsey number?。如果你查阅这篇论文，你会发现作者是Tom Odda。那是葛立恒发表这篇论文时所用的笔名（事实上，Tom Odda是一个汉语骂人词——葛立恒当时正在学汉语）。

1991年，吉安-卡洛·罗塔提名葛立恒担任美国数学会主席，写道[12]：——

葛立恒是当代数学界具有非凡魅力的人物之一，也是他那一代人中首屈一指的问题解决者。在过去二十五年里，他一直是离散数学发展的核心人物。他的开创性工作至少催生了三个新的数学分支：弗兰克·普伦普顿·拉姆齐理论、计算几何，以及多处理算法的最坏情况分析（现在有时被称为“葛立恒型分析”）。葛立恒的典型品质是一种不知疲倦的活力，既为数学事业，也为数学的应用。Ron从不会拒绝同事——无论远近——打来求助解决问题的电话。他的每一位合作者都知道，Ron总会设法挤出所需的时间或日子，提出一些实质性的建议，而且常常是迈向解决方案的关键一步。他能够同时有效地处理多个问题，同时在贝尔实验室承担繁重的行政工作，这一点不同寻常，或许独一无二。Ron对数学和科学的积极看法，以及他引人入胜的讲座，激励了一代又一代数学家。

葛立恒在1993-94年担任美国数学会主席。也许这里适合指出，他还在2003-05年担任美国数学协会主席。

葛立恒 从 1962 年到 1995 年担任信息科学主任。然后他在 1996 年被任命为首席科学家。1999 年他离开了贝尔实验室，但我们不应认为他在这 37 年里离开了学术界。在那段时间里，他在普林斯顿大学、斯坦福大学、加州理工学院、加州大学洛杉矶分校和加州大学戴维斯分校担任访问职位。他被任命为罗格斯大学数学科学大学教授，并从 1986 年到 1999 年担任这个兼职职位。葛立恒 于 1999 年被任命为加州大学圣地亚哥分校的 Irwin and Joan Jacobs 计算机与信息科学讲席教授；他继续担任这个讲席。

Ron和Nancy葛立恒在1970年代末离婚。1983年，他与金芳蓉结婚，后者也在贝尔实验室工作。两人研究相同的数学领域，并自1975年起合作撰写论文：例如On multicolor Ramsey numbers for complete bipartite graphs （1975年）；On the set of distances determined by the union of arithmetic progressions（1976年）；（与埃尔德什合作）On the product of the point and line covering numbers of a graph（1979年）。截至2009年12月，MathSciNet记录了Ron Graham和金芳蓉的77篇合作论文（许多还有其他合作作者）。

我们现在简要看看葛立恒写的一些书。1980年，他与Bruce Rothschild和Joel Spencer合作写了Ramsey theory。作者们写道：-

弗兰克·普伦普顿·拉姆齐理论直到最近十年才被承认为组合分析的一个有凝聚力的子学科。该理论的基本哲学是，在任何足够大的系统中，某种规律性必定总是存在。引用已故的西奥多·默慈金的话：“完全无序是不可能的。”因此，弗兰克·普伦普顿·拉姆齐理论的结果出现在数学的很大一部分中并不令人惊讶——弗兰克·普伦普顿·拉姆齐理论是纯数学的一颗明珠。

葛立恒的其他书包括：（与埃尔德什）Old and new problems and results in combinatorial number theory（1980）；Rudiments of Ramsey theory（1981），一位评论者描述为“不仅在数学阐述方面非常易读，而且极具娱乐性”；（与高德纳和Oren Patashnik）Concrete mathematics. A foundation for computer science（1989）；以及（与金芳蓉）Erdős on graphs（1998）。

葛立恒于1972年获得工业与应用数学学会颁发的乔治·波利亚组合学奖，1990年获得美国数学协会颁发的Carl Allendoerfer奖，1991年获得美国数学协会颁发的莱斯特·佛特奖，1994年获得组合学及其应用研究所颁发的莱昂哈德·欧拉奖章。他当选为美国国家科学院（自1996年起担任其财务主管）、Hungarian Academy of Sciences、American Academy of Arts and Sciences以及美国科学促进会会士。他是1983年8月在华沙举行的国际数学家大会的受邀演讲者，并于2000年担任美国数学会的约西亚·威拉德·吉布斯讲师。他是1990年在东盎格利亚举行的英国数学讨论会的全体演讲者，当时他作了Arithmetic progressions: from Hilbert to Shelah讲座，2009年他再次在戈尔韦担任全体演讲者，作了The combinatorics of solving linear equations讲座。他获得了西密歇根大学（1984年）、圣奥拉夫学院（1985年）、阿拉斯加大学（1988年）、中密歇根大学（2000年）和维滕贝格大学（2000年）的荣誉学位。

2003年，葛立恒获得了美国数学会颁发的凯瑟琳·斯蒂尔终身成就奖。颁奖词写道[1]：-

葛立恒是近年来离散数学在全球迅速发展的主要缔造者之一。他对此学科做出了许多重要的研究贡献，包括与金芳蓉一起发展拟随机组合族和图族理论、弗兰克·普伦普顿·拉姆齐理论、装填与覆盖理论等，以及对数论的贡献，还有对近似算法和计算几何的开创性贡献（“葛立恒扫描”）。此外，他的演讲和著作在很大程度上塑造了美国数学研究的积极公众形象，并激励年轻人进入这一学科。他多年担任贝尔实验室的首席科学家，并将其建设成为离散数学和理论计算机科学的世界级研究中心。他在1993-94年担任美国数学会主席。

在获得斯蒂尔奖时的回复中，葛立恒说[1]：-

我不记得有哪个时候我不热爱做数学，而且这种渴望多年来（至今！）从未减弱。但我也非常乐于与他人分享数学发现和见解，尽管这对数学家与非数学家交流来说可能是一个特殊的挑战。然而，我真的相信这种交流在未来会变得越来越重要。

Ronald Graham is known by all as Ron. When he was born, his father was working in the oil fields around Taft, which is not surprising for someone living there since the town owes its existence to the two major California oilfields on either side. However, his father did not keep the same job for very long and, as Ron was growing up, the family moved back and forward between Georgia and California as Ron's father worked in various jobs related to oil fields and shipbuilding. As a result of continual moving, Ron's schooling was in a whole variety of different schools, none of which he was in for more than eighteen months. In 1941, with the United States entering World War II, Ron's father enlisted in the Merchant Marine.

Moving schools had the effect that the extremely bright young boy could enter a new school in a higher class than normal for his age. This meant that he progressed rapidly missing out a few grades. Being younger, and therefore smaller, than his classmates, his interests at this time tended to be academic rather than sporting. His first real fascination was with astronomy but soon he fell in love with mathematics. When in the fifth form a teacher showed him how to extract square roots, he immediately wondered if he could generalise the method to find cube roots and, although he was not able to solve his own problem for a long time, he learnt a lot of advanced mathematics in the attempt. When he was eleven years old his mathematics teacher, Mr Schwab, gave him a problem which he could not solve [2]:-

I knew algebra and trigonometry and thought I could solve any problem given to me. But one day, Mr Schwab gave me one I couldn't do. The problem was to find the size of a population of mice if it was known that the death rate was proportional to the size of the population. It took a knowledge of differential equations to solve it. He then gave me a book and told me that I would be able to solve the problem by the time I finished it. That book was 'Calculus' by Granville, Smith and Longley. He was right. By the end of the semester, I finished the book and had a solution. He also chose me to be on the school chess team.

Graham saw little of his father after he joined the Merchant Marine and eventually his parents were divorced. His mother then went to live in Florida, and Graham once again had to adjust to a new school. At 15 he won a Ford Foundation scholarship to the University of Chicago and he began his university studies without graduating from high school. He spent three years at the University of Chicago where, due to the level of his mathematics attainment in the scholarship examinations he took no further mathematics courses, but he learnt gymnastics and in particular became proficient at juggling and the trampoline. His scholarship lasted for three years after which he spent the year 1954-55 at the University of California at Berkeley where he majored in electrical engineering. However he took a number theory course given by Derrick Henry Lehmer [1]:-

As an undergraduate at Berkeley, a one-year course in number theory taught by D H Lehmer fired my imagination for the subject ... Although I never took another course from Dick Lehmer, he taught me the value of independence of thought and an appreciation for the algorithmic issues in mathematics.

Graham decided to enlist in the U.S. Air Force rather than wait to be drafted. He spent four years in the Air Force, three of which were spent in Fairbanks, Alaska. Keen to continue his education, he enrolled at the University of Alaska and, carrying out his studies as well as his Air Force duties, he was awarded a B.S. in physics in 1959. When he had served four years in the Air Force he returned to the University of California, Berkeley, and was awarded an M.A. in 1961. Then he undertook research for his doctorate with D H Lehmer as his thesis advisor [13]:-

While he was there, he and two other students formed a professional trampoline troupe, earning money by performing at schools, supermarket openings, and even the circus.

He was awarded a Ph.D. in 1962 for his thesis On Finite Sums of Rational Numbers. While working towards his doctorate, Graham married Nancy Young who was a mathematics major at Berkeley; they had two children Cheryl and Mark. Following the award of his doctorate he moved to New Jersey and joined the staff at the Bell Telephone Laboratories. Soon he was publishing papers which related to his doctoral thesis. Within two years he had eight papers in print: On a theorem of Uspensky (1963); A combinatorial theorem for partial sums (1963); A theorem on partitions (1963); On quadruples of consecutive kth power residues (1964); On finite sums of reciprocals of distinct nth powers (1964); On finite sums of unit fractions (1964); Complete sequences of polynomial values (1964); and On a conjecture of Erdős in additive number theory (1964).

To get a flavour of these papers we give William LeVeque's summary of A theorem on partitions:-

It is first shown that every integer greater than 77 can be partitioned into distinct positive integers whose reciprocals add to 1. This depends on a table of such partitions for the integers between 78 and 333, together with a pair of transformations by which this table may be extended recursively. Using this result and a further lemma, it is then shown that if $a$ and $b$ are positive rational numbers, there is an $r = r(a, b)$ such that if $n > r$, there is a partition of $n$ into integers larger than $b$ whose reciprocals add to $a$.

In 1963 there was a Number Theory Conference in Boulder, Colorado. Graham attended the conference as did Paul Erdős and the two mathematicians met for the first time. Graham recalled [2]:-

I saw this rather senior guy of 50, already quite famous, playing ping-pong during one of the breaks. He asked me if I wanted to play and I agreed. He absolutely killed me! I had played casual ping-pong but I couldn't believe that this old guy had beaten me. ... I went back to New Jersey ... I bought a table, joined a club, started playing at Bell Labs, and in the State league. I eventually became the Bell Labs champion at ping-pong, and won one of the New Jersey titles.

Graham also started to collaborate with Erdős and, in total, they published 30 joint papers (many with additional joint authors). Examples of these papers are: On sums of Fibonnaci numbers (1972); On a linear diophantine problem of Frobenius (1972); On packing squares with equal squares (1975); On products of factorials (1976); and Maximal anti-Ramsey graphs and the strong chromatic number (1989). Donald Albers writes [2]:-

As Erdős aged, Graham helped him tend to some of the basics of life - paying taxes, buying clothes, etc. Graham even set up an Erdős room in his home. Up until the time of his death in September 1996, Erdős frequently stayed with Graham ...

Graham was forced to become an expert on currency exchange rates because honoraria from Erdős's lectures were paid in a wide variety of currencies. Graham said:-

I signed his name on cheques and deposited them. I did this so long I doubt the bank would have cashed a cheque if he had endorsed it himself.

There is one further Graham-Erdős link we should mention at this point. Almost every professional mathematician knows his "Erdős number" - the number of links in the shortest chain of papers, adjacent ones with an author in common, leading to Erdős. For example my [EFR] Erdős number is 2 since I have written a joint paper with a mathematician who has written a joint paper with Erdős and mine [JOC] is 3 since I have written a paper with EFR. This notion (now a part of MathSciNet) was due to Graham in a 1979 paper On properties of a well-known graph or what is your Ramsey number? If you look up this paper you will find that the author is Tom Odda. That was the pseudonym under which Graham wrote the paper (in fact Tom Odda is a Mandarin term of abuse - Graham was learning Mandarin at the time).

In 1991, Gian-Carlo Rota nominated Graham to be President of the American Mathematical Society writing [12]:-

Graham is one of the charismatic figures in contemporary mathematics, as well as the leading problem-solver of his generation. For the last twenty-five years, he has been the central figure in the development of discrete mathematics. His seminal work has led to the birth of at least three new branches of mathematics: Ramsey theory, computational geometry, and worst case analysis of multiprocessing algorithms (now sometimes referred to as "Graham type analysis.") Graham's characteristic quality is an indefatigable activity, both in the cause of mathematics, and on behalf of it applications. Ron will never turn down a telephone call from a colleague, near or far, asking for help on a problem. Every one of his collaborators knows that Ron will somehow find whatever hours or days are needed to come up with some substantial suggestion, and frequently with the crucial step towards the solution. He is unusual, unique perhaps, in being able to effectively work on several problems at once, while carrying a full load of administrative work at Bell Labs. Ron's positive view of mathematics and of science, as well as his entertaining lectures, have inspired generations of mathematicians.

Graham served as President of the American Mathematical Society in 1993-94. Perhaps this is an appropriate place to note that he was also President of the Mathematical Association of America in 2003-05.

At Bell Laboratories, Graham was Director of Information Sciences from 1962 to 1995. He was then appointed Chief Scientist in 1996. In 1999 he left Bell Laboratories, but we should not think that he had been out of the academic world for these 37 years. During that time he held visiting positions at Princeton University, Stanford University, the California Institute of Technology, the University of California, Los Angeles, and the University of California, Davis. He was appointed as a University Professor of Mathematical Sciences at Rutgers and held this part-time appointment from 1986 to 1999. Graham was appointed to the Irwin and Joan Jacobs Endowed Chair of Computer and Information Science at the University of California at San Diego in 1999; he continues to hold this Chair.

Ron and Nancy Graham were divorced in the late 1970s. In 1983 he married Fan Chung who also worked at Bell Laboratories. Both work on the same areas of mathematics and had been writing joint papers since 1975: for example On multicolor Ramsey numbers for complete bipartite graphs (1975); On the set of distances determined by the union of arithmetic progressions (1976); (with Paul Erdős) On the product of the point and line covering numbers of a graph (1979). By December 2009 MathSciNet records 77 joint papers by Ron Graham and Fan Chung (many with additional joint authors).

We now look briefly at some of the books Graham has written. In 1980, in collaboration with Bruce Rothschild and Joel Spencer, he wrote Ramsey theory. The authors write:-

Ramsey theory has only within the last ten years been recognized as a cohesive subdiscipline of combinatorial analysis. The basic philosophy underlying the theory is that within any sufficiently large system some regularity must always exist. To quote the late T S Motzkin: "Complete disorder is impossible." Consequently, it is not surprising that results from Ramsey theory occur throughout a large part of mathematics - Ramsey theory is a jewel of pure mathematics.

Other books by Graham include: (with Paul Erdős) Old and new problems and results in combinatorial number theory (1980); Rudiments of Ramsey theory (1981) described by a reviewer as "not only very readable in terms of mathematical exposition, it is highly entertaining"; (with Donald Knuth and Oren Patashnik) Concrete mathematics. A foundation for computer science (1989); and (with Fan Chung) Erdős on graphs (1998).

Graham has received the Pólya Prize in Combinatorics from the Society for Industrial and Applied Mathematics in 1972, the Carl Allendoerfer Award from the Mathematical Association of America in 1990, the Lester R Ford Award from the Mathematical Association of America in 1991, and the Euler Medal from the Institute of Combinatorics and Its Applications in 1994. He has been elected to the National Academy of Sciences of the United States (he has served as its treasurer since 1996), the Hungarian Academy of Sciences, the American Academy of Arts and Sciences, and the American Association for the Advancement of Science. He was an invited speaker at the International Congress of Mathematicians held in Warsaw in August 1983 and was the American Mathematical Society's Gibbs Lecturer in 2000. He was a plenary speaker at the British Mathematical Colloquium in East Anglia in 1990 when he gave the lecture Arithmetic progressions: from Hilbert to Shelah and he was again a plenary speaker in 2009 in Galway when he gave the lecture The combinatorics of solving linear equations. He has been awarded honorary degrees by Western Michigan University (1984), St Olaf College (1985), the University of Alaska (1988), Central Michigan University (2000), and Wittenberg University (2000).

In 2003, Graham received the Steele Award for Lifetime Achievement from the American Mathematical Society. The citation reads [1]:-

Ron Graham has been 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 centre for research in discrete mathematics and theoretical computer science. He served as president of the American Mathematical Society in 1993-94.

In his reply on the occasion of receiving the Steele Award, Graham said [1]:-

I can't remember a time when I didn't love doing mathematics, and that desire has not dimmed over the years (yet!). But I also get great pleasure sharing mathematical discoveries and insights with others, even though this can present a special challenge for mathematicians talking to non-mathematicians. However, I really believe that this type of communication will become increasingly important in the future.