Deterministic polynomial construction of strong thin spanning trees
Status OpenLLM status Open unverified
Top Open Problems unknownunknown Not reported cataloguedOpenOpenStatement
Definitions and mathematical statement
Statement recorded in the supplied source.
Is there an absolute C and a deterministic algorithm polynomial in total binary input length that, on every k-edge-connected finite loopless multigraph (parallel-edge multiplicities allowed), returns a spanning tree T with |T intersect $\delta (S)|<=C|\delta (S)|/k$ for every vertex cut S?Short English statement
Is there an absolute C and a deterministic algorithm polynomial in total binary input length that, on every k-edge-connected finite loopless multigraph (parallel-edge multiplicities allowed), returns a spanning tree T with |T intersect $\delta (S)|<=C|\delta (S)|/k$ for every vertex cut S?Sources
- S1 Original question source or mathematical context. https://arxiv.org/abs/1411.4613v4.
- S2 Original question source or mathematical context. https://arxiv.org/abs/1411.4613v4.
- S3 Original question source or mathematical context. https://arxiv.org/abs/1411.4613v4.
- S4 Original question source or mathematical context. https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/The-strong-thin-tree-conjecture-September-23-2026/paper.pdf.
- S5 Original question source or mathematical context. https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/The-strong-thin-tree-conjecture-September-23-2026/paper.pdf.
- S6 Original question source or mathematical context. https://web.archive.org/web/20211025204852/https://www.sfu.ca/~goddyn/Problems/problems.html.
- S7 Original question source or mathematical context. https://web.archive.org/web/20211025204852/https://www.sfu.ca/~goddyn/Problems/problems.html.
- S8 OpenAI, manuscript citation page. Source of the formulation motivating this local problem. https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/A-polynomial-time-construction-of-strong-thin-trees-September-23-2026/README.md.
Statement licence: CC-BY-4.0 · Source file
Contributions 1
OpenAI claim summary for Math-2597
Algorithmic strong thin trees: The manuscript’s result handles finite multigraphs on at least one vertex, k>=1, all cuts and one absolute C. It returns a tree in deterministic time polynomial in total binary encoding, explicitly allowing binary parallel multiplicities and the empty one-vertex tree. Loops are excluded by the paper's multigraph convention.
With the hypotheses and conventions above, the claimed result addresses the whole mathematical assertion on this page.
Deterministic polynomial construction of strong thin spanning trees
OpenAI's claim
Algorithmic strong thin trees: The algorithmic manuscript claims a deterministic procedure polynomial in the binary input length that returns a $C/k$-thin spanning tree in a finite $k$-edge-connected loopless multigraph. Binary-encoded parallel multiplicities and the one-vertex case are included.Mathematical statement of the claimed result
Mathematical claim 1.
Given a finite $k$-edge-connected undirected multigraph $G$ and integer $k\ge1$, a deterministic algorithm is claimed to return a spanning tree $T$ using a number of bit operations polynomially bounded by the full input encoding length such that \[|\delta_T(S)|\le(C/k)|\delta_G(S)|\quad(\varnothing\ne S\subsetneq V(G)),\] where $C$ is absolute and $\delta_G(S)$ is the edge cut. The bound applies to explicitly listed edges and binary-encoded multiplicities; for one vertex the output is the empty tree.Outline of the argument
Algorithmic strong thin trees: An effective metric-cone hierarchy constructs a rational shortcut form and many low-resistance candidate edges. A second frame preserves the ranks needed for spanning-tree packing, and rational padding supplies signing certificates without irrational whitening. Iterated simultaneous sparsification controls every cut and packing inequality, with a separate reduction handling binary multiplicities.Formal verification
Family 174 describes Lean coverage for thin-tree existence and the companion deterministic construction with binary multiplicities.Algorithmic strong thin trees: The manuscript links AlgorithmicThinTrees.lean, StrongThinTree.lean (declaration OAI.StrongThinTree.strongThinTree).
The documented selection includes this manuscript’s main assertion; that assertion retains the restrictions stated above.
This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.
Status caveat
OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.Sources
- OpenAI, A polynomial-time construction of strong thin trees, 2026-09-23; citation key
OAI:A-polynomial-time-construction-of-strong-thin-trees-September-23-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:tt-algorithm. - Family 174: Lean scope.
- Comparator AlgorithmicThinTrees.json.
- Comparator AlgorithmicThinTrees.lean.
- Comparator StrongThinTree.json.
- Comparator StrongThinTree.lean.
- OpenAI catalogue entry.