Goddyn's thin tree conjecture

About 2 years old · traced to

Let G=(V,E)G=(V,E) be an unweighted undirected graph. A set T⊆ET\subseteq E is α\alpha-thin with respect to GG if, for every nonempty set S⊊VS\subsetneq V,

∣T(S,S‾)∣≤α∣E(S,S‾)∣.\lvert T(S,\overline{S})\rvert\leq\alpha\lvert E(S,\overline{S})\rvert.

A graph is dd-edge-connected if every cut has at least dd edges. Thin Tree Conjecture. For any α<1\alpha<1, there exists d≥1d\geq1 such that any dd-edge-connected graph GG has a spanning tree TT that is α\alpha-thin. This conjecture asks for combinatorial constructions of thin spanning trees; spectral constructions of linear-sized thin subsets are known, but the combinatorial question remains open.

References

Primary source

Shayan Oveis Gharan and Arvin Sahami, “Unweighted One-Sided Code Sparsifiers and Thin Subgraphs”, arXiv:2502.02799 (2025).

Additional references

2 papers in this index state this conjecture (2024–2025). The statement above is taken from the most recent of them; the others are arXiv:2403.05178.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.