| Monday, March 17th, 2014 | 4pm-5pm | Burnside 1205 |
The seminal work of Robertson and Seymour on graph minors introduced tree decompositions and treewidth. One of their key results is the Excluded Grid Theorem which states that every graph G with treewidth at least k contains a f(k) x f(k) grid-minor for some (slowly growing) function f. Treewidth has since become a fundamental tool for structural and algorithmic results on graphs. In this talk we will discuss some recent developments on the structure of graphs with large treewidth. These development were motivated by the study of polynomial-time approximation algorithms for the maximum disjoint paths problem, culminating in a breakthrough by Chuzhoy in 2011. Subsequent work, building upon some of her ideas and other prior tools, has led to several new results. A highlight is a polynomial relationship between treewidth of a graph and the size of its largest grid-minor. A key technical tool is a theorem stating that a graph with treewidth k can be partitioned into h disjoint subgraphs each with treewidth at least r as long k \ge poly(h,r) polylog(k). This tool by itself gives several interesting applications to Erdos-Posa type theorems and fixed parameter tractable algorithms. The purpose of the talk is to state and explain the main results and give a high-level overview of the technical ingredients in the improved grid-minor theorem. Based on joint work with Julia Chuzhoy.