[Colloquium] Reminder: Tan/MS Presentation/Oct 5, 2018

[Margaret Jaffey via Colloquium]

This is a reminder about Zihan Tan's MS Presentation tomorrow.

------------------------------------------------------------------------------
Date:  Friday, October 5, 2018

Time:  10:30 AM

Place:  JCL (Crerar Library) 298

M.S. Candidate:  Zihan Tan

M.S. Paper Title: Excluded Grid Theorem: Improved Bounds

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 : Z → Z, 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) =
Ω(g^2log g) must hold. 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 thesis we further improve 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 thesis can lead to even tighter bounds on
f(g).

Zihan's advisors are Prof. Laszlo Babai and Prof. Julia Chuzhoy

Login to the Computer Science Department website for details:
 https://www.cs.uchicago.edu/phd/ms_announcements#zihantan

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey            margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)               (773) 702-6011
The University of Chicago      http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=