"If you don't know how to attack a particular problem, ask Erdős" was the constant refrain among his colleagues and collaborators. He was a one-man clearinghouse for information on the status of unsolved problems in the fields of mathematics that attracted his attention (see "Paul Erdos and an Infinity of Problems").
By the time he died in 1996, Erdős had also earned a reputation as the greatest problem solver of all time. He had the knack of asking just the right mathematical question—one that was neither so simple that it could be solved in a minute nor so difficult that a solution was unattainable. Ramsey theory, which offered a wide variety of challenges, was one of his joys.
A typical question involving Ramsey theory concerns how many numbers (see "Pigeonhole Congestion"), points (see "Planes of Budapest"), or specified objects are needed to guarantee the presence of a certain structure or pattern. You look for the smallest "universe" that automatically contains a given object.
For example, it may be the smallest group of arbitrarily positioned stars that would include a convex quadrilateral or the number of people required to ensure the attendance of three strangers or three acquaintances at a gathering (see "Party Games").
Fascinated by such problems, Paul Erdős particularly liked those he called "party puzzles," which involve different combinations of strangers and acquaintances brought together at some sort of gathering. But he didn't usually think of these problems in terms of people—except as a way of describing them informally.
Erdős reasoned in terms of points, lines, and colors—all elements of a branch of mathematics known as graph theory. In general, a graph (in this context) consists of an array of points, or vertices, connected by straight lines, which are often called edges.
To convert a party puzzle into a graph problem, you draw a point for each person present. You then draw lines between the points, with red lines joining two people who know each other and blue lines for two people who are strangers. When all pairs of points are joined, the resulting network of points and lines is known as a complete graph.
Depending on the relationships specified in a given case, such a graph may contain only red lines, only blue lines, or a mixture of red or blue lines joining the points. The problem comes down to proving that no matter how the lines are colored, you can't avoid producing, in the case of six points (or people), either a red triangle (representing three mutual acquaintances) or a blue triangle (three strangers).
Such a coloring is guaranteed for a complete graph of six points, but not necessarily for a graph of five or fewer points. Hence, the minimum number of points that necessarily has the requisite pattern is six, often designated by the so-called Ramsey number R(3,3), where the first number inside the parentheses gives the number of acquaintances and the second gives the number of strangers.
What about subgroups of four strangers or four acquaintances? It turns out that an array of 17 points is insufficient to guarantee that four points will be linked by the same color. Only a graph of 18 or more points will always do the job. Thus, R(4,4) = 18.
In a graph representing seventeen people (left), it's possible to color the lines so that no four points are connected by a network of lines that are completely blue or completely red. In contrast, in a graph representing eighteen people (right), there is always such a network, meaning that a group of four mutual acquaintances or four mutual strangers will always be present in such a gathering.
In other words, at a dinner party of 18 there will always be at least four mutual acquaintances or strangers, but that may not necessarily happen when only 17 people are present,
It may be tempting to consider Ramsey's theorem in drawing up a guest list to ensure an appropriate balance of novelty and familiarity in some random gathering—guests selected, perhaps, by sticking pins in a phone book.
The trouble is that calculating the minimum number of partygoers to have—say, seven acquaintances or nine strangers—can be extraordinarily difficult. Though Ramsey's theorem guarantees the existence of such arrangements, determining their actual size is an onerous task.
The chief problem is that the number of cases that must be checked escalates rapidly with each step up in the size of the group. For example, a group of five represents 1,024 different cases, a group of six has 32,768 possibilities, and a group of seven has 221 possibilities.
A prodigious amount of effort involving considerable mathematical ingenuity has gone into producing the rather scant table of Ramsey numbers known in the year 2000 (below). In several cases, mathematicians have been able to find the answer only to within a range of the true value—all for the sake of solving an intriguing puzzle rather than for any particular practical application.
A Ramsey number represents the minimum number of people needed to guarantee the presence of a given number of mutual acquaintances and a given number of mutual strangers. In some cases, mathematicians have not yet pinpointed the actual Ramsey number and can give only the range within which the number must fall.
In the last few decades, computers have played a significant role in determining Ramsey numbers. For example, in 1990, Brendan McKay and Zhang Ke Min relied on computers to help them sift through thousands upon thousands of possibilities to determine R(3,8).
A little later, McKay collaborated with Stanislaw P. Radziszowski in a concerted effort to find R(4,5). Checking all possible graphs was out of the question. Instead, McKay and Radziszowski focused on developing efficient procedures for mathematically "gluing" together small graphs, which could be checked more easily, to make graphs large enough for the problem at hand.
Because their search technique involved using the same computer program many times with different data, the researchers could readily partition their task into small pieces. This meant that they could do the necessary computations on many desktop computers rather than having to rely on a single supercomputer.
Both of the institutions where the researchers were based had a large number of workstations located in staff offices and student laboratories. Many of these machines were often idle during the night or on weekends. By commandeering these resources at odd times, the mathematicians could have as many as 110 computers working simultaneously on the problem.
By early 1993, McKay and Radziszowski had their answer: R(4,5) = 25. At that time, however, the prospect of cracking the next candidate, R(5,5) appeared bleak.
Erdős liked to tell an allegorical tale about the difficulties of determining Ramsey numbers. Suppose an evil spirit were to come to Earth and declare, "You have two years to find R(5,5). If you don't, I will exterminate the human race." In such an eventuality, it would be wise to get all the computers in the world together to solve the problem. "We might find it in two years," Erdős predicted.
But if the evil spirit were to ask for R(6,6), Erdős noted, it would be best to forgo any attempt at the computation and instead launch a preemptive strike against the spirit to destroy him before he destroys us.
On the other hand, "if we could get the right answer just by thinking, we wouldn't have to be afraid of him, because we would be so clever that he couldn't do any harm," Erdős concluded.
Erdős himself was a master of innovative techniques for solving problems, sometimes even exploiting randomness and probability to establish the existence of structures that he was determined to corral in his many party puzzles.
Previously: Planes of Budapest
Next: Dartboard Estimates
No comments:
Post a Comment