Sci Am Profile Of Ron Graham

   
Recent changes
Table of contents
Links to this page
FRONT PAGE / INDEX

Scientific American: Profile: Ronald L. Graham: March 1997

RONALD L. GRAHAM

Juggling Act

Ronald L. Graham , chief scientist at AT&T Labs Research, begins with two balls, flipping them into the air with one hand while casually chatting with a visitor. He grabs another ball off a counter, and another, while noting that the world record for juggling is nine balls. He can do six consistently, seven "playing around." Nodding at a photograph on the wall showing himself juggling 12 balls, he reveals that it is an illusion generated by his daughter, Che, a photographer who specialises in digital doctoring.

Settling into a chair to give himself more vertical room, Graham juggles five balls, occasionally shifting the pattern, his hands a blur. His ground-level office here in Murray Hill, N.J. - adorned with a tabletop rock garden through which a minuscule stream burbles, a sheet of Chinese ideograms, a print of M. C. Escher's Night into Day - has too low a ceiling for six.

As Graham is fond of saying, "Juggling is a metaphor." Each of these white silicone balls could refer to a different aspect of his life, except that an accurate representation would require far too many balls. As a manager at AT&T Labs Research, which he joined 35 years ago when it was still called Bell Laboratories, he has nurtured some of the top mathematicians and computer scientists in the world. His work in number theory and other realms of mathematics earned him the prestigious Polya Prize in 1972 and membership in the National Academy of Sciences in 1985.

He carries a crushing load of other professional commitments. He is a part-time professor at Rutgers University and gives lectures and seminars around the world. He is highly active in the American Mathematical Society and the National Academy of Sciences, and he sits on the editorial board of 40 - yes, 40 - mathematics and computer journals. He served during the past two years on a high-profile National Research Council committee on cryptography, which last December issued a 750-page report recommending less restrictive U.S. regulation of encryption.

Graham's nonmathematical feats are equally diverse. He is an expert juggler and gymnast, who at the age of 61 can still do a triple somersault on a trampoline and a one-armed handstand on a swivelling pedestal. Over the past few decades he has mastered Ping-Pong (he is the former champion of Bell Labs), bowling (he has two perfect games under his belt) and Mandarin (he says he can pass himself off as Chinese in telephone conversations).

Cabinets just outside Graham's office are crammed with skill-challenging tchotchkes: an adult-size pogo stick, a unicycle, a spherical chess game, a box of so-called aperiodic tiles that, when properly fitted together, can cover an infinite plane with patterns that never quite repeat themselves. Graham pulls out a mutant basketball whose asymmetrical center of gravity makes it difficult to spin on a finger. "It's a constant battle," he murmurs as he gets the ball up and whirling. Graham makes it look easy.

Indeed, Graham's most impressive feat may be that he does not come across as the type-AAA person that at some level he must be. Tall, slim and sandy-haired, with a ready smile and a soft, tenor-pitched voice, he is the essence of easy-goingness. In conversation, he meanders from topic to topic, segueing seamlessly from the implications of Gödel's theorem to the psychological perils of gymnastics to the secret of his successes. The best way to crack a complex problem, he confides, whether a triple somersault or a conundrum in graph theory - is to "break it down into component parts, learn each of the parts and learn how the parts go together."

Only rarely does Graham offer a glimpse of the forces that compel him. The death last September of one of his closest friends, the legendary Hungarian mathematician Paul Erdös (pronounced AIR-dish), has made him more cognizant of how little time he has to learn new skills, solve new problems. He has considered making a memento mori, he says, out of a piece of graph paper with 100 squares on a side, 10,000 squares in all: "Every day you come in, make an X in that square." He draws an X in the air and then pauses, as if pondering an invisible sheet before him. Chances are, he adds, that he would not finish filling in the sheet.

Graham's history demonstrates that mathematicians can sprout even from the most apparently infertile soil. He was born in Taft, Calif., 100 miles northwest of Los Angeles, where his father worked in the oil fields. Young Ron's family kept moving back and forth across the country as his father switched from one job to another, mostly in shipyards.

Although he never stayed longer than two years at any one school, Graham nonetheless displayed a prodigious appetite and aptitude for mathematics and science. When he was 15 years old, he won a Ford Foundation scholarship to the University of Chicago, which had a program for gifted youths. On the small side for contact sports, he enrolled in a school program called Acrotheater, which taught students gymnastics, juggling and trampolining. (Graham is now 6 ft. 2 in., "huge" for gymnastics.) "We did shows throughout the year at high schools to show what a fun place the University of Chicago really is," he says.

