Search Mailing List Archives
[theory-seminar] Amin speaking in combinatorics seminar
Gregory Valiant
gvaliant at cs.stanford.edu
Wed Oct 7 12:56:20 PDT 2015
Hi Everyone,
Amin will be talking at tomorrow's combinatorics seminar about some
cool graph theory/combinatorics that is very relevant to problems in
tcs. title/abstract/time/place below.
-g
Amin Saberi (Stanford), Thin spanning trees and their algorithmic applications
When: Thu, October 8, 3pm – 4pm
Where: 384-H (math building, fourth floor)
Abstract: 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.
More information about the theory-seminar
mailing list