Abstract
I will discuss an extension and an application of the method of interlacing families, pioneered by Marcus, Spielman, and Srivastava, to a combinatorial conjecture of Goddyn on the existence of thin trees: Every k-edge-connected graph has a spanning tree which has at most O(1/k)-fraction of the edges in every cut.
Random spanning trees satisfy this conjecture within a factor of log(n)/log log(n). I will discuss how we can go beyond randomized rounding and prove the existences of trees that satisfy the conjecture within a factor of polyloglog(n). This requires extending the method of interlacing families to a setting where input matrices are chosen according to negatively dependent distributions, as opposed to an independent/product distribution.
I will also briefly discuss relations between the thin tree conjecture and the asymmetric traveling salesman problem.
Based on joint work with Shayan Oveis Gharan.