skip to content

Thin spanning trees and their algorithmic applications

Presented by: 
Amin Saberi Stanford University
Tuesday 12th July 2016 - 12:00 to 12:30
INI Seminar Room 1
Motivated by Jaeger's modular orientation conjecture, Goddyn asked the following question: 

A spanning tree of a graph G is called epsilon-thin if it contains at most an epsilon fraction of the edges of each cut in that graph. Is there a function f:(0,1)→
such that every f(epsilon)-edge-connected graph has an epsilon-thin spanning tree?
I will talk about our journey in search of such thin trees, their applications concerning traveling salesman problems, and unexpected connections to graph sparsification and the Kadison-Singer problem.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons