Perfection and Beyond
About 10 years ago one of the central open problems in graph theory at the time, the Strong Perfect Graph Conjecture, was solved. The proof used structural graph theory methods, and spanned 155 journal pages. Maria Chudnovsky was part of the team of authors of this mathematical beast. In this talk, she will explain the problem, describe some of the ideas of the proof—that has since been shortened somewhat—and discuss related problems that have been a subject of more recent research.
Friday, October 5, 2012
1:30-2:30 p.m.
Brickyard Artisan Court 110
School of Computing, Informatics, and Decision Systems Engineering
Distinguished Guest Lecturer Maria Chudnovsky
Hosted by Arunabha Sen
Bio
Maria Chudnovsky received her bachelor’s and master’s degrees from the Technion, and a doctorate from Princeton University in 2003. Currently she is an associate professor at Columbia University. Before that she was a Veblen Research Instructor at Princeton University and the IAS, and then an assistant professor at Princeton. Until April 2008 she was a Clay Mathematics Institute research fellow. Her research interests are in graph theory and combinatorial optimization. In 2009 she was awarded the Fulkerson Prize, as part of a team of researchers, for their proof of the Strong Perfect Graph Theorem, a forty-year old conjecture, that had been a well-known open problem in both graph theory and combinatorial optimization.
