PIMS Network Wide Colloquium: Maria Chudnovsky
Event Recap
A recording of this event is available on mathtube.org.
Topic
Tree decompositions: representing a graph by a tree
Speakers
Details
How does one describe the structure of a graph? What is a good way to measure how complicated a given graph is? Tree decompositions are a powerful tool in structural graph theory, designed to address these questions. To obtain a tree decomposition of a graph G, we break G into parts that interact with each other in a simple ("tree-like") manner. But what properties do the parts need to have in order for the decomposition to be meaningful? Traditionally a parameter called the "width" of a decomposition was considered, that is simply the maximum size of a part. In recent years other ways of measuring the complexity of tree decompositions have been proposed, and their properties are being studied. In this talk we will discuss recent progress in this area, touching on the classical notion of bounded tree-width, concepts of more structural flavor, and the interactions between them.
Additional Information
Maria Chudnovsky is a prominent mathematician known for her work in graph theory and combinatorics. Her work on the proof of the strong perfect graph theorem won for her and her co-authors the 2009 Fulkerson Prize. She earned her degrees from the Technion and Princeton University, and holds a position at Princeton University, having previously taught at Columbia University. A recipient of a 2012 MacArthur Fellowship, her research focuses on the structure of graphs and has real-world applications in areas such as transportation and computer networks.