GNRS Conjecture

GNRS Conjecture

OpenAI's claim

OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 089; 2026-09-23), the asserted result is that each fixed treewidth class has a uniform $L_1$ distortion bound for arbitrary positive weighted shortest-path metrics; In manuscript 2 (family 089; 2026-09-23), the asserted result is that arbitrary positive edge lengths on finite planar graphs admit a common constant-distortion embedding into real $L_1$.

Mathematical statement of the claimed result

Manuscript 1.

For every integer $k\ge2$, the claim gives a constant $C_k<\infty$ such that any finite connected graph whose tree decomposition has every bag cardinality bounded by $k$, with arbitrary strictly positive edge lengths, has a real $L^1$ embedding $F$ satisfying \[ d_{G,\ell}(u,v)\le\|F(u)-F(v)\|_1\le C_kd_{G,\ell}(u,v) \qquad(u,v\in V(G)). \] The constant depends only on bag size, not on vertex count, decomposition depth or edge-length ratios. Bag size $k$ corresponds to treewidth at most $k-1$.

Manuscript 2.

Assign arbitrary positive real lengths to the edges of any finite planar graph that is connected. The claim supplies a real $L^1$ embedding and one constant $C<\infty$, common to all these graphs, satisfying \[ d_G(x,y)\le\|f(x)-f(y)\|_1\le C d_G(x,y)\quad(x,y\in V(G)). \] No dependence on vertex count, particular planar embedding or edge-length ratios occurs in $C$.

Outline of the argument

For manuscript 1 (family 089; 2026-09-23), consistent cut laws are built directly on decomposition bags and glued by a Markov construction. A common-submeasure transport estimate preserves separation along long bag paths; threshold sweeps and protected anchors keep a useful distance scale alive.

For manuscript 2 (family 089; 2026-09-23), measurable labels define cut distances whose upper comparison holds deterministically. Random chart changes, portals, and component ancestry supply a lower separation probability, and packing control permits the cut families to be assembled at all scales.

Formal verification

For manuscript 1 (family 089; 2026-09-23), OpenAI lists Lean statements for this assertion: each fixed treewidth class has a uniform $L_1$ distortion bound for arbitrary positive weighted shortest-path metrics.

This coverage does not establish a formal proof of the complete problem as stated here.

For manuscript 2 (family 089; 2026-09-23), OpenAI lists Lean statements for this assertion: arbitrary positive edge lengths on finite planar graphs admit a common constant-distortion embedding into real $L_1$.

This coverage does not establish a formal proof of the complete problem as stated here.

The linked family Comparator checks are BoundedTreewidthL1.lean, PlanarL1.lean.

Their named declarations include OAI.BoundedTreewidthL1.main_theorem, OAI.PlanarL1.planar_graph_metrics_embed_L1.

This site has not executed the Lean code. Described statement coverage is not an independent proof check.

Status caveat

The manuscripts were produced by an internal OpenAI model. OpenAI cautions that results without formalization can contain mistakes. This site has not independently checked the proofs; the label records the scope of OpenAI's claim.

Sources

• OpenAI, L${}_{1}$ Embeddings of Graphs of Bounded Treewidth, 2026-09-23; citation key OAI:L1-Embeddings-of-Graphs-of-Bounded-Treewidth-September-23-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:main, eq:main-embedding.
• OpenAI, Planar Graph Metrics Embed into L${}_{1}$ with Constant Distortion, 2026-09-23; citation key OAI:Planar-Graph-Metrics-Embed-into-L1-with-Constant-Distortion-September-23-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:main.
• Family 089: Lean scope.
• Comparator BoundedTreewidthL1.json.
• Comparator BoundedTreewidthL1.lean.
• Comparator PlanarL1.json.
• Comparator PlanarL1.lean.
• OpenAI catalogue entry.

GNRS Conjecture

Definitions and mathematical statement

