Abstractions blog

Undergraduate Math Student Pushes Frontier of Graph Theory

By Kevin Hartnett

November 30, 2020

At 21, Ashwin Sah has produced a body of work that senior mathematicians say is nearly unprecedented for a college student.

Ashwin Sah stands in AmberGlen park, near his hometown of Portland, Oregon, where he’s been spending time during the pandemic.

Celeste Noche for Quanta Magazine

On May 19, Ashwin Sah posted the best result ever on one of the most important questions in combinatorics. It was a moment that might have called for a celebratory drink, only Sah wasn’t old enough to order one.

The proof joined a long list of mathematical results that Sah, who turned 21 in November, published while an undergraduate at the Massachusetts Institute of Technology (he posted this new proof just after graduating). It’s a rare display of precocity even in a field that celebrates youthful genius.

“He has done enough work as an undergraduate to get a faculty position,” said David Conlon of the California Institute of Technology.

The May proof focused on an important feature of combinatorics called Ramsey numbers, which quantify how big a graph (a collection of dots, or vertices, connected by edges) can get before it necessarily contains a certain kind of substructure.

For example, imagine you’ve got six vertices, each connected to every other vertex by edges. Now color each of the 15 total edges either red or blue. No matter how you apply the colors, it’s inevitable that you’ll end up with three vertices that are all connected to each other by edges of the same color (known as a “clique”). The same is not true, however, if you start with five vertices (for which it’s possible to do the coloring without creating a clique). As a result, mathematicians say that the Ramsey number for two colors and a clique of size 3 is 6 — meaning you need at least six vertices to guarantee the clique exists.

As the size of the clique you’re looking for grows bigger, it becomes very difficult to calculate exact Ramsey numbers. Instead, mathematicians try to zero in on them by guaranteeing that the Ramsey number for a clique of some arbitrary size is greater than some number (the “lower bound”) and less than another (the “upper bound”).

Paul Erdős and George Szekeres initiated the study of upper and lower bounds for Ramsey numbers in the 1930s. Since then, mathematicians have made relatively little progress on either one — though Quanta recently covered an innovative new proof that set the best-ever lower bound for some Ramsey numbers.

In May, Sah showed that a graph can only get so big before it must contain certain patterns, pushing the existing line of research to its limits.

Celeste Noche for Quanta Magazine

Sah’s proof, in contrast, improved the upper bound for two-color Ramsey numbers. He achieved it by optimizing a method that originated with Erdős and Szekeres, and which a small number of mathematicians have managed to improve since. Sah’s result proves that once a graph reaches a certain size, it inevitably contains a clique of some corresponding size. Many in the field see Sah’s proof as the best result that can be achieved using the existing line of research.

“He’s pushing the method to its logical limit,” said Conlon, who had set the previous best upper bound on the problem.

A Life of Math

Sah grew up in Portland, Oregon, and liked math from a young age. “Some of my earliest memories are of my mom teaching me basic arithmetic,” he said.

He got his first taste of advanced math in competitions, where he excelled. In the summer of 2016, when he was 16, he won a gold medal at the International Mathematical Olympiad in Hong Kong. The next year he enrolled at MIT (he’d graduate two and a half years later).

While there, Sah made two connections that were crucial for his mathematical development. The first was with a professor named Yufei Zhao. Sah took two classes with him during his first year at MIT, including a graduate-level seminar on combinatorics. Even among some of the most talented math students in the world, Sah stood out.

“He’d clearly mastered the material even though he was just a first-year in college,” said Zhao.

The second connection was with Mehtaab Sawhney, now 22. Sawhney was a year ahead of Sah and had transferred to MIT that fall from the University of Pennsylvania. They met in class in September and became friends.

By the spring they were doing research together. They worked on a range of topics within discrete mathematics like graph theory, probability and the properties of random matrices. Many of the problems they tackled were relatively simple to state and could be approached directly, without needing the years of formal training that they didn’t yet have.

“I like the kinds of problems that you can think about from first principles and you don’t need to have read a massive amount of literature or know a ton of theory to start thinking about it,” said Sawhney.

They worked closely with Zhao, who suggested research questions and coached them on how to write formal math papers. Often Zhao would ask them to look into a particular problem, thinking it might keep them busy for a while — only to have them return the next day with an answer.

Ashwin Sah, 21, compiled a nearly unparalleled body of math research as an undergraduate at MIT.

Celeste Noche for Quanta Magazine

“They’re both incredibly energetic individuals. I throw out a question and I hear back almost immediately,” Zhao said.

Over the past three years Sah and Sawhney have written dozens of papers, many of them together. This fall they were announced as winners of the 2021 Morgan Prize, jointly given out each year by leading math organizations to recognize the best research by undergraduate mathematicians. Zhao remarked that there is no recent precedent for what they have accomplished.

“There is a long tradition of undergraduate research, but nothing quite at the level of Ashwin and Mehtaab in quantity and quality,” he said.

Sah and Sawhney are now first-year graduate students at MIT, though due to the pandemic they’re currently on opposite coasts. Sah is back in Portland and Sawhney is on Long Island in New York, where he grew up. But they’re still in almost ceaseless contact.

“We meet once or twice a day for five or six hours,” said Sawhney. “Even when we’re not meeting, we’re just constantly messaging each other.”

They say they don’t feel burdened by their early success. If anything, it motivates them to surpass it.

“I guess I try not to focus on the past,” said Sah. “I’m always sort of looking forward to what I can do next.”

from Hacker News https://ift.tt/3mrfxI4