Polynomial Bounds for the Grid-Minor Theorem

Julia Chuzhoy, TTI
Fine Hall 214

THIS IS A SPECIAL PACM COLLOQUIUM.  One of the key results in Robertson and Seymour's seminal work on graph minors is the Grid-Minor Theorem (also called the Excluded Grid Theorem). The theorem states that for every fixed-size grid H, every graph whose treewidth is large enough, contains H as a minor. This theorem has found many applications in graph theory and algorithms. Let f(k) denote the largest value, such that every graph of treewidth k contains a grid minor of size f(k). Until recently, the best quantitative bound, due Kawarabayashi and Kobayashi, and Leaf and Seymour, showed that: f(k)=\Omega(\sqrt{\log k / \log \log k}).The best known upper bound implies that f(k)=O(\sqrt{k/ \log k}). In this talk we present the first polynomial relationship between treewidth and grid-minor size, by showing that: f(k) = \Omega(k^d), for some fixed constant d > 0. Joint work with Chandra Chekuri.