TIME: 1:30 -- 2:30 pm, Tuesday, Feb 3, 2009

SPECIAL PLACE: CSE 503

SPEAKER: James Lee, University of Washington

TITLE: Random embeddings, topological complexity, and the geometry of graphs

ABSTRACT:

It's not too difficult to show that the vertices of an n-cycle cannot
be mapped into a tree without significantly distorting the pairwise
distances.  On the other hand, deleting a uniformly random edge of the
cycle preserves every pairwise distance up to a factor of 2 in
*expectation*.

How general is this phenomenon?  If we identify an arbitrary subset of
nodes in a tree, can the resulting object still be randomly embedded
into a tree?  What about the same question, where "tree" is replaced
by "planar graph"?  In this talk, I will address (and largely resolve)
the general problem of reducing "topological complexity" via random
embeddings.  The fact that this actually works is somewhat surprising,
given that most previous results in this area had been negative.

The primary application of our techniques is to a widely-studied
conjecture of Gupta, Newman, Rabinovich, and Sinclair, about
generalizations of the max-flow/min-cut theorem in graphs. One of our
main tools arises out of a connection with the Lipschitz extension
problem, and motivates our construction of probabilistic versions of
some classical objects from analysis (e.g. random Whitney
decompositions).