University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Thin spanning trees and their algorithmic applications

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Thin spanning trees and their algorithmic applications

Download to your calendar using vCal

If you have a question about this talk, please contact INI IT .

SNAW01 - Graph limits and statistics

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.

Bio: saberi/bio.txt" target="_blank" rel="nofollow">http://stanford.edu/saberi/bio.txt

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

CUAES Queen's Building, Emmanuel College followed by dinner in Pembroke College St John's Divinity School, Main Lecture Theatre

Other talks

Polar Oceans Seminar Talk LMB Seminar - Mechanisms of mRNA packaging and export Rothschild Public Lecture: The Quantum Centenary: from Order to Chaos Coming soon From lab to clinic: an introduction to translational research Rothschild Public Lecture: Forty years of causal inference: Report of a great-grandfather
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity