[Colloquium] Tan/MS Presentation/Oct 5, 2018
Margaret Jaffey via Colloquium
colloquium at mailman.cs.uchicago.edu
Thu Sep 20 11:21:34 CDT 2018
This is an announcement of Zihan Tan's MS Presentation.
------------------------------------------------------------------------------
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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
More information about the Colloquium
mailing list