Computer Science/Discrete Mathematics Seminar I

One of the key results in Robertson and Seymour's seminal work on graph minors is the Grid-Minor Theorem (also known as the Excluded Grid Theorem). The theorem states that any graph of treewidth at least \(k\) contains a grid minor of size \(f(k)\) for some function \(f\). This theorem has found many applications in graph theory and algorithms. The best current quantitative bound, due to recent work of Kawarabayashi and Kobayashi, and Leaf and Seymour, shows that \(f(k)=\Omega(\sqrt{\log k/\log \log k})\), while 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^{\delta})\) for some fixed constant \(\delta > 0\), and also describe an efficient algorithm to construct such a minor. Joint work with Chandra Chekuri.