Browse › Convex and metric geometry › 089 Bounded-distortion L1 embeddings of planar and bounded-treewidth graphs
L1 Embeddings of Graphs of Bounded Treewidth
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
For every fixed treewidth bound, the shortest-path metrics of finite connected graphs with arbitrary positive real edge lengths embed into real L1 with uniformly bounded distortion. This resolves the bounded-treewidth case of the Gupta–Newman–Rabinovich–Sinclair conjecture positively.
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.
Comments and discussion
- Hung Le, OpenAI Math Dump Hits My Home (Rambling on Graphs, 2026-10-07; updated through 2026-10-20). Discusses both embedding claims and records an ongoing detailed reading of the planar proof, highlighting the column model and charts; the author reports increasing confidence while still working to internalize the argument. [family-level]
Formalization
- OpenAI math release, Bounded-distortion L₁ embeddings of planar and bounded-treewidth graphs: Lean scope (lean/docs/089.md, 2026). Describes the scope of the release's own Lean formalization of the bounded-treewidth result (a constant $C(k)$ for each bag-size bound $k\ge2$, with target finite-dimensional real $L_1$) and links the Comparator statement
BoundedTreewidthL1.lean. [family-level]
Possibly relevant literature (found by the agent, not checked)
- Yuri Rabinovich, On average distortion of embedding metrics into the line and into L1 (STOC 2003, doi:10.1145/780606.780609). Shows that bounded-treewidth shortest-path metrics embed into $\ell_1$, and even into the line, with constant average distortion, a weaker form of the paper's Theorem 1.1 that the paper's bibliography does not cite.
- Hsien-Chih Chang, Jonathan Conroy, William Eliot, Hung Le, Vinayak, Peeling Half the Onion: Embedding k-Outerplanar Graphs into ℓ1 and Trees with a Polynomial Distortion (in k) (arXiv:2610.10888, 7 October 2026). Gives a bound polynomial in $k$ for $k$-outerplanar graphs, a bounded-treewidth subclass, improving the Chekuri et al. bound that the paper cites among earlier structural cases; it does not mention the release.
Digests and expositions
- Latent Seminar, Constant-distortion L1 embeddings of planar and bounded-treewidth graphs (2026-10-06). Explains cut metrics, the planar column and scale constructions, and the treewidth particle and reservation mechanisms, explicitly limiting its review to statements and selected proof mechanisms rather than independent verification of the complete proofs. [family-level]
- Orply / Perplexity, Bounded Treewidth Guarantees Finite-Distortion L1 Embeddings (2026-10-09). Summarizes the bag-size-dependent distortion claim and the use of consistent cut laws, particle reservations, uncertainty transport, and anchors to preserve separation. [AI-generated per source]
Elsewhere
- Emergent Mind: family 089
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:L1-Embeddings-of-Graphs-of-Bounded-Treewidth-September-23-2026,
author = {{OpenAI}},
title = {{$L_1$ Embeddings of Graphs of Bounded Treewidth}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/L1-Embeddings-of-Graphs-of-Bounded-Treewidth-September-23-2026/paper.pdf}{OAI:L1-Embeddings-of-Graphs-of-Bounded-Treewidth-September-23-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/089.md. The Lean statements have not been checked by people against the paper's claims.
Family 089: Bounded-distortion L1 embeddings of planar and bounded-treewidth graphs
Resolves the planar and bounded-treewidth cases of the Gupta–Newman–Rabinovich–Sinclair conjecture. Shortest-path metrics of finite connected graphs with arbitrary positive edge lengths embed into real L1 with universal distortion for planar graphs, and distortion depending only on treewidth for bounded-treewidth graphs. The corresponding multicommodity flow–cut gaps are uniformly bounded.
Other papers in this family:
- Planar Graph Metrics Embed into L1 with Constant Distortion · September 23, 2026