A graph family is minor-closed if it is closed under vertex deletion, edge deletion, and edge contraction, and proper if it does not contain all finite graphs. Equip a connected graph in such a family with positive edge lengths and its shortest-path metric $d$. The GNRS conjecture asserts that for every proper minor-closed family there is a constant $C$ such that every such metric admits a map $f$ into an $L^1$ space and a scale $a>0$ with \[ a\,d(x,y)\le\|f(x)-f(y)\|_1\le C a\,d(x,y) \qquad(x,y\in V). \] The constant depends only on the family, not the graph size or edge lengths. This metric formulation is equivalent to the bounded multicommodity flow-cut gap in the source's capacities-and-demands convention. The statement does not assert isometric embedding or a dimension-independent Euclidean embedding.

Formulation and concept references: [S1].

Short English statement

Do graph families excluding a fixed minor have uniformly bounded distortion when their weighted shortest-path metrics are embedded into $L^1$?

Research attempt

Scope and first unresolved step.

This GPT-6 Astra Ultra attempt, dated 27 September 2026, constructs exact $L^1$ embeddings for weighted trees, cycles, and cactus graphs, and proves an obstruction to demanding isometry for all planar graphs. It then tests a separator-based construction. The partial results are standard geometric mechanisms with complete derivations here; no new general embedding theorem is claimed.

The first missing step is a uniformly bounded-distortion construction for all weighted graphs in an arbitrary fixed proper minor-closed family. Neither a bound growing with the number of recursive separator levels nor a construction for one subclass suffices. The source [S1] discusses the undirected GNRS conjecture as background to results about directed quasimetrics. Its directed conclusions are not substituted for this symmetric $L^1$ problem.

Trees as sums of cuts.

Root a finite weighted tree at $r$. For an edge $e$, let $A_e$ be the component of its deletion not containing $r$, and write its positive length as $\ell_e$. Define \[ F(v)_e=\ell_e\,\mathbf1_{\{v\in A_e\}}. \] Then \[ \|F(u)-F(v)\|_1 =\sum_e\ell_e |\mathbf1_{A_e}(u)-\mathbf1_{A_e}(v)| =d(u,v). \] The last equality holds because exactly the edges on the unique $u$--$v$ path separate the two vertices. This is a finite-dimensional isometric embedding, with one coordinate per edge. There is no dimension restriction in the conjecture, so the number of coordinates is harmless.

Every edge is counted once for each pair it actually separates. This exact bookkeeping, rather than a generic estimate on tree depth, is why the distortion is one even for a path with arbitrarily many vertices.

Weighted cycles also embed isometrically.

Realize a cycle with total length $L$ as a circle parameterized by $[0,L)$ with endpoints identified, placing the graph vertices at the cumulative edge lengths. For a vertex at position $x$, let $I_x$ be the half-open circular arc of length $L/2$ starting at $x$. Consider \[ F(x)=\tfrac12\mathbf1_{I_x}\in L^1([0,L),dt). \] If $\delta$ is the shorter circular distance between $x$ and $y$, then $0\le\delta\le L/2$, and the symmetric difference of their two semicircles has measure $2\delta$. Hence \[ \|F(x)-F(y)\|_1=\delta=d(x,y). \] The factor one-half is required; omitting it gives twice the distance.

This representation remains valid when an individual edge is longer than half the circumference: graph shortest distance then uses the complementary arc. For finitely many graph vertices, partition the circle at all endpoints of the arcs $I_x$. On each resulting interval every indicator is constant. Replacing an interval by a coordinate weighted by its length gives a finite-dimensional $L^1$ embedding with exactly the same distances. Thus no infinite-dimensional approximation argument is needed.

Gluing at one vertex preserves exact embeddability.

Suppose connected metric graphs $G_1,G_2$ meet at precisely one vertex $o$, with no other cross edges. Translate isometric embeddings $F_i$ so that $F_i(o)=0$. Map vertices in $G_1$ to $(F_1(v),0)$ and those in $G_2$ to $(0,F_2(v))$ in the $L^1$ direct sum.

Distances within one graph are unchanged. A path from $u\in G_1$ to $v\in G_2$ must pass through $o$, so \[ \|F(u)-F(v)\|_1 =\|F_1(u)\|_1+\|F_2(v)\|_1 =d(u,o)+d(o,v)=d(u,v). \] Excursions into the other piece cannot shorten an internal path, since they return to $o$ and have nonnegative length.

