Browse › Combinatorics › 174 Deterministic construction of strong thin spanning trees
The strong thin tree conjecture
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 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.
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 an absolute constant C>0 such that every finite loopless k-edge-connected multigraph has a C/k-thin spanning tree (no numerical value of C), with comparator statement
StrongThinTree.lean; it also covers the deterministic polynomial-time construction (AlgorithmicThinTrees). [family-level]
Possibly relevant literature (found by the agent, not checked)
- Shayan Oveis Gharan, Arvin Sahami, Unweighted One-Sided Code Sparsifiers and Thin Subgraphs (arXiv:2502.02799, Feb 2025; rev. Sep 2025). Proves by combinatorial means that unweighted subgraphs exist that keep about half the edges and are 1/2-thin, so it relates to the paper's sparsification step, which keeps an unweighted edge subset with each cut roughly halved.
- Mahtab Alghasi, Combinatorially Thin Trees and Spectrally Thin Trees in Structured Graphs (University of Waterloo thesis, Dec 2023). Studies the thin tree conjecture for planar graphs and certificates for spectral thinness, which is the structured-graph setting the paper cites through Oveis Gharan–Saberi.
- 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, and gives O(1/λ)-type certificates for planar graphs, so it bears on checking the all-cut bound of Theorem 1.1 for concrete trees.
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 174
Independent sites; their content is not reviewed here.
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}
}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:
- A polynomial-time construction of strong thin trees · September 23, 2026