VibeMathedMath problems solved with AI
Sign in

The planar and bounded-treewidth cases of the GNRS L1-embedding conjecture

Gupta, Newman, Rabinovich and Sinclair conjectured that for every proper minor-closed family of graphs there is a constant CC such that the shortest-path metric of every graph in the family, with arbitrary positive edge lengths, embeds into L1L_1 with distortion at most CC; equivalently, the multicommodity flow-cut gap is uniformly bounded on the family. Constant distortion was known for series-parallel graphs (GNRS; sharp value 2 by Chakrabarti-Jaffe-Lee-Vincent) and for bounded outerplanarity, while the best bound for nn-vertex planar graphs was O(log⁡n)O(\sqrt{\log n}) (Rao 1999). Do planar graph metrics, and for each fixed kk the metrics of graphs of treewidth at most kk, embed into L1L_1 with distortion bounded independently of the graph and the edge lengths?

Result
Proved(see note)
Status
Partial result
AI contribution
AI-discovered
Method
Argument
Field
Metric embeddings into L1; multicommodity flow-cut gaps
Posed by
A. Gupta, I. Newman, Y. Rabinovich and A. Sinclair, Cuts, trees and l1-embeddings of graphs, Combinatorica 24 (2004)
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

Planar paper, Theorem 1.1: a universal constant C≥1C\ge1 such that every finite connected planar graph with positive edge lengths embeds into L1L_1 with distortion at most CC; hence the undirected multicommodity flow-cut gap is uniformly bounded on planar graphs. Treewidth companion, Theorem 1.1: for each kk, a constant CkC_k (no explicit estimate) for graphs with tree decompositions of bag size at most kk, hence also for graphs excluding a fixed planar minor. Together they give constant distortion for fixed-parameter almost-embeddable families. Not shown: the full GNRS conjecture for every minor-closed family (closure under clique sums is open), and no explicit value of CC.

What the AI did

Produced by an unreleased internal OpenAI model as part of an OpenAI evaluation on open research problems, published in the openai/math release (pinned commit adc7f12). The release README says the vast majority of results used one fixed procedure, averaging about three hours of ChatGPT Pro thinking compute per result; this result is not among the README's stated exceptions (the Riemann zeta zero-free region work and the Hodge conjecture for CM abelian varieties). The manuscript is authored as OpenAI with no human author named. Both main theorems have Lean formalizations in the release (Comparator challenges PlanarL1 and BoundedTreewidthL1).

Verification

No independent mathematician has checked this yet. Checked here: the abstracts, introductions and main theorems of both manuscripts (TeX source), read against the GNRS conjecture as cited. Lean-checked on the release's Comparator challenge PlanarL1 (declaration OAI.PlanarL1.planar_graph_metrics_embed_L1, listed in lean/formalization.yaml). Its statement was read here: it asserts one real C≥1C\ge1 such that every connected graph on Fin n with a planar drawing (injective vertex points, simple arcs with pairwise disjoint interiors) and symmetric positive edge lengths has a map into L1L^1 of some measure space with d≤∥f(x)−f(y)∥≤Cdd\le\|f(x)-f(y)\|\le C d for the walk-length distance dd. That is the planar headline. The companion challenge BoundedTreewidthL1 (OAI.BoundedTreewidthL1.main_theorem, also listed) states, for every bag-size bound k≥2k\ge2, a constant C(k)C(k) and an embedding into finite-dimensional ℓ1\ell_1 for every finite connected graph with a tree decomposition of bag size at most kk; that is the treewidth headline. Neither was rebuilt here. The papers state that the full GNRS conjecture (general clique-sum closure) is not established.

Sources

Changelog1 change

Discussion