A cactus graph is a connected graph in which every edge belongs to at most one simple cycle. Its blocks are single edges or cycles, joined along a tree of cut vertices. One way to see the relevant structure is that two distinct cycles cannot share an edge or two distinct vertices: the latter configuration would create an additional simple cycle sharing edges. Repeatedly remove a leaf block and apply the one-vertex gluing lemma. The preceding tree and cycle constructions therefore prove that every positively weighted cactus graph embeds isometrically into $L^1$.

This completes a size-independent subcase, including arbitrarily many cycles. It does not cover arbitrary planar graphs, where blocks can have many intertwined cycles.

The cut inequality satisfied by every finite $L^1$ metric.

For integers $b_1,\ldots,b_N$ with $\sum_i b_i=1$, an $L^1$ metric $d_1$ satisfies \begin{equation}\label{wsref-0-61-34-30-39-3a-70-65-6e-74-61-67-6f-6e-61-6c} \sum_{i<j}b_ib_jd_1(i,j)\le0. \end{equation} First check a cut metric $\delta_A$. If $B=\sum_{i\in A}b_i$, the left side is $B(1-B)$, which is nonpositive because $B$ is an integer. Nonnegative sums preserve the inequality.

For completeness, the same conclusion holds for arbitrary $L^1$ embeddings, not only explicitly given cut sums. For real numbers $a,b$, \[ |a-b|=\int_{\mathbb R} |\mathbf1_{\{a>t\}}-\mathbf1_{\{b>t\}}|\,dt. \] Apply this identity pointwise to the finitely many coordinate functions of the embedded vertices and integrate over the underlying measure space. The metric is an integral of cut metrics, so the finite linear inequality follows. All pairwise integrals are finite; coefficients can be separated into their positive and negative parts.

A planar graph needing distortion greater than one.

Use the unit-length shortest-path metric of $K_{2,3}$. Assign $b=1$ to each of the three vertices in its larger part and $b=-1$ to each of the two in its smaller part. Their sum is one. Distances within either part are two and cross-part distances are one, giving \[ \sum_{i<j}b_ib_jd(i,j) =3\cdot2+1\cdot2-6\cdot1=2>0. \] Thus this planar metric has no isometric $L^1$ embedding.

More quantitatively, normalize an embedding with distortion $D$ so that $d\le d_1\le Dd$. The positive terms of (a409:pentagonal) total at least eight, while the absolute sum of its negative terms is at most $6D$. Therefore \[ D\ge\frac43. \] This is a lower bound for a particular planar metric, fully consistent with GNRS. A proof for all planar graphs must allow some distortion; it cannot aim for a universal exact cut decomposition.

A recursive partition can overcharge nearby vertices.

Balanced separators suggest repeatedly splitting a graph and introducing a cut coordinate at each scale. A naive version assigns the diameter of a part as the weight of its child cut. Even a path exposes the problem. Take the unit path on $2h$ vertices and split it between vertices $h$ and $h+1$. A coordinate distinguishing the two halves with weight comparable to the whole diameter gives these adjacent vertices $L^1$ distance comparable to $h$, although their original distance is one.

Adding further nonnegative cut coordinates cannot repair that upper-bound violation. Rescaling every coordinate down by $h$ would instead jeopardize the required lower bounds elsewhere. Randomized partitions, padding estimates, or more carefully weighted combinations need additional arguments; existence of small separators by itself supplies none of those estimates. This is a failure of the stated construction, not an obstruction to embedding the path, whose exact embedding was already given.

Verification and outcome.

Finite checks verify the tree-cut identity on weighted examples, the circle construction at antipodal and unequal-edge cases, and all cuts underlying the five-point inequality. The analytic proofs cover arbitrary positive lengths. No finite test establishes a constant simultaneously for all excluded-minor graph sizes.

UNRESOLVED. Exact embeddings are constructed for weighted cactus graphs, and the $K_{2,3}$ metric has distortion at least $4/3$. The remaining gap is a construction controlling expansion and contraction by one family-dependent constant for the full proper minor-closed family, beyond the one-vertex gluing structure.

Sources

• S1 Kawarabayashi and Sidiropoulos, arXiv:2111.07974 $2021$. https://arxiv.org/html/2111.07974v1. Formulation source.