Party numbers: deploying a host of computers to sort out a mathematical puzzle.

You're one of six people at a dinner party You look across the table at your five companions. It should come as no surprise to you that the dinner party includes either a group of at least three people who all know one another or a group of at least three people who don't know one another.

The reason for this certainty lies in a mathematical proof that any gathering of six people will always automatically include one or the other of these two groupings. No such guarantee is possible when five or fewer people are present.

This result stems from a branch of pure mathematics known as Ramsey theory, which concerns the existence of highly regular patterns in any large set of randomly selected numbers, points, or objects. Given enough stars, for example, it's not difficult to find groups of stars that very nearly form a straight line, a rectangle, or even a dipper.

Similarly, any sufficiently long sequence of numbers generated by the roll of a die will inevitably display certain regularities. Ramsey theorists try to work out just how many stars, numbers, or party goers are required to guarantee the presence of a certain pattern.

The party puzzle typifies the sorts of problems that Ramsey theory tackles: What is the minimum number of guests that must be invited so that either at least x guests will know one another or at least y guests won't? The resulting minimum number--which equals 6 when x is 3 and y is 3--is called a Ramsey number.

The search for Ramsey numbers belongs to the realm of pure mathematics. So far, there are no direct practical applications. Nonetheless, the techniques developed to look for Ramsey numbers may themselves prove useful one day in both mathematics and computer science.

Determining the Ramsey numbers associated with various combinations of acquaintances and strangers has proved extraordinarily difficult (see table). Now, two researchers have finally shown that 25 is the minimum number of guests needed to guarantee that a party includes a group of at least four people who all know one another or a group of at least five people who are strangers to one another. Using as many as 110 desktop computers at one time to sift through various possibilities, Stanislaw P. Radziszowski of the Rochester (N.Y) Institute of Technology and Brendan D. McKay of the Australian National University in Canberra spent nearly three years establishing this result.

"This was the smallest unsolved Ramsey number," Radziszowski says. "It will quite probably be the last one solved for many, many years."

Ramsey theory originated in the work of Frank Plumpton Ramsey, a mathematician at the University of Cambridge in England who was keenly interested in mathematical logic, philosophy, and economics. Although only 26 years old when he died in 1930, Ramsey left behind a rich legacy of mathematical results that continue to intrigue mathematicians.

"He is especially noted for the remarkable originality of his work, which was in many cases not appreciated until long afterwards," Radziszowski says. The party puzzle represents a special case of a theorem that appeared in one of Ramsey's papers on mathematical logic. This theorem states that if the number of objects in a set is sufficiently large and if each pair of objects has one of a number of relations, there exists a subset containing a certain number of objects where each pair has the same relation (that is, all the members of the subset are mutual acquaintances or strangers).

That's like saying that complete disorder is impossible, remarks mathematician Ronald L. Graham of AT&T Bell Laboratories in Murray Hill, N.J. "Somehow, no matter how chaotic something looks, deep within it is something smaller that's more structured."

In the 1930s, Hungarian mathematician Paul Erdos, who pioneered many of the key ideas extending Ramsey's theorem, started thinking about the question of exactly how large a set must be to guarantee the presence of a certain subset. Out of his ruminations came the party puzzle.

Mathematicians deal with these problems by constructing what they call a graph. In general, a graph consists of an array of points connected by straight lines, which are called edges.

In the party problem, one proceeds by drawing a point for each guest, then connecting each point with every other point by either a red line (meaning these two people are acquainted) or a blue line (meaning these two people are strangers). If three people all know one another, one would see a red triangle in the maze of lines connecting the points.

The party puzzle requires finding the minimum number of points so that no matter how you color the lines, there must always exist a certain geometrical structure -- for instance, a red or a blue triangle when looking for groups of three strangers or three acquaintances. A graph with six points meets this criterion, whereas a graph with five points does not necessarily contain the required geometrical figure (see diagrams).

Solving such a problem by checking every possible graph has proved impractical. The simplest case involving three acquaintances and three strangers would require looking at 32,768 possibilities. The number of cases that must be checked escalates tremendously for subsets that are only slightly larger.

Nonetheless, by employing ingenious reasoning that circumvents the brute-force approach, mathematicians managed to determine seven Ramsey numbers by the end of the 1980s without resorting to computers.

In 1990, McKay and Zhang Ke Min of Nanjing University in China showed that the case involving three acquaintances and eight strangers has the Ramsey number 28. This time, the researchers had required extensive computer assistance to sift through various possibilities to determine the number.

At this stage, Radziszowski entered the picture. Communicating almost entirely by electronic mail, he began collaborating with McKay in a concerted effort to establish the Ramsey number for four acquaintances and five strangers.

Individually checking the 1065 possible graphs was clearly out of the question. McKay and Radziszowski concentrated on developing efficient procedures, or algorithms, for such operations as mathematically "gluing" together small graphs to make larger graphs. They also spent considerable time testing their method.

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 they could do the necessary computations on lots of desktop computers rather than having to rely on a single supercomputer.

"Both of our institutions have considerable numbers of personal computers -- mostly Sun workstations --that sit in staff offices or in student laboratories," Radziszowski says. "In the middle of the night and on weekends, many of these computers are available for other uses. At some times, we had about 110 computers working simultaneously"

To rule out potential errors, the researchers did everything twice. Each one wrote an independent computer program that implemented the same basic ideas in a slightly different way.. The companion computations required a total of 11 years of computer time.

"The total amount of computer time might be the greatest ever used to solve a problem in pure mathematics," Radziszowski says.

The work of Radziszowski and McKay may aid others conducting monstrous mathematical searches. "We developed a method of collapsing such searches by, in effect, doing many cases at the same time," he says. "Our technique will not apply in every situation, but we are confident there are important practical problems around for which it will be a major advance."

"What happens in mathematics a lot is that a particular problem serves as a kind of milepost," Graham says. "You attack this particular problem, you develop tools [to solve it], and the tools turn out to be what are important."

At the same time, the prospects of determining the Ramsey number for the next important case - that of five acquaintances and five strangers - appear bleak. "We do not believe that present techniques are adequate for the determination of any further Ramsey numbers," Radziszowski says. "Even a thousandfold increase in computer power-which will probably happen within two decades -- may not be enough."

Graham agrees. "It's going to be a while before you see the next number," he says. "This is like a little plateau. You develop some tools and you're climbing. Eventually, you get there. Then the question is what you need to do to push further. That's the job of the next generation [of mathematicians]."

  Number of  Number of  Ramsey
Friends    Strangers  Number
3          3           6
3          4           9
3          5          14
3          6          18
3          7          23
3          8          28
3          9          36
4          4          18
4          5          25
5          5           ?

This table lists all known Ramsey numbers. Mathematicians have established that the Ramsey number for five friends and five strangers is at least 43 but no larger than 49.