[Colloquium] Research at TTIC: Friday, May 10th at Noon

[Dawn Ellis]

When:     Friday, May 10th at 12:00pm -1:30pm

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

Who:     Julia Chuzhoy, Associate Professor at TTIC

Title:      Polynomial Bounds for the Grid-Minor Theorem

Abstract:

One of the key results in Robertson and Seymour's seminal work on the Graph
Minor Theory is the Grid-Minor Theorem. The theorem states that any graph
of tree width at least k contains a grid minor of size f(k), for some
function f. This theorem has found many applications in both graph theory
and algorithms. The best current quantitative bound, due to Leaf and
Seymour, is f(k)=\Omega(log k/log log k). In this talk we describe an
ongoing work with Chandra Chekuri, geared towards obtaining a polynomial
bound f(k)=\Omega(k^{\epsilon}) for some constant \epsilon.

***************************************
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 Nati Srebro at nati at ttic.edu.

-- 
*Dawn Ellis*
Administrative Assistant
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20130503/34c478b7/attachment.htm