"How hard is it to go up a down escalator?" Erdos asked his friend and colleague, Ronald Graham.
"It can be done," Graham replied.
To prove his point, Dr. Graham, then director of the Mathematical Sciences Research Center at AT+T Bell Laboratories, raced up the down escalator at Newark Airport.
"That looks easy," Erdos remarked.
Despite firm warnings from Graham that it was not at all easy, and that Erdos couldn't possibly perform the stunt, Erdos insisted on having a try. He took a few steps, lost his footing, and slid to the bottom on his stomach. Graham was probably the only one in the amused crowd who knew that the elderly man in the grubby raincoat lying at the bottom of the escalator was a world renowned mathematician (Hoffman 1987).
Ronald Graham and Paul Erdos have spent a lot of time together. They have collaborated on twenty-five papers and a book. Much of their work has been in Ramsey theory. Ramsey theory is named after Frank Ramsey, a Cambridge University logician, who proved a complex theorem about infinite sets. The theorem implies that complete randomness is impossible; patterns are certain to appear in the positions of stars, rock formations, and the dates of assassinated presidents. The mathematics demonstrates that patterns do not prove the existence of a designer, human or divine; even totally random processes must produce order. Ramsey theorists are interested in the smallest set or "universe" which makes a particular pattern inevitable. Ramsey theory can be illustrated with a problem involving a dinner party in which the guests are selected at random from the telephone book: How many guests must be invited to insure that there are at least three mutual acquaintances or at least three mutual strangers?
It is easy to show that a party of six will insure the outcome. Picture yourself greeting five guests at the door. At least three must be acquaintances of yours, or, at least three must be strangers to you. Suppose that there are three acquaintances. If these three are mutual strangers, the condition is met. If not, then at least two are friends, and combined with yourself form the required group.
A similar argument can be made if there are three or more guests that you have never met, (see exercise 2).
Thus, among any group of six people, even if randomly chosen, a certain amount of order exists: it is certain that the group contains at least three mutual friends or three mutual strangers.
With a little effort you should be able to construct an example of a dinner party of five in which there are not three or more mutual friends, or, three or more mutual strangers (see exercise 3). With this construction the solution to our problem is complete: the dinner party must involve six or more people.
While this problem was easily dispatched, determining the party size necessary to insure at least four mutual friends or at least four mutual strangers is much more difficult, and for five, the problem, is unsolved! As the number of guests increases, the number of possible acquaintance relationships increases very rapidly. For this reason, while problems of this type are easily stated and understood, solutions are very difficult to find (Tierney 1984).
Persi Diaconis, a Stanford statistician, believes that the work Erdos and Graham have done in Ramsey theory may "...take a hundred years to be applied (Schecter 1985)." Like all of Erdos' work it is far removed from the practical demands of business and industry. Erdos is a pure mathematician, motivated solely by intellectual challenge and the beauty of mathematical relationships. (Look for the future lesson, "Is That a Problem?"). While Graham can become very enthusiastic about the purely theoretical‹his license plate reads "RAMSEY"--he is also very much interested in the applications of mathematics. At Bell Labs, Dr. Graham worked with a staff of seventy mathematicians who dealt with a multitude of problems related to the need to route hundreds of millions of telephone calls through a vast network of cables, microwaves, and satellites.
Unlike Erdos, Graham has many interests outside of mathematics. While Paul often falls asleep or slips off to a corner to work on his mathematics when he is forced to attend a nonmathematical event, Ron's interests have no bounds. He is an accomplished juggler, a past president of the International Juggler's Association. He was Bell Lab's pingpong champion, has bowled two 300 games, and still practices the trampoline routine that helped him earn his college tuition as a professional acrobat. Since leaving college he has learned to play the piano and speak Chinese. He is deadly with a boomerang and is quickly becoming an excellent tennis player. Ron Graham somehow finds enough hours in the week for these diversions, friends and family, his administrative duties, and a considerable amount of original mathematical research. Despite Graham's hectic schedule, his demeanor is calm and deliberate. He is always willing to push aside his work for a student or colleague struggling with a problem. As Diaconis says, "He's a nice genius" (Schecter 1985).
Paul Erdos and Ronald Graham seem to be an unlikely pair. While one is a mathematical monk, the other is intent on learning and experiencing everything that life on our planet has to offer. They have been brought together by their love and respect for the universal language: mathematics.
1. A drawer contains 5 blue socks, 11 red socks, and 7 yellow socks. What is the least number of socks chosen at random that guarantees a matched pair?
2. Show that if 5 randomly selected people arrive at your door, and at least 3 are strangers to you, then there exists a set of at least 3 mutual acquaintances or at least 3 mutual strangers, among the 5 guests and yourself.
3. Draw 5 dots in a circle on a piece of paper. Each dot will represent a person at a dinner party. Draw line segments connecting each dot with every other dot. Let blue segments indicate that the connected dots (people) are strangers, and red segments indicate friends. Try to complete this construction without drawing a red or a blue triangle. This will demonstrate that a party of five does not insure the presence of three or more mutual friends or three or more mutual strangers.
4. Many of the applied problems that Ronald Graham worked on at Bell Laboratories involve scheduling. Read Chapter 3, "Planning and Scheduling" in For All Practical Purposes, and write a short paper describing the nature of these problems.
Graham, Ronald L. 1978. Combinatorial scheduling theory. In Mathematics today, ed. Lynn Arthur Steen, 1983-211. New York: Vintage Books, a Division of Random House.
Hoffman, Paul. 1987. The man who loves only numbers. The Atlantic Monthly (November): 60-74.
Schecter, Bruce. 1985. Ronald L. Graham. In Mathematical people, ed. Donald J. Albers and G.L. Alexanderson, 109-17. Boston: Birkhauser.
Steen, Lynn A. ed., 1988. For all practical purposes: Introduction to contemporary mathematics. New York: W.H. Freeman and Company.
Tierney, John. 1984. Paul Erdos is in town. His brain is open. Science 84 (October): 40-47.
1. 4
2. If the three strangers are mutual acquaintenances, the condition is met. If not, then at least two are mutual strangers, and along with yourself form the required group.
3. Connect adjacent dots on the circle with blue segments. All other connections can be red.
4. Talented mathematics students may also want to read "Combinatorial Scheduling Theory," by Ronald Graham.