∑math20

Combinatorics · Result 174

Deterministic construction of strong thin spanning trees

2 papersLean

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.

Watch

▶Introduction: the problem and why it mattersin preparation
▶The presented solutionin preparation

Papers 2

First page of The strong thin tree conjecture

The strong thin tree conjecture

OpenAI · September 23, 2026

We prove that every finite loopless k-edge-connected multigraph on at least two vertices, with k ≥ 1, has a spanning tree meeting each cut in at most \(C/k\) times the size of the cut, where C is a universal constant. This resolves the strong thin tree conjecture.

Read PDF Download Source

Cite
@misc{OAI:The-strong-thin-tree-conjecture-September-23-2026,
  author = {{OpenAI}},
  title = {{The strong thin tree conjecture}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/The-strong-thin-tree-conjecture-September-23-2026/paper.pdf}{OAI:The-strong-thin-tree-conjecture-September-23-2026}},
  year = {2026}
}
First page of A polynomial-time construction of strong thin trees

A polynomial-time construction of strong thin trees

OpenAI · September 23, 2026

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.

Read PDF Download Source

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}
}

What was formalized in Lean

The following describes the scope of the Lean formalization related to the following accompanying paper(s):

Scope

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.

Comparator links

ResultComparator statement
Strong thin-tree boundStrongThinTree.lean
Polynomial-time construction of strong thin treesAlgorithmicThinTrees.lean

Scope note on GitHub →