16 Apr – Maria Chudnovsky: Induced subgraphs and tree decompositions (Kovalevskaya Colloquium)
Tree decompositions are a powerful tool in structural graph theory; they are traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has until recently remained out of reach. Tree decompositions are closely related to the existence of “laminar collections of separations” in a graph, which roughly means that the separations in the collection “cooperate” with each other, and the pieces that are obtained when the graph is simultaneously decomposed by all the separations in the collection “line up” to form a tree structure. Such collections of separations come up naturally in the context of forbidden minors.
In the case of families where induced subgraphs are excluded, while there are often natural separations, they are usually very far from forming a laminar collection. In what follows, Chudnovsky will mostly focus on families of graphs of bounded degree. It turns out that due to the bound on the degree, these collections of natural separations can be partitioned into a bounded number of laminar collections. This in turn results in a wide variety of structural and algorithmic results, which will be surveyed in this talk.
Maria Chudnovsky received her 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 was also named one of the “brilliant ten” young scientists by the Popular Science magazine. In 2012, Chudnovsky received the MacArthur Foundation Fellowship. In 2014, she was an invited speaker at the International Congress of Mathematicians.
