Posts
 |
| MIT Assistant Professor Yufei Zhao (far right) gave undergraduates (l-r) Mehtaab Sawhney, David Stoner, and Ashwin Sah a particularly vexing combinatorics problem. Their theorem on the number of independent sets in a graph is on the board behind them. Photo: courtesy of Yufei Zhao |
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...
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.”
Read more...
Source: MIT News
