• This event has passed.

# Zihan Tan, Towards Tight(er) Bounds for the Excluded Grid Theorem

## Thursday, September 24, 2020 @ 10:00 AM - 11:00 AM KST

Zoom ID: 869 4632 6610 (ibsdimag)

### Speaker

Zihan Tan
Department of Computer Science, University of Chicago

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} \operatorname{poly log} g)$ was proved by Chekuri and Chuzhoy. It was later improved to $f(g) = O(g^{36} \operatorname{poly log} g)$, and then to $f(g) = O(g^{19} \operatorname{poly log} g)$. In this talk, we present our recent work that further improves this bound to $f(g) = O(g^9 \operatorname{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.

## Details

Date:
Thursday, September 24, 2020
Time:
10:00 AM - 11:00 AM KST
Event Category:
Event Tags:

## Venue

Zoom ID: 869 4632 6610 (ibsdimag)

## Organizer

O-joung Kwon (권오정)
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209