# Polynomial Bounds for the Grid-Minor Theorem

 Computer Science/Discrete Mathematics Seminar I Topic: Polynomial Bounds for the Grid-Minor Theorem Speaker: Julia Chuzhoy Affiliation: Toyota Technological Institute at Chicago Date: Monday, February 10 Time/Room: 11:15am - 12:15pm/S-101 Video Link: https://video.ias.edu/csdm/2014/0210-JuliaChuzhoy

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.