2019年9月16日上午，芝加哥大学Zihan Tan访问北京大学前沿计算研究中心，并在静园五院做了题为 “Towards Tight(er) Bounds for the Excluded Grid Theorem”的学术报告。报告由中心助理教授孔雨晴老师主持，听众包括来自北京大学前沿计算研究中心及北京大学信息科学技术学院的师生。

Abstract: 

We study the Excluded Grid Theorem, a fundamental structural result in graph theory, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem states that there is a function f, such that for every integer g > 0, every graph of treewidth at least f(g) contains the g×g-grid as a minor. For every integer g>0, let f(g) be the smallest value for which the theorem holds. Establishing tight bounds on f(g) is an important graph-theoretic question. Robertson and Seymour showed that f(g) is at least of order g^2 log g. For a long time, the best known upper bounds on f(g) were super-exponential in g. The first polynomial upper bound of f(g) = O(g^98 poly log g) was proved by Chekuri and Chuzhoy. It was later improved to f(g) = O(g^36 poly log g), and then to f(g) = O(g^19 poly log g). In this talk we present our recent work that further improves this bound to f(g) = O(g^9 poly log g) via a simpler proof. Moreover, while there are natural barriers that seem to prevent the previous methods from yielding tight bounds for the theorem, it seems conceivable that the techniques proposed in this talk can lead to even tighter bounds on f(g).

This talk is based on joint work with Julia Chuzhoy.

Biography: 

Zihan Tan is a graduate student in the Computer Science Department of the University of Chicago, advised by Professor László Babai, and co-advised by Professor Julia Chuzhoy at Toyota Technological Institute at Chicago. His research interests span the areas of algorithms, combinatorial optimization and computational complexity. He is currently working on graph-theoretic problems, especially on exploring the relationship between structural notions of general graphs and designing approximation algorithms for graph routing problems. Zihan holds Bachelor’s degrees in Computer Science and in Mathematics from Tsinghua University. Prior to starting his graduate studies, he worked as a research intern at Microsoft Research Asia under the supervision of Wei Chen, and as a research assistant student at the Chinese University of Hong Kong under the supervision of Shengyu Zhang.