Browse › Combinatorics › 174 Deterministic construction of strong thin spanning trees
A polynomial-time construction of strong thin trees
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We give a deterministic polynomial-time construction of strong thin trees. Given a finite k-edge-connected loopless multigraph on at least one vertex, the algorithm constructs a spanning tree meeting every cut in at most a $C/k$ fraction of its edges, for a universal constant C. The running time is polynomial in the binary input length, including when parallel-edge multiplicities are encoded in binary.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI math release, Deterministic construction of strong thin spanning trees — Lean scope (release Lean docs, 174.md). Scope note for the release's Lean formalization of a deterministic polynomial-time algorithm that outputs a C/k-thin spanning tree, including binary-encoded parallel-edge multiplicities, with comparator statement
AlgorithmicThinTrees.lean; it also covers the existence bound (StrongThinTree). [family-level]
Possibly relevant literature (found by the agent, not checked)
- Zhao Song, Song Yue, Polynomial Time Algorithms for the Kadison-Singer Problem (IACR ePrint 2026/2070, Sep 2026). A deterministic rank-one signing algorithm with constant 3.3443, offered as an alternative to the Ezeunala–Jiang method the paper uses to replace the existential Marcus–Spielman–Srivastava step.
- Ali Jadbabaie, Amin Saberi, Suvrit Sra, Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time (arXiv:2609.23855, Sep 2026). A concurrent polynomial-time algorithm for Kadison–Singer partitions, relevant to the paper's constructive matrix-signing step (signing section and appendix).
- Alice Moayyedi, Thin Tree Verification is coNP-Complete (arXiv:2512.25043, Dec 2025). Shows that deciding whether a given tree is thin is coNP-complete, which is context for the paper's use of rational matrix certificates in place of checking cuts directly.
- Mohit Daga, Thin Trees via k-Respecting Cut Identities (arXiv:2510.12050, 14 October 2025). Computes exact thinness certificates for a given spanning tree, including for cuts crossing the tree in a bounded number of edges, a possible tool for checking the algorithm's output trees on concrete instances.
Elsewhere
- Emergent Mind: family 174
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:A-polynomial-time-construction-of-strong-thin-trees-September-23-2026,
author = {{OpenAI}},
title = {{A polynomial-time construction of strong thin trees}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/A-polynomial-time-construction-of-strong-thin-trees-September-23-2026/paper.pdf}{OAI:A-polynomial-time-construction-of-strong-thin-trees-September-23-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/174.md. The Lean statements have not been checked by people against the paper's claims.
Family 174: Deterministic construction of strong thin spanning trees
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 $C/k$ fraction of the edges of every cut. Such a tree can be found deterministically in polynomial time, even with binary-encoded parallel-edge multiplicities.
Other papers in this family:
- The strong thin tree conjecture · September 23, 2026