Julia Chuzhoy: Excluded Grid Theorem: Improved and Simplified

Abstract:  One of the key results in Robertson and Seymour's seminal work on graph
minors is the Excluded Grid Theorem. The theorem states that there is a
function f, such that for every positive integer g, every graph whose
treewidth is at least f(g) contains the (gxg)-grid as a minor. This theorem
has found many applications in graph theory and algorithms. An important
open question is establishing tight bounds on f(g) for which the theorem
holds. Robertson and Seymour showed that f(g)\geq \Omega(g^{^2} log g), and
this remains the best current lower bound on f(g). Until recently, the best
upper bound was super-exponential in g. In this talk, we will give an
overview of a recent sequence of results, that has lead to the best current
upper bound of f(g)=O(g^{19}polylog(g)). The main emphasis will be on
presenting a simple proof of the theorem that achieves a bound that is
polynomial in g. We will also outline some techniques that allow us to
achieve the best current bounds.