[Colloquium] Research at TTIC: Julia Chuzhoy, TTIC

[Mary Marre]

When:     Friday, June 12th at noon

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:        Julia Chuzhoy, TTIC

Title:       On Large-Treewidth Graphs, Grid Minors, and Treewidth
Sparsifiers


*Abstract:*

This talk consists of two parts. In the first part I will show a new, and a
much simpler, proof of a polynomial bound for the well-known Grid-Minor
Theorem of Robertson and Seymour. In the second part, I will describe a
construction of treewidth sparsifiers: given a graph G of treewidth k, we
show how to find a minor H of G whose treewidth is at least k/polylog k,
such that H contains at most O(k^4) vertices, and its maximum vertex degree
is 3. The second part is based on joint work with Chandra Chekuri.


***************************************
Research at TTIC Seminar Series

TTIC is hosting a weekly seminar series presenting the research currently
underway at the Institute. Every week a different TTIC faculty member will
present their research.  The lectures are intended both for students
seeking research topics and adviser, and for the general TTIC and
University of Chicago communities interested in hearing what their
colleagues are up to.

To receive announcements about the seminar series, please subscribe to the
mailing list: https://groups.google.com/a/ttic.edu/group/talks/subscribe

Speaker details can be found at: http://www.ttic.edu/tticseminar.php.

For additional questions, please contact David McAllester at
mcallester at ttic.edu


Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL  60637*
*p:(773) 834-1757 <%28773%29%20834-1757>*
*f: (773) 357-6970 <%28773%29%20357-6970>*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150608/63a9d98b/attachment.htm