VibeMathedMath problems solved with AI
Sign in

The strong thin tree conjecture

A spanning tree TT of a multigraph GG is α\alpha-thin if ∣δT(S)∣≤α∣δG(S)∣|\delta_T(S)|\le\alpha|\delta_G(S)| for every nonempty proper vertex set SS. Goddyn's thin tree conjecture asks whether for every ε>0\varepsilon>0 sufficiently high edge connectivity guarantees an ε\varepsilon-thin spanning tree; the strong form asks for the rate: is there a universal constant CC such that every kk-edge-connected multigraph has a C/kC/k-thin spanning tree? Known results gave O(1/k)O(1/k) for planar and bounded-genus graphs (Oveis Gharan-Saberi) and poly(log⁡log⁡n)/k\mathrm{poly}(\log\log n)/k in general (Anari-Oveis Gharan). Via Asadpour et al., thin trees bound the integrality gap of asymmetric TSP. Does every kk-edge-connected finite multigraph have a spanning tree that is C/kC/k-thin, with CC absolute?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Argument
Field
Graph theory; spanning trees, cuts and connectivity
Posed by
Luis Goddyn (thin tree conjecture); the C/k strong form is from the thin-tree literature around asymmetric TSP
Year posed
2004
Years open
22y
Solved
2026-09-23
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
45 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: there is an absolute C>0C>0 such that every finite loopless kk-edge-connected multigraph with at least two vertices has a spanning tree TT with ∣δT(S)∣≤(C/k)∣δG(S)∣|\delta_T(S)|\le(C/k)|\delta_G(S)| for all cuts. The proof extracts tree packings on low-resistance edges and iterates a Marcus-Spielman-Srivastava sparsification. The companion gives a deterministic polynomial-time construction, polynomial in the binary input length. Neither paper gives an explicit constant or a new ATSP approximation ratio (constant-factor ATSP was already known by other methods), and spectrally thin trees are not claimed.

What the AI did

The release README says every result in it was produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored 'OpenAI' and names no human author. The principal manuscript and its algorithmic companion are both dated September 23, 2026; the companion extends the hierarchy argument to a deterministic polynomial-time construction.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 of the principal manuscript was read against the conjecture; it gives the strong C/kC/k form for every k≥1k\ge1 and every finite loopless multigraph on at least two vertices, which also implies Goddyn's original form. No value of CC is given. lean/formalization.yaml lists a main result for this manuscript (comparator StrongThinTree, declaration OAI.StrongThinTree.strongThinTree, file OAI/Combinatorics/ThinTrees/Main.lean). ComparatorChallenges/StrongThinTree.lean was read here: it states exactly the headline over finite multigraphs given by endpoint maps with parallel edges distinct. The companion's challenge AlgorithmicThinTrees.json is not in the formalization catalogue; its solution module OAI/Combinatorics/ThinTrees/AlgorithmicMain.lean exists at the pinned commit, and its statement (a stack machine that halts in polynomially many steps in the input length, including binary-encoded multiplicities, and outputs a C/kC/k-thin tree) was read here. Neither was rebuilt here. Permitted axioms: propext, Quot.sound, Classical.choice.

Sources

Changelog1 change

Discussion