After Graham had spent three years at Chicago, his father, worried that the university was too leftist, convinced him to transfer to a "nice, all-American school," the University of California at Berkeley. Graham enrolled there as an electrical engineering major, but after only one year, concerned that he might be drafted, he enlisted in the U.S. Air Force.

Shipped to Alaska, he worked as a communications specialist at night and attended classes full-time at the University of Alaska at Fairbanks during the day. On fulfilling his tour of duty, he returned to Berkeley and obtained a graduate degree in mathematics. In 1962 he joined Bell Laboratories, where he quickly rose through the managerial ranks while still pursuing his own research.

One of Graham's abiding mathematical interests is Ramsey theory, conceived almost 70 years ago by the British mathematician Frank P. Ramsey. "Complete disorder is impossible: that's the guiding philosophy of Ramsey theory," Graham says. "In any large, apparently disordered structures there are smaller, more well behaved substructures."

Problems in Ramsey theory are sometimes posed as "party puzzles." How many people must be invited to a party to ensure that a given number all know one another or are all mutual strangers? Finding the so-called Ramsey number becomes extraordinarily difficult as the number of guests increases. In 1993 two mathematicians established that the Ramsey number for a party with at least four mutual acquaintances or five mutual strangers is 25; the proof required a calculation that consumed the equivalent of 11 years of computation by a workstation.

It is still unclear whether Ramsey theory will prove to be useful (even to Martha Stewart). But areas of mathematics that seem utterly impractical, Graham points out, often turn out to have significant applications. Number theory, which was the subject of Graham's Ph.D. thesis and was once the "purest of the pure," is now a vital part of cryptography. Many encryption schemes exploit the fact that although multiplying two 100-digit numbers is relatively easy (at least for a computer), factoring one is mind-numbingly hard.

On the other hand, Graham adds, "it may be that just around the corner there's some great new idea" that would make factoring large numbers easy. Some experts think quantum computing, in which the bizarre properties of the quantum realm are harnessed to accomplish feats beyond the capability of conventional computers, may represent such a breakthrough. "That's one of my main jobs right now, to help foster this very far-out speculative thinking," Graham remarks.

The most forceful fosterer of Graham's thinking was Erdös, whom Graham calls "one of the great problem posers of all time." They met in 1963, and their first joint paper appeared in 1972. Graham maintained an "Erdös room" in his house for his mentor, who never had a family or steady job but travelled around the world staying with friends.

A 1979 paper by Graham helped to popularise the concept of an "Erdös number," which reflects a mathematician's degree of separation from Erdös. Those who have co-authored papers with Erdös have the Erdös number one, those who have co-authored papers with a member of this group but not Erdös himself have the number two, and so on. To Graham's surprise, a similar game has recently flourished on the Internet, in which people try to name the movies connecting the actor Kevin Bacon to other show-business personalities.

Graham has little difficulty switching from mathematics to other activities, in part because mathematics is connected with so much of what he does. For example, many of the 3,000 members of the International Jugglers Association, of which Graham once served as president, are involved with math or computers, and juggling has inspired some ingenious mathematics [see "The Science of Juggling," by Peter J. Beek and Arthur Lewbel; Scientific American, November 1995].

Moreover, Graham's closest collaborator lately is Fan Chung, a professor of mathematics at the University of Pennsylvania whom he married in 1983. (A previous marriage produced Graham's two children, Che and Marc.) The two recently tackled a problem related to the routing of calls through a telephone network. An ideal way to prevent calls from converging on the same route and thus exceeding its capacity is to assign calls to routes at random, but achieving true randomness is tricky. Chung and Graham have shown that most of the benefits of randomness can be obtained with "quasirandom" methods that are much easier to design and deploy.

Graham and his wife also just improved on a conjecture first posed by Erdös and a colleague back in 1935. The conjecture held that the number of points on a plane required to generate a convex polygon with n sides is a hideously complicated function of n + 1, or f(n) + 1. "We got rid of the plus one," Graham says happily.

--John Horgan

See also Erdos Number, Paul Erdos.


Contents

There were no headings
in the main text so there
is no table of contents.
 

Links on this page


Suggest a change ( <-- What does this mean?) / Send me email
Front Page / All pages by date / Site overview / Top of page

Universally Browser Friendly     Quotation from
Tim Berners-Lee
    Valid HTML 3.2!