UCSB CS Theory Colloquium Series

UCSB CS Distinguished Lecture

CS Theory Colloquium Series

Spring 2023

Wednesday, June 7th, 3:30pm Henley Hall room 1010 (auditorium)

Speaker: Maria Chudnovsky (Princeton)

Title: Induced subgraphs and tree decompositions

Abstract: Tree decompositions are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”. Exhibiting a particular kind of a tree decomposition is also a useful way to describe the structure of a graph.

Tree decompositions have traditionally been used in the context of forbidden graph minors; bringing them into the realm of forbidden induced subgraphs has until recently remained out of reach. Over the last couple of years we have made significant progress in this direction, exploring both the classical notion of bounded tree-width, and concepts of more structural flavor. This talk will survey some of these ideas and results.

Bio: Maria Chudnovsky received her B.A. and M.Sc. from the Technion, and a PhD from Princeton University in 2003. Currently she is a professor at Princeton. Before returning to Princeton in 2015, she was a Veblen Research Instructor at Princeton University and the IAS, an assistant professor at Princeton, a Clay Mathematics Institute research fellow, and a Liu Family Professor of IEOR at Columbia University. Her research interests are in graph theory and combinatorics. She is an editorial board member of several journals in her field. Dr. Chudnovsky was a part of a team of four researchers that proved the strong perfect graph theorem, a 40-year-old conjecture that had been a well-known open problem in both graph theory and combinatorial optimization. For this work, she was awarded the Ostrowski foundation research stipend in 2003, and the prestigious Fulkerson prize in 2009. She was also named one of the "brilliant ten" young scientists by the Popular Science magazine. In 2012, Dr Chudnovsky received the MacArthur Foundation Fellowship. In 2014, she was an invited speaker at the International Congress of Mathematicians. In 2022 she was elected foreign member of Academia Europaea.