Deep Mathematics and Simple Fun

Ramsey Theory advancements highlight the 21st Random Structures & Algorithms Conference

Applications to Ramsey Theory is one of the central topics in the mathematical field of random structures and algorithms. Two major breakthroughs occurred prior to Carnegie Mellon University hosted the 21st International Conference on Random Structures & Algorithms in mid-June, allowing researchers to present the new findings in Pittsburgh.

"There's a famous anecdote of Paul Erdös who once said if aliens come to the planet Earth and say, 'We're going to destroy you unless you tell us to determine the diagonal Ramsey number R(5,5),' we should put all the world's computers and minds behind an answer," said Prasad Tetali, head of the Department of Mathematical Sciences at Carnegie Mellon. "If they demand that we determine R(6,6), we should instead try to get rid of the aliens."

Diagonal Ramsey numbers quantify how large a graph has to be to ensure that the graph or its complement contains a group, known as a clique, of a certain size.

For example, if a mathematician wants to host a party, and they want to guarantee that there will either be a group that all know each other or a group of mutual strangers, Ramsey Theory helps them determine how large that party would have to be for these cliques to emerge. Based on the patterns that Ramsey Theory produces, if a mathematician wanted a clique of 3, they would have to host a party of 6 people. If they wanted a clique of 4, they would have to host a party of 18 people. However, researchers are unsure of the numbers of guests needed to ensure larger cliques of 5 or more.

Julian Sahasrabuddhe, of the University of Cambridge, spoke about how he and colleagues improved the upper bound on the Ramsey number by an exponential amount, the first significant improvement in nearly 90 years.

Sam Mattheus, a postdoctoral researcher at the University of California, San Diego, also presented a breakthrough by himself and UCSD Professor Jacques Verstraete which applies constructions from finite geometry and settles a part of the Ramsey theory that had been proposed in 1947.

"We were thrilled to have talks on two exciting breakthrough results in Ramsey theory that came in the last few months," said Tom Bohman, a professor of mathematical sciences at Carnegie Mellon and a conference organizer. "The questions that these results answer were among the most important in the field of combinatorics for nearly a century. It will be interesting to see how things develop over the next few months and years as the community digests the new ideas needed to produce these breakthrough results."

The conference also featured presentations on major advances regarding phase transitions in discrete probability theory, mixing times of Markov chains and concentration of random variables defined on the random graph.

"It's always been a lively meeting with people coming in," said Joel Spencer, a mathematician and computer scientist at New York University who has attended the biennial conference since it began in 1983. "The use of probability has gotten much deeper. Originally, it was very simple probability, and now, there are a lot of deep methods, things like Brownian motion that are being used."

Between lectures on mathematical theories and findings, the participants took to Carnegie Mellon's Gesling Stadium track for the Random Run, a conference tradition.

"The Random Run is such an original idea and felt like it combined my love of running with my love of game theory," said Jacob Lehmann Duke, an undergraduate student from Williams College who won first place in the all men's category. "I run cross country and track for Williams, so I'm used to races, but I don't think I've ever run one with as enthusiastic and diverse a set of participants. I am particularly impressed with the people who ran the original Random Run in 1983 and were back toeing the line."

This was the second time that the conference was held at Carnegie Mellon. In 2015, the Department of Mathematics hosted Random Structures & Algorithms Conference in celebration of Professor of Mathematical Sciences Alan Frieze's 70th birthday. He said he was pleased with the growth of the field.

"There's no shortage of places where this sort of analysis can be used," Frieze said. "The probabilistic method is creeping into all other areas of mathematics, and it's very powerful."

The conference was supported by the Carnegie Mellon Department of Mathematical Sciences, the National Science Foundation and the National Security Agency. Organizers and attendees made use of infrastructure for running scientific meetings that was recently established by the Mellon College of Science.