Advertisement
Supported by
Ronald L. Graham, Who Unlocked the Magic of Numbers, Dies at 84
He was pre-eminent in the field of discrete mathematics, coming up with “some really pretty cool stuff.” (He was also a world-class juggler.)
Ronald L. Graham, who gained renown with wide-ranging theorems in a field known as discrete mathematics that have found uses in diverse areas, ranging from making telephone and computer networks more efficient to explaining the dynamics of juggling, died on July 6 at his home in the La Jolla section of San Diego. He was 84.
The cause was bronchiectasis, a chronic lung condition, according to a statement from the University of California, San Diego, where Dr. Graham was an emeritus professor.
“He created a lot of mathematics and some really pretty cool stuff,” said Peter Winkler, a mathematician at Dartmouth College. “This occurred over many years, and so it’s only now that we get to sort of look back and see all the stuff that he did.”
One thing he did was develop methods for worst-case analysis in scheduling theory — that is, whether the order in which actions are scheduled wastes time. On another front, with his wife and frequent collaborator, Fan Chung, an emeritus mathematician at the University of California, San Diego, he developed the idea of quasi-random graphs, which applied numerical preciseness in describing the random-like structure of networks.
Dr. Graham’s research was detailed in about 400 papers, but he never fit the stereotype of a nerdy mathematician. Soft-spoken but garrulous, he leavened his talks on high-level equations with silly jokes and sight gags. He was also an expert trampoline gymnast and juggler, a side pursuit — he was elected president of the International Jugglers’ Association in 1972 — that in his hands also lent itself to mathematical analysis. At one point Dr. Graham and three other juggling mathematicians proved an equation for the number of possible ball-juggling patterns before a pattern repeats.
Dr. Graham was a collaborator and close friend of Paul Erdos, one of the great mathematicians of the 20th century. Dr. Erdos cared only about numbers, so much so that he lived without a permanent home or job. Carrying a single piece of battered luggage, he would flit from one place to another, relying on the hospitality of colleagues, including Dr. Graham, who set aside a room at his home for him.
Dr. Erdos was not, however, the easiest of houseguests. “After a couple of days, they start fighting,” Dr. Chung said of him and her husband.
When they met, Dr. Graham and Dr. Erdos were among the few working in discrete mathematics, particularly in an area known as combinatorics — the mathematics of combinations.
In an introductory probability class, a simple combinatorics problem might ask: If one pulls three balls at random out of a bag that contains six blue ones and four red ones, what are the chances that all three are red? (The answer is 1 out of 30.)
Combinatorics proved to be important to the rise of digital technology in the 1970s. “Such thinking was exactly right for many of the key issues in theoretical computer science,” said Andrew Granville, a mathematician at the University of Montreal.
It led to what became known as Graham’s number, which was for a time the largest number used in a proof, according to the Guinness Book of World Records. The number came out of a problem known as the Ramsey theory, which states that in large systems there can never be complete disorder, that pockets of structure will appear within the apparent chaos.
Dr. Graham was looking at cubes in which the lines between the corners were colored red or blue. In a three-dimensional cube, it is easy to color the lines so that no planar slice of the cube with four vertexes has edges all of one color. But mathematicians can also imagine cubes in four dimensions and greater, and so Dr. Graham wanted to know whether this property of being able to avoid slices of one color would persist in greater dimensions.
“The answer: no,” Dr. Graham explained in 2014 in an episode of Numberphile, a math show on YouTube. “If the dimension is large enough, you cannot avoid it. No matter how you color it, you cannot avoid it.”
No one knows in precisely what dimension this unavoidability would kick in, but Dr. Graham calculated an upper bound for the answer — a number so huge that there is not enough space in the entire universe in which to write all of the digits.
Ronald Lewis Graham was born to Leo and Margaret Jane (Anderson) Graham on Oct. 31, 1935, in Taft, Calif., an oil- and gas-producing region about 120 miles northwest of Los Angeles. His father worked in the oil fields, and both parents later worked in shipyards, moving with the family back and forth between California and Georgia, resulting in Ronald’s skipping several grades. After his parents divorced, he and his mother moved to Florida.
Without graduating from high school, Ronald received a Ford Foundation scholarship to attend the University of Chicago at 15. When his scholarship ran out, he transferred to the University of California, Berkeley, where he majored in electrical engineering and also studied number theory.
In 1955, he enlisted in the United States Air Force and was assigned to a base in Fairbanks, Alaska. He signed up to work the night shift so that he could attend the University of Alaska, about 30 miles away. He received his bachelor’s degree in 1958 in physics, because the university was not accredited to award degrees in mathematics.
He returned to Berkeley for graduate school, where he and two friends formed a professional trampoline group, the Bouncing Baers, which performed with a circus.
After obtaining a doctoral degree in mathematics from Berkeley in 1962, Dr. Graham joined Bell Labs, solving problems that proved helpful for a telephone company. In the 1960s, a Bell Labs engineer named John R. Pierce came up with the idea of dividing up how phone calls were sent from one place to another, a precursor to what is now known as packet switching.
“Until then, communication was done by phone lines, and lines had to be open from one end to the other,” Dr. Winkler said.
In Dr. Pierce’s method, the data carrying the sound of a phone call was chopped apart, and “that information would be piled into these little packets, and these packets would swim around the network,” Dr. Winkler said.
That was more efficient, since one phone line could now handle many calls at once. But “the key to such a system is how to assign addresses to the nodes so that the packets can find their way around,” Dr. Winkler said.
Dr. Pierce used unique strings of 0s and 1s, but the labeling method failed, so he sought help from Dr. Graham and Henry O. Pollak, another Bell mathematician. In 1971, Dr. Graham and Dr. Pollak came up with another labeling technique using an asterisk in addition to 0 and 1. (The asterisks represented “don’t care” — designating parts of the address that were not used in calculating where the packet should be sent next.)
“They came up with an idea which, frankly, sounds to me like a bad idea, even though I was eventually the person who proved that it worked,” Dr. Winkler said. “I mean, even in retrospect, I don’t see how they saw this.”
After the breakup of AT&T, Dr. Graham became the chief scientist of AT&T Labs. In 1999, he became a professor of computer and information science at the University of California, San Diego.
He never stopped exploring mathematical problems, and several new papers of his have yet to be published.
Dr. Graham was president of the two largest professional mathematics organizations in the United States — the American Mathematical Society and the Mathematical Association of America — and a member of the National Academy of Sciences.
His first three marriages ended in divorce.
In addition to Dr. Chung, whom he married in 1983, survivors include a son, Marc; three daughters, Ché Graham, Christy Newman and Laura Lindauer; two stepchildren, Dean Chung and Laura Bower; a brother, Jerry Graham; and 11 grandchildren.
Dr. Winkler remembered a visit by Dr. Graham to Emory University about 40 years ago. During the talk, Dr. Graham placed a slide on the overhead projector, and people in the audience began pointing out that it appeared to be upside down or backward. But no matter how Dr. Graham flipped it, it still looked wrong.
In fact, individual letters had been written backward on the slide to create the confusion.
“It was marvelous because everybody in the audience thought that they knew what could be done to this slide to make it right,” Dr. Winkler said. “It was a sight gag.”
After the talk, Dr. Graham asked if there was a large field nearby. There was, and he got the mathematicians to pile into cars. Once there, Dr. Graham opened the attaché case that he had conspicuously brought to the lecture.
“It was full of boomerangs,” Dr. Winkler said. “And Ron proceeded to show us all how to throw a boomerang. We had a ball. We had an absolutely wonderful time.”
Advertisement
No comments:
Post a Comment