[Colloquium] Theory Seminars at Computer Science

[Donna Brooms via Colloquium]

Departments of Computer Science & Mathematics
Combinatorics & Theoretical Seminar

Tuesday, March 28, 2017
Ryerson 251 @ 3pm

James R. Lee
University of Washington
http://www.cs.washington.edu/homes/jrl/

Title: Extremal metrics, eigenvalues, and graph separators 

Abstract:
It is well-known that endowing a graph with a suitable geometric represention is useful in studying its isoperimetric structure.  For instance, the planar separator theorem follows readily from the Koebe-Andreev-Thurston circle packing theorem (every planar graph is the tangency graph of interior-disjoint disks in the plane). 

Even when there is not a natural ambient geometry, one can deform the intrinsic graph metric by choosing a suitable extremal path metric from a given class.  This is very familiar to computer scientists in the form of LP and SDP relaxations for various optimization problems.  We consider conformal weightings of the underlying graph that minimize an associated "area" functional.  Such metrics often yield detailed information about the Laplacian spectrum and isoperimetric profile. 

For example, we will confirm a conjecture of Fox and Pach (2010) that every string graph with m edges has a balanced separator of size O(\sqrt{m}).  (String graphs are the intersection graphs of continuous arcs in the plane.)  This is a consequence of a more general result on separators in "region intersection graphs" that generalizes the Alon-Seymour-Thomas separator theorem. 

[This talk also serves as an introduction to graph uniformization for the Math colloquium (29-Mar), where related methods will be applied to analyze the structure of discrete models for 2D quantum gravity.]

Host:  Prof. Alexander Razborov
Refreshments will be served prior to the talk at 2:30 in Ry. 255

 

 


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20170316/4b6e3476/attachment.html>