Deterministic construction of strong thin spanning trees
What the paper claims, in its own words
Resolves the strong thin-tree conjecture constructively. Every finite loopless k-edge-connected multigraph on at least two vertices has a spanning tree containing at most a universal fraction of the edges of every cut. Such a tree can be found deterministically in polynomial time, even with binary-encoded parallel-edge multiplicities.
The plain-language explainer for this entry is still coming.
The original papers (2)
- The strong thin tree conjecture (PDF, opens in a new tab) September 23, 2026 Formal proof listed
- A polynomial-time construction of strong thin trees (PDF, opens in a new tab) September 23, 2026