Discrete Applied Mathematics Seminar by Sophie Spirkl: Treewidth and Complete Bipartite Induced Minors

Speaker: Sophie Spirkl, associate professor of combinatorics and optimization, University of Waterloo

Title: Treewidth and Complete Bipartite Induced Minors

Abstract: I will talk about treewidth, which is one measure of the complexity of a graph, both in terms of structure and algorithms. While subgraphs that cause large treewidth are completely understood (due to Robertson and Seymour), the same cannot be said for induced subgraphs. I will talk about recent progress on this, which is related to a question about words. Joint work with Maria Chudnovsky and Sepehr Hajebi. 

 

Discrete Applied Math Seminar

Request Zoom Link