View source for The GNRS conjecture for planar and bounded-treewidth graphs

'''The Gupta–Newman–Rabinovich–Sinclair (GNRS) conjecture''' predicts that, for every proper minor-closed family of finite graphs, the shortest-path metrics of graphs in the family, with arbitrary positive edge lengths, embed into ''L''<sub>1</sub> with uniformly bounded distortion. Equivalently, the undirected multicommodity flow–cut gap is uniformly bounded on such a family. Two manuscripts dated 23 September 2026 in OpenAI's public mathematics collection ([https://github.com/openai/math github.com/openai/math]) claim the planar case and the bounded-treewidth case. This page summarizes the published claims and lists publicly available follow-up work. Statements are the respective authors' claims; this page does not certify them.

== Background ==
* As recounted in the introductions of the manuscripts:
** The worst flow–cut gap on a fixed graph equals the worst ''L''<sub>1</sub> distortion of its weighted shortest-path metrics (Gupta, Newman, Rabinovich and Sinclair, Section 3, Theorem 3.2).
** For ''n''-vertex planar metrics the general preceding bound was ''O''(√log ''n''), due to Rao, through Euclidean space. Newman and Rabinovich showed that even series-parallel metrics can require Ω(√log ''n'') distortion into Euclidean space.
** Constant ''L''<sub>1</sub> distortion was known for series-parallel graphs (Gupta, Newman, Rabinovich and Sinclair), with the sharp value 2 (upper bound of Chakrabarti, Jaffe, Lee and Vincent; matching lower bound of Lee and Raghavendra), and for planar graphs of bounded outerplanarity (Chekuri, Gupta, Newman, Rabinovich and Sinclair). Further results restrict the pairs to be preserved (terminals on few faces) or the geometry (Sidiropoulos's nonpositively curved planar metrics).
** For bounded treewidth, Lee and Sidiropoulos settled bounded pathwidth through stochastic embeddings into trees, and Abraham, Filtser, Gupta and Neiman obtained ''O''(√''p'') distortion for pathwidth ''p''. The manuscript notes that dominating trees cannot give a uniform bound for all bounded-treewidth graphs, and names the local-consistency theorem of Chlamtáč, Krauthgamer and Raghavendra as its closest precursor.

== The original results ==
* '''Planar graphs.''' Theorem 1.1 of ''Planar Graph Metrics Embed into L<sub>1</sub> with Constant Distortion'' states that there is a universal constant ''C'' such that the shortest-path metric of every finite connected planar graph with positive real edge lengths embeds into a real ''L''<sub>1</sub> space with distortion at most ''C''. The constant does not depend on the number of vertices or on the edge lengths. The manuscript also states the corresponding universal bound on the undirected fractional flow–cut gap for planar graphs.
* '''Bounded treewidth.''' Theorem 1.1 of ''L<sub>1</sub> Embeddings of Graphs of Bounded Treewidth'' states that for every bag-size bound ''k'' ≥ 2 there is a constant ''C''<sub>''k''</sub> such that every finite connected graph with a tree decomposition whose bags have at most ''k'' vertices embeds with distortion at most ''C''<sub>''k''</sub>, for every positive edge-length function. The manuscript gives no explicit estimate for ''C''<sub>''k''</sub>. By the excluded-planar-minor theorem of Robertson and Seymour, it states, the result also gives a uniform bound for graphs excluding any fixed planar graph as a minor.
* '''Almost-embeddable families.''' The planar manuscript combines both theorems with a stochastic reduction of Lee and Sidiropoulos to obtain uniform distortion, and flow–cut, bounds for each fixed-parameter almost-embeddable family in their sense. It states that this "does not establish closure under general clique sums of order greater than one, and therefore does not prove the full GNRS conjecture".
* ''Method, as described:'' the planar proof represents the graph by a non-crossing column model and builds random families of cuts through charts attached to points. Component separation limits which pairs need further updates, which yields a packing bound for the surviving pairs, and an interpolation step makes local formulas agree exactly at their interfaces, so that the updates combine without a loss proportional to the number of scales. The treewidth proof constructs cut laws on the bags of a tree decomposition, glues consistent laws by the Markov sampling principle of Chlamtáč, Krauthgamer and Raghavendra, and adds anchor cuts built from the padded decompositions of Filtser and coauthors.
* '''Sources.''' At commit <code>1581d4c</code>: [https://github.com/openai/math/tree/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/Planar-Graph-Metrics-Embed-into-L1-with-Constant-Distortion-September-23-2026 Planar Graph Metrics Embed into L1 with Constant Distortion] and [https://github.com/openai/math/tree/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/L1-Embeddings-of-Graphs-of-Bounded-Treewidth-September-23-2026 L1 Embeddings of Graphs of Bounded Treewidth].
* '''Formalization, as described by the repository.''' The [https://github.com/openai/math/blob/1581d4cbdd69a0faf34b2089614fe2a814316a6a/lean/docs/089.md scope note] states that the formalization gives one constant for every finite connected planar graph with arbitrary positive real edge lengths, and a constant ''C''(''k'') for each bag-size bound ''k'' ≥ 2, independent of the graph and decomposition size. The Comparator statements are [https://github.com/openai/math/blob/1581d4cbdd69a0faf34b2089614fe2a814316a6a/lean/ComparatorChallenges/PlanarL1.lean PlanarL1.lean] and [https://github.com/openai/math/blob/1581d4cbdd69a0faf34b2089614fe2a814316a6a/lean/ComparatorChallenges/BoundedTreewidthL1.lean BoundedTreewidthL1.lean].

== Public follow-up work ==
{| class="wikitable"
! Date !! Work !! Relation !! Public claim !! Public status (checked 25 October 2026)
|-
| 2026-10-07 to 2026-10-20 || H. Le, ''[https://minorfree.github.io/OpenAIDump/ OpenAI Math Dump Hits My Home]'', blog ''Rambling on Graphs'' || Reading (dated reading log of the planar manuscript) || A researcher on both problems records reading Sections 2–9 of the planar manuscript. On 19 October he writes that he is "more confident that the proof is correct (hard to put a percentage, but 90% would be a reasonable number)", identifies the column model and the per-point charts as its two main ideas, and reports that the constant remains very large (about 10<sup>73</sup> after an optimization with ChatGPT Astra). He names the minor-free case as a natural next step, via the Robertson–Seymour decomposition. || Blog post with dated updates; personal reading notes, not a published verification.
|-
| 2026-10-08 || [https://github.com/mathvet/mathvet MathVet] (GitHub; review of openai/math, tables at repository commit <code>22ef46c</code>, 24 October 2026) || Review (fidelity of the formal statements) || Rates this family "full" and records sandboxed Comparator passes for <code>PlanarL1</code> and <code>BoundedTreewidthL1</code>. Its note says that both embedding theorems are stated but the flow–cut-gap corollary is not, and that planarity is defined by a custom drawing predicate. || MathVet states that it does not claim any theorem false and reports what was machine-checked as stated.
|-
| 2026-10-10 || [https://github.com/carlostoledo1891/cert-machine/blob/d93dd5b48e798372da73a42ac2275a3eeacd9a5e/corpus/openai-math/kernel-runs/38019899278/PlanarL1.json cert-machine], openai/math lane K || Verification (two kernels) || Records that Lean's default kernel and the nanoda kernel accept the <code>PlanarL1</code> solution (394 s, run 38019899278) and the [https://github.com/carlostoledo1891/cert-machine/blob/a8f92f8e74893ff9afd167fd55310ad5afbc4958/corpus/openai-math/kernel-runs/38017370880/BoundedTreewidthL1.json <code>BoundedTreewidthL1</code>] solution (349 s, run 38017370880). || Repository.
|-
| 2026-10-10 to 2026-10-14 || [https://github.com/leanprover/con-leche/blob/90577d9e49ee3aed45da3d421bdf5dc780192304/DESIGN.md con-leche development journal] (task #348) || Verification (second kernel) || In its run over all Comparator challenges of the collection at commit <code>fd4aeeb</code>, the journal's table of exceptions lists neither challenge of this family, so both were accepted by con-leche and by Lean's official kernel. || Development journal.
|-
| 2026-10-13 || K. Adler, [https://github.com/keithadler/planar-l1-companion/tree/e3efb2b0c566aae92df6eb4a586c2d42e8a043ef keithadler/planar-l1-companion] and [https://github.com/keithadler/planar-l1-lean/tree/a501b543d0f8ca7fbc4cb486b2d2a53534318be2 keithadler/planar-l1-lean] || Reading (section notes) and partial formalization || Section-by-section notes on the planar manuscript, written by an AI for the author and tagged by status, giving "no verdict on the main theorem". The companion Lean repository formalizes selected lemmas of Sections 3, 5 and 6 (356 declarations, standard axioms only), with the inputs from other sections taken as explicit hypotheses. || Both repositories describe themselves as unreviewed by experts; the Lean repository is conditional and states that its authors did not compile OpenAI's formalization.
|}

== Notes ==
* The earlier results are due to the authors named in the Background section, as recounted by the manuscripts.
* Independently, Chang, Conroy, Eliot, Le and Vinayak ([https://arxiv.org/abs/2610.10888 arXiv:2610.10888], 7 October 2026) embed ''k''-outerplanar graphs into ''L''<sub>1</sub> and into distributions over trees with distortion polynomial in ''k'', improving the earlier exponential bound. Their introduction describes the planar conjecture as open and does not cite the OpenAI manuscripts. It also records Lee and Poore's resolution of the 2-sum case of the clique-sum conjecture and that nothing is known for sums of order at least three.
* The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.

[[Category:OpenAI results]]