In 2009, when Yufei Zhao was an MIT undergraduate, he was intrigued by a 2001 conjecture by Rutgers University mathematician Jeff Kahn regarding the number of independent sets in a graph. An independent set in a graph is a subset of vertices such that no two of them are joined by an edge.
“Many important structures can be modeled using independent sets,” said Zhao. “For example, if the graph models some kind of incompatibility, then an independent set represents a mutually compatible collection.”
Zhao was participating in a Research Experience for Undergraduates (REU) summer program in Duluth, Minnesota, and while he was researching what would be one of his first math research papers, he came across a combinatorics problem by Kahn. The problem puzzled him. An attempt to solve it came close, as he described in a paper he wrote with David Galvin in 2010 titled, “The number of independent sets in a graph with small maximum degree.”
Yufei Zhao graduated in 2010, received his PhD in 2015, and is now the Class of 1956 Career Development Assistant Professor at MIT. His focus is on combinatorics, discrete mathematics, and graph theory.
Through the years, that conjecture continued to nag at him, so last spring, Zhao decided to pass on the challenge to his “fearless” student mathematicians, sophomore Ashwin Sah and junior Mehtaab Sawhney.
Harvard senior David Stoner, who Sawhney coincidentally befriended at that REU program in Duluth, also takes combinatorics classes at MIT. When he heard about his friends’ project, he asked to join in.
Zhao recalls that, over the course of a month, they debated their ideas online as well as at many a late-night marathon session in Building 2, “where they tore apart one inequality after another.”
“To my amazement, they came to me with a solution of this old conjecture,” he says. “Lots of experienced mathematicians have worked on this conjecture without success.”
To cap off their success, they have published a paper — “The number of independent sets in an irregular graph” — in Journal of Combinatorial Theory, Series B, a leading journal in combinatorics.
“The approach in the paper, while not very difficult, ends ups being very technical,” says Sawhney. “Figuring out how to handle all the various terms that appear in our proof and reduce them into a manageable form plays a key role.”
Adds Stoner: “Probably the most challenging part in retrospect was discovering a particular application of Holder's Inequality. This allowed for the inductive inequality to be transformed into something completely local.”
For Sah, the hardest part was “figuring out the right approach and framing, and understanding the theorem in the correct way.”
“Once we believed that the ‘local inequality’ was true, it allowed us to view the problem in a very different way compared to what was already known, and although there are still lots of difficulties beyond this realization, it definitely underpins the whole effort,” Sah says.
Kahn was excited with the results. “It was great to see my old conjecture finally resolved, and even better to see what it led to. Some of the problems settled by Yufei and company had been tried by some excellent, much more experienced people. Of course, having a fresh young mind can also be an advantage.”
Zhao, for his part, is now happy to check that conjecture off his bucket list. But he is even happier to have students like them in his combinatorics class.
“The students are amazing,” he says. “They are constantly asking questions and bombarding me with ideas. I have learned so much from them.”
The techniques that they found to solve that conjecture quickly led to work on several related problems, including for their upcoming paper “A Reverse Sidorenko Inequality,” related to graph colorings and graph homomorphisms. Explains Zhao: “This paper solves several open problems concerning graph colorings and homomorphisms, including one of my favorite problems regarding maximizing the number of q-colorings in a d-regular graph.”
The three students are prolific. Sawhney has written 12 papers so far, including four others with Stoner, and another with Sah, who is the author or coauthor of six papers in total. Stoner has eight papers so far.
“They are incredible,” said Zhao. “Most graduate students don’t have as many papers.”
All three enjoy working together. “Often we discuss ideas over the phone or in person and tend to communicate ideas quickly even if they are only half-baked,” Sawhney says. “This leads to always feeling as if there is something else to try on a problem we are working on.”
Adds Stoner: “When it comes time to execute these ideas in detail, we generally try to play to each of our individual strengths.”
Ashwin describes their dynamic as “pretty relaxed,” using Slack and other online mediums to discuss ideas and debate the shortcomings of various methods when they can’t meet up in person. “There's definitely always something happening and something to think about,” he says.
Sah says that collaborative atmosphere is what attracted him to MIT.
“I'm definitely grateful to be able to work with this particular group of people on combinatorics research,” he says.
