*********************************** * Princeton Discrete Math Seminar * *********************************** Date: Thursday 6th February, 4:30 in Fine Hall 224. Speaker: Julia Chuzhoy (TTI Chicago) Title: Polynomial bounds for the grid-minor theorem One of the key results in Robertson and Seymour's seminal work on graph minors is the grid-minor theorem, that every graph of sufficiently large treewidth contains any fixed grid as a minor. This theorem has found many applications in graph theory and algorithms. Let f(k) be maximum such that every graph of treewidth at least k contains a grid minor of size f(k). The best current quantitative lower bound, due to recent work of Kawarabayashi and Kobayashi, and Leaf and Seymour, shows that f(k) = Omega(sqrt{ log k / loglog 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^d) for some constant d > 0. Joint work with Chandra Chekuri. ----------- Next week: Alex Scott Anyone wishing to be added to or removed from this mailing list should contact Paul Seymour (pds@math.princeton.edu)