Thin trees are intriguing objects in graph theory that relate to foundational topics, such as nowhere-zero flows and the asymmetric traveling salesman problem (ATSP). A spanning subtree T of a graph G is called alpha-thin if every cut in T contains at most an alpha-fraction of G's edges in that cut.

Asadpour et al gave an algorithm constructing an O(log n / k log log n)-thin tree in any graph with n vertices and edge-connectivity k. Improving this to O(1/k) would imply a constant-factor approximation algorithm for ATSP.

We define a stronger notion of thinness that is naturally motivated by spectral sparsification of graphs. A spanning subtree T of G is called alpha-spectrally-thin if T's Laplacian matrix is upper-bounded by alpha times G's Laplacian matrix in the Lowner ordering.

We give a deterministic, polynomial time algorithm to construct an O(log n / c log log n)-spectrally thin tree in any graph with n vertices and for which the effective conductance across each edge is at least c.

Remarkably, this can be improved to O(1/c) if one does not require an efficient algorithm. The recent breakthrough results of Marcus, Spielman and Srivastava imply the existence of a O(1/c)-spectrally-thin tree.

This is joint work with Neil Olver (MIT / Vrije Universiteit).