How many people would you need at a party to guarantee that at least three individuals know each other, or that at least three do not know each other? Working this out with pen and paper may take a while, but many mathematicians will readily tell you the answer is six. This party scenario, also called the "friends and strangers" theorem, is based on a concept known as Ramsey numbers, named after early 20th-century British Mathematician Frank Ramsey.
Now, imagine that more people are invited to this hypothetical party. How many would be required to ensure that at least five people know each other, or, conversely, that at least five are strangers? The answer is not clear. Indeed, mathematicians only know that the number of required people would be at least 43 and no more than 48. The actual answer falls somewhere in this range but is unknown. Add even more people to the party, and the uncertainty in the problem quickly becomes enormous.
Now, for the first time in decades, Caltech professor of mathematics David Conlon and his colleague Asaf Ferber of UC Irvine have shrunk that uncertainty by exponential amounts, for a special category of Ramsey numbers known as multicolor Ramsey numbers. The researchers describe their work in a study appearing in the journal Advances in Mathematics.
"One of the most stubborn numbers in math has finally budged," wrote Kevin Harnett in an article about the research in Quanta magazine.
"The solution came along very, very quickly," says Conlon. "We were surprised that it worked so well, actually."
Mathematicians think about Ramsey number problems in the form of points connected by lines, which they call graphs. The people at the party from the example above are essentially the points in these graphs. If individuals know each other, a line of one color, say blue, would be drawn between their respective points. If they do not know each other, they would be connected by a red line.
In the case described above, with six people attending the party, at least three people know each other, or at least three people do not know each other. Thus on the graph representing this situation, there would be at least one blue triangle, or one red triangle.
"We are interested in what patterns emerge in these scenarios," says Conlon. "Ramsey numbers tell us that even when things look chaotic, there are still patterns to be found."
In the new study, Conlon and Ferber looked at Ramsey numbers where three or more colors are used to connect the points in the graphs (thus the term "multicolor"). For example, if you used the colors blue, green, and red to connect points, 17 points would be required to guarantee at least one blue, or one red, or one green triangle. From our two-color example above, we know it takes only six points to guarantee one red or one blue triangle. Essentially, more points are needed in the scenarios with multiple colors.
Additionally, when the mathematicians want to identify not triangles but shapes containing four, five, or more points, the uncertainty in the total number of required points rises even faster for multicolor problems.
For their work, Conlon and Ferber used a new type of proof to shrink the multicolor Ramsey uncertainties by exponential amounts. They say they used a hybrid approach that blended older strategies, in which randomness comes into play, with newer strategies that are more deterministic.
"We found there is a better way to solve the problem than to color the connections between points at random," says Conlon. "We blended this approach with one where we know exactly what we are coloring a certain color."
Conlon says he is now returning to the problem of two-color Ramsey numbers. For his PhD work in 2009, he made the first significant improvements since 1935 in the reduction of the uncertainty of the solutions. To really make dramatic improvements for this type of problem, he says, something entirely new is needed.
"The two-color case is likely to require such a substantial new idea that I think the math would prove useful in other unsolved math problems," says Conlon. "In math, you start out because you are interested in the thing for its own sake, but further down the line, it becomes important or interesting for other reasons."
The study, titled, "Lower bounds for multicolor Ramsey numbers," was funded by the National Science Foundation.