[Discrete-math-seminar] Year-end Networks and Optimization seminar: Tasos Sidiropoulos Dec. 7
rellis at math.iit.edu
Mon Nov 23 11:53:31 CST 2009
Monday Dec. 7th, 12:50-1:40pm, E1 119
Networks and Optimization seminar
Anastasios Sidiropoulos, TTI -- Chicago
Title: Graph genus and random partitions (Abstract below)
We have a very nice upcoming Networks and Optimization talk by Anastasios
(Tasos) Sidiropoulos to round out the year. Tasos is currently at Toyota
Technological Institute at Chicago, and did his PhD work at MIT. He will be
speaking about random partitioning schemes in graphs with small genus, with
applications to multi-commodity network flow; and approximating treewidth,
graph eigenvalues, Lipschitz extensions over Banach spaces, and distortion
of planar embeddings of graphs.
*All faculty interested in a 30-minute research discussion with Tasos are
invited to sign up on Doodle: http://www.doodle.com/wktaprm2r6affb9t.* Be
sure to write in your name and email address, and I will notify you of the
location of the meeting in E1 building.
Feel free to send me an email with any questions. I hope you will join us.
We study the quantitative geometry of graphs with small genus. In
particular, we exhibit new, optimal random partitioning schemes for such
graphs. Using these geometric primitives, we give exponentially improved
dependence on genus for a number of problems like approximate
max-flow/min-cut theorems, approximations for uniform and non-uniform
Sparsest Cut, treewidth approximation, Laplacian eigenvalue bounds,
Lipschitz extension theorems, and various embeddings into normed
We list here a sample of these improvements. All the following statements
refer to graphs of genus g.
- We show that such graphs admit an O(log g)-approximate multi-commodity
max-flow/min-cut theorem for the case of uniform demands. This bound is
optimal, and improves over the previous bound of O(g). For non-uniform
demands, we give a bound of O(sqrt(log g)(log n)), improving over the
previous bound of O(sqrt(g
- We give an O(log g)-approximation for treewidth, improving over the
previous bound of O(g).
- If a graph G has genus g and maximum degree D, the k-th Laplacian
eigenvalue of G is (log g)^2 * O(k g D/n), improving over the previous bound
of g^2 * O(k g D/n). There is a lower bound of Omega(kgD/n), making this
result almost tight.
- We show that if (X,d) is the shortest-path metric on a graph of genus g
and S is a subset of X, then every L-Lipschitz map f : S -> Z into a Banach
space Z admits an O(L log g)-Lipschitz extension f' : X -> Z. This improves
over the previous bound of O(Lg), and compares to a lower bound of Omega(L
sqrt(log g)). In a related way, we show that there is an O(log
g)-approximation for the 0-extension problem on such graphs, improving over
the previous O(g) bound.
- We show that if planar graphs embed into L_1 with O(1) distortion, then
graphs of genus g embed into L_1 with O(log g) distortion, improving over
the previous conditional bound of O(g^2). This is conditionally tight, as
there is an Omega(log g) lower bound. We also show that every n-vertex
shortest-path metric on a graph of genus g embeds into L_2 with distortion
O(sqrt((log g)(log n))), improving over the
previous bound of O(sqrt(g log n)).
Joint work with James R. Lee.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Discrete-math-seminar