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. (OpenAI’s Lean note)
Lean is a language for mathematical statements and proofs that a computer can verify. The assessments below ask whether those statements express the result OpenAI describes here.
Both independent assessments find that the Lean statements express or imply the whole result described above. Read the assessments
In The strong thin tree conjecture, 23 September 2026
The paper’s main theorem is shown as a possible match to OpenAI’s description. No review confirming the selection is recorded.
There is a universal constant C>0 such that, for every integer k\ge1, every finite k-edge-connected undirected multigraph without loops and with at least two vertices has a spanning tree T satisfying
In A polynomial-time construction of strong thin trees, 23 September 2026
Possible match to OpenAI’s description, selected because it shares the most wording. No review confirming the selection is recorded.
There is an absolute constant C with the following property. Given a finite k-edge-connected multigraph G on at least one vertex and an integer k\ge1, a deterministic algorithm returns a spanning tree T satisfying
in time polynomial in the total binary input length, whether edges are listed explicitly or multiplicities are encoded in binary. For a one-vertex graph the answer is the empty tree.
No Lean statement in the release is paired with this theorem.
The release does not say which paper theorem its catalogue describes. Both statements above are shown whole: the paper’s main theorem first, then the statement that shares the most wording with the description. The atlas has not reviewed either choice.
Each paper opens as a reading page in the browser, with the PDF beside it. The statements each paper opens with are on its reading page.
Choose one to see it beside the paper theorem it is paired with.
For a configured theorem, the Comparator program tests whether OpenAI’s separate proof proves the exact Lean statement using only the allowed axioms. Some statement files instead configure definitions for comparison by name and type. Acceptance does not establish that a formal statement means the same thing as the paper’s theorem.
StrongThinTreeThe paper states
In The strong thin tree conjecture, 23 September 2026
There is a universal constant C>0 such that, for every integer k\ge1, every finite k-edge-connected undirected multigraph without loops and with at least two vertices has a spanning tree T satisfying
The words they share: tree, connected, spanning, edge, integer, strong, thin, multigraph, constant, two, least, vertices, finite.
Possible Lean counterpart
Selected from shared wording. No review of whether the statements mean the same thing is recorded.
StrongThinTree.lean, the release lists it as a main result.
def MainStatement : Prop := ∃ C : ℝ, 0 < C ∧ ∀ (k : ℕ), 1 ≤ k → ∀ (n m : ℕ), 2 ≤ n → ∀ G : MultiGraph n m, G.EdgeConnected k → ∃ T : Finset (Fin m), G.SpanningTree T ∧ ∀ S : Finset (Fin n), S.Nonempty → S ≠ Finset.univ → ((G.cut T S).card : ℝ) ≤ (C / (k : ℝ)) * (G.cut Finset.univ S).card theorem strongThinTree : MainStatement := by sorryThis file states the theorem with sorry, a placeholder, in place of its proof. OpenAI supplies a separate proof file. Comparator tests whether that proof proves the statement here.
two independent groups report that Comparator accepted runs for this Lean statement file: cert-machine; MathVet. Who ran the proof-verification program
AlgorithmicThinTreesThe paper states
No paper theorem is paired with this Lean statement.
no paper statement matches the Lean text clearly enough to pair, so the closest candidates are listed below.
Statements it shares words with:
The Lean statement
No paper theorem is paired with it.
AlgorithmicThinTrees.lean, the release lists it as a supporting statement.
def AlgorithmicStrongThinTrees : Prop := ∃ C : ℝ, 0 < C ∧ ∃ M : CurrentKS.Machine, ∃ a degree : ℕ, 0 < a ∧ ∀ x : Input, Valid x → let result := M.run x.encode (a * (x.length + 1) ^ degree) result.state = none ∧ GoodOutput C x (result.stacks M.outputStack) theorem algorithmic_strong_thin_trees : AlgorithmicStrongThinTrees := by sorryThis file states the theorem with sorry, a placeholder, in place of its proof. OpenAI supplies a separate proof file. Comparator tests whether that proof proves the statement here.
two independent groups report that Comparator accepted runs for this Lean statement file: cert-machine; MathVet. Who ran the proof-verification program
Atlas found these propositions by scanning the text of the project’s Model.lean file. Each name links to its definition, with any associated statement file beside it. This list does not record running Lean to interpret or verify those definitions.
Connected Model.lean, line 19SpanningTree Model.lean, line 22EdgeConnected Model.lean, line 25MainStatement Model.lean, line 31MathVet and cert-machine agree on how much of the advertised result the Lean statements express.
MathVet and Carlos Toledo’s cert-machine independently assessed whether this family’s Lean statements express the whole result OpenAI describes in its catalogue. These are assessments of the family as a whole, not of each paper theorem separately.
MathVet finds that the Lean statements express or imply the whole advertised result (their term: “full”).
Their note: StrongThinTree.MainStatement (∃ C > 0, ∀ k ≥ 1, ∀ n m, 2 ≤ n → ∀ G : MultiGraph n m, G.EdgeConnected k → ∃ T, G.SpanningTree T ∧ ∀ S, |cut T S| ≤ (C/k) * |cut univ S|) is the existence theorem; AlgorithmicStrongThinTrees adds ∃ M : CurrentKS.Machine, ∃ a degree,... result.state = none ∧ GoodOutput C x... for explicit and binary-multiplicity inputs. Both parts of the summary are stated; binary multiplicities are really binary (encodeNat n = frame (Computability.encodeNat n) and Mathlib’s encodeNat is binary).
Definitions the group asks readers to compare with the paper: CurrentKS.Machine (hand-rolled multi-stack machine with a lookup table, Machine.run with a fuel argument) and the notion of polynomial time M.run x.encode (a * (x.length + 1) ^ degree) halting with state = none: a custom model, not Mathlib’s TM2ComputableInPolyTime; multi-stack machines are polynomially equivalent to Turing machines so this looks faithful, but ‘polynomial time’ is a bespoke definition.
“full”, in their words: The challenge statements imply the headline claim after unpacking definitions or one routine step.
Their method: An independent, model-assisted, pre-referee reading of each family’s challenge statements against its headline claim under a published rubric (PROTOCOL.md), with its own Comparator runs per challenge.
cert-machine finds that the Lean statements express or imply the whole advertised result (their term: “MATCHES”).
“MATCHES”, in their words: The challenge statements state the headline as OpenAI wrote it.
Their method: Every Comparator challenge re-run on Linux with nanoda switched on, decided by a preregistered rule.
OpenAI’s own note on what its Lean covers
The strong thin-tree conjecture asks for spanning trees that cross every cut sparsely relative to the original graph. The formalized result gives one absolute constant $C>0$ such that every finite loopless $k$-edge-connected multigraph with at least two vertices has a spanning tree crossing each nontrivial cut at most $(C/k)$ times the original cut size. Parallel edges remain distinct. No numerical value of $C$ or construction algorithm is asserted.
The strong thin-tree problem asks for a spanning tree that crosses every cut sparsely relative to the original graph. The formalization gives one deterministic polynomial-time algorithm and an absolute constant $C>0$ such that a finite $k$-edge-connected loopless multigraph yields a spanning tree using at most a $C/k$ fraction of the edges of every cut. The input may encode parallel-edge multiplicities in binary, and the running time is polynomial in that binary input length.
Strong thin-tree bound StrongThinTree
Unreviewed AI draft: states a paper’s theorem as the paper does. States the main theorem: one constant C such that every k-edge-connected loopless multigraph has a spanning tree using at most a C/k fraction of every cut.
Polynomial-time construction of strong thin trees AlgorithmicThinTrees
Unreviewed AI draft: states a paper’s theorem as the paper does. States the main theorem of the algorithmic paper (stated in an input file the dataset’s statement list misses): a deterministic polynomial-time construction of C/k-thin spanning trees, with multiplicities in binary.
These groups report running Comparator with the release’s Lean statement files. For a configured theorem, it verifies OpenAI’s separate proof against the exact statement; some files instead configure definitions for comparison by name and type. Each row is the named group’s report. Atlas has not repeated the runs.
These reports do not list the software versions, proof-verification programs, axioms, time or memory in separate fields. Any such details in a report’s prose are reproduced below.
StrongThinTreeTwo reports, all at the release’s recorded version.
| Reported by | Their word | Their account | Date | Original report |
|---|---|---|---|---|
| cert-machine | “CERTIFIED” | Re-run through Comparator with the independent nanoda kernel switched on: Lean’s kernel and nanoda both accept OpenAI’s solution. | 10 October 2026 | Original report |
| MathVet | “comparator-sandboxed-pass” | Re-run through Comparator in a sandboxed virtual machine: accepted. | 8 October 2026 | Original report |
AlgorithmicThinTreesTwo reports, all at the release’s recorded version.
| Reported by | Their word | Their account | Date | Original report |
|---|---|---|---|---|
| cert-machine | “CERTIFIED” | Re-run through Comparator with the independent nanoda kernel switched on: Lean’s kernel and nanoda both accept OpenAI’s solution. | 10 October 2026 | Original report |
| MathVet | “comparator-sandboxed-pass” | Re-run through Comparator in a sandboxed virtual machine: accepted. | 8 October 2026 | Original report |
These links come from the papers’ bibliographies. A citation records that one paper cites another; how each cited result is used has not been examined here.
This family’s papers cite no paper elsewhere in the release.
No paper elsewhere in the release cites this family’s papers.
Each paper’s outside references are listed with it on its reading page, where each citation is placed. Every outside work cited in the release: References outside the release
Atlas has no contributed explanation for this family yet. You can offer one with a GitHub account. You receive named credit and disclose any AI assistance.
Each button opens a GitHub form with this page and its source version filled in. Opening the form does not reserve the work.
Offer to write an explanationCompare one Lean statement with its paper: StrongThinTree, AlgorithmicThinTreesSuggest a source attributionSuggest a change
Commentary on this family by others, dated and credited. It is commentary, not a finding.
An unsigned public tier list, the OpenAI Math Tier List, classes it as a algorithm and rates its significance, if it holds up, as “Major math journal”. The page says that nothing on it is verified.
Author not stated. Source
Each item identifies a statement, definition or report that needs further review. Its link opens a GitHub form with the source version already recorded.
Why this passage is shown
Theorem 1.1
In The strong thin tree conjecture, 23 September 2026
Why this passage is shown
Theorem (number unavailable) (Algorithmic strong thin trees)
In A polynomial-time construction of strong thin trees, 23 September 2026
Why this passage is shown
Theorem 2.1 (Hierarchy bound for the metric test cone)
In A polynomial-time construction of strong thin trees, 23 September 2026
Why this passage is shown
Corollary 7.1 (Thin and cheap rounding of fractional cuts)
In A polynomial-time construction of strong thin trees, 23 September 2026
Why this passage is shown
Proposition 3.1 (Constructive shortcut extraction)
In A polynomial-time construction of strong thin trees, 23 September 2026
Why this passage is shown
Theorem A.1 (Rational rank-one signing)
In A polynomial-time construction of strong thin trees, 23 September 2026
Why this passage is shown
Theorem 1.1
In The strong thin tree conjecture, 23 September 2026
Why this passage is shown
Theorem 4.1 (Shortcut extraction)
In The strong thin tree conjecture, 23 September 2026
Why this passage is shown
Proposition 6.2 (Packing-preserving sparsification)
In The strong thin tree conjecture, 23 September 2026
Why this passage is shown
Proposition 2.5 (Simultaneous response)
In A polynomial-time construction of strong thin trees, 23 September 2026
Why this passage is shown
Theorem 2.1 (Hierarchy bound for the metric test cone)
In A polynomial-time construction of strong thin trees, 23 September 2026
Independent assessment
MathVet
14c7f91Independent assessment
Carlos Toledo’s cert-machine
9814e4cProof-verification report
cert-machine, StrongThinTree
Proof-verification report
MathVet, StrongThinTree
Proof-verification report
cert-machine, AlgorithmicThinTrees
Proof-verification report
MathVet, AlgorithmicThinTrees
Lean statement
AlgorithmicThinTrees
Lean statement
StrongThinTree