Changes
It was shown by Oveis Gharan and Saberi <ref name="Ov"/> that the conjecture is true for graphs of bounded orientable genus. Erickson and Sidiropoulos <ref name="ErSi"/> proved the existence of thin spanning forests with few components in graphs of bounded genus, and used these to obtain an <math>O(\log(g)/\log\log(g))</math>-approximation for ATSP. Anari and Oveis Gharan <ref name="AnOv"/> proved that a ''k''-edge-connected graph with <math>k \geq 7 \log(n)</math> has a <math>(\mathrm{polylog}(k)/k)</math>-thin spanning tree.
The notion of <math>\epsilon</math>-thinness canbe defined similarly for arbitrary edge sets, not just spanning trees. The following related theorem follows from the work of Batson, Spielman and Srivastava <ref name="BaSpSr"/>on spectral sparsifiers.
'''Theorem.''' Given an arbitrary graph <math>G=(V,E)</math>, there exists an edge set <math>F \subseteq E</math> of size <math>|V|</math> that is <math>4|V|/|E|</math>-thinin ''G''.
==Related conjectures==
