Seminar: November 3

Anastasios Sidiropoulos, TTIC

Graph Genus and Random Partitions

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 spaces.

We list here a sample of these improvements. All the following statements refer to graphs of genus g.

Joint work with James R. Lee.