UofT Mathematics Logo

Department of Mathematics Seminars and Talks

 
Seminar

Combinatorics Seminar

Talk Information
Title
Induced minors and treewidth
Start date and time
10:00 on Tuesday November 24, 2026
Duration in minutes
60 (until 11:00 on Tuesday November 24, 2026)
Room
Virtual
Streaming password
202834
External video link
Abstract

This talk deals with induced minor obstructions to treewidth. The natural setup for this problem is to consider the class of graphs excluding some planar graph, and some complete bipartite graph as induced minors, and some complete graph as a subgraph. Unfortunately, such classes still contain graphs of arbitrarily large treewidth. Moreover, a result of Alecu, Bonnet, Bureo Villafana and Trotignon and its extensions suggest that there is unlikely to be an elegant characterization of families of bounded treewidth in terms of induced obstructions. On the other hand, it is conjectured that graphs in the classes as above have treewidth bounded by a poly-logarithmic function of their number of vertices. If true, this will imply the existence of quasi-polynomial time algorithms for a host of problems on such classes that are NP-complete in the general setting. While this conjecture remains open, in joint work with Julien Codsi, David Fischer and Daniel Lokshtanov, we were able to prove the existence of a sub-polynomial bound on treewidth in terms of the number of vertices. This in turn leads to sub-exponential algorithmic behavior. In this talk we will discuss some ideas of the proof, and, if time permits, some results in the more general setting when the bound on the clique size is removed.

Speaker Information
Full Name
Maria Chudnovsky
Institution
Princeton University
Institution URL