Constant-distortion L1 embeddings of planar and bounded-treewidth graphs

Source and verification

This article explains family 089 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Graph distances and cut metrics

A connected finite graph with positive edge lengths has a shortest-path metric $d_G$. An embedding into $L_1$ has distortion at most $D$ if, after rescaling, its image distances satisfy

$$\begin{array}{rl}{d}_G(x,y)& \le \Vert f(x)-f(y){\Vert }_1,\\ \Vert f(x)-f(y){\Vert }_1& \le D{d}_G(x,y).\end{array}$$

No requirement of linearity is meaningful on the graph’s vertex set. The target dimension may depend on the graph.

The useful description of a finite $L_1$ metric is a nonnegative sum of cut metrics:

$$d_f(x,y)=\sum _{S\subseteq V}{w}_S|1_S(x)-1_S(y)|.$$

To see the origin of this formula, apply $|a-b|={\int }_{\mathbb{R}}|1_{\{a>t\}}-1_{\{b>t\}}|dt$ to every coordinate. On a finite domain, only finitely many distinct cuts arise. Conversely the weighted indicator coordinates realize the sum in a finite-dimensional ${\ell }_1$ space.

The construction problem is thus probabilistic: produce cuts that separate every distant pair often enough, while charging every edge only in proportion to its length.

🏷️ The two graph classes

Statements in the family

The planar-graph manuscript claims an absolute distortion bound for every finite connected planar graph with positive edge lengths. The bound is independent of vertex count and of the ratio of the longest to shortest edge. (OpenAI, 2026)

The tree-decomposition manuscript claims that, for every fixed bag-size bound $k\ge 2$, there is a finite constant $C_k$ giving such an embedding for all finite graphs admitting a tree decomposition with bags of size at most $k$. (OpenAI, 2026a)

A tree decomposition is a tree whose nodes carry vertex subsets called bags. Every graph edge lies in a bag, and the bags containing any one vertex form a connected subtree. Bag size at most $k$ means treewidth at most $k-1$. A bound independent of the depth of this decomposition is essential: a long chain of small bags is still allowed.

These are distinct hypotheses. Planar graphs may have arbitrarily large treewidth, while fixed treewidth supplies a separator structure of a different kind. The two statements do not by themselves prove a constant-distortion theorem for every excluded-minor graph class.

🏷️ An elementary model: trees

For a weighted tree, deleting an edge $e$ splits the vertex set into a cut $S_e$. The unique path from $x$ to $y$ crosses $e$ exactly when the cut separates them. Therefore

$$\begin{array}{c}{d}_G(x,y)\\ =\sum _e\ell (e)|1_{S_e}(x)-1_{S_e}(y)|.\end{array}$$

Trees embed isometrically in $L_1$. Cycles destroy this unique-path formula: a cut may be crossed more than once along a path, and a construction that keeps edge costs small can fail to separate a distant pair.

For any proposed cut measure, an upper estimate on each edge extends to all pairs by summing along a shortest path. The lower estimate is the difficult direction; it must be established for every pair, rather than only for adjacent vertices or a sampled collection.

🏷️ Planar columns, switching, and scale control

The planar manuscript organizes vertices into columns with a height coordinate derived from distance to a root. Its cut labels occupy upper intervals in each column. Local switching operations preserve that monotonicity in every realization, which protects the edge-charge estimate. Neighboring coordinate charts must agree on their interfaces; the source gives paired chart formulas with opposite perturbations to enforce this compatibility. (OpenAI, 2026b)

For the lower estimate, a first cut system either separates a pair or confines the unresolved pair to seeds near two short paths. The ensuing packing assertion applies to those seeds. It does not assert that arbitrary planar graph metrics are doubling. A second system uses circular-arc and transverse fields to handle the surviving configurations.

The constructions at different scales must coexist. The source selects a lacunary sequence, meaning that consecutive scales differ by a sufficiently large fixed factor. Failures caused by much coarser scales have a geometric-series bound; movements introduced at much finer scales have another summable bound. These two estimates protect a separation obtained at the scale of the pair. Without them, an estimate at one isolated scale would not yield a single embedding of the whole graph.

Taking expected cut distances gives a deterministic $L_1$ metric. Positivity of the weights preserves the upper bound, while the pairwise separation probabilities supply the lower bound.

🏷️ Consistent bags and a depth-independent estimate

The second manuscript starts with compatible probability laws for cuts restricted to individual bags. Tree-structured conditional sampling can glue consistent bag laws into a global law, but that observation alone only manages local marginals and upper bounds. It does not ensure that distant vertices are separated. (OpenAI, 2026a)

The additional mechanism uses paired perturbations of particles. Their average vanishes on a bag, so existing bag marginals remain unchanged while unresolved distances can be exposed. A quadratic budget controls the largest differences, preventing a fresh loss from accumulating at every bag along a long decomposition path.

Reservations retain selected pairs of particles in a common order. Since a bag contains at most $k$ vertices, the possible order types are bounded in terms of $k!$. The lower estimate is expressed through transport among cut states on bags; there are at most $2^k$ such states. These are finite bounds depending on bag size, not on the number of bags.

The manuscript concludes existence of $C_k$, rather than the sharp dependence of $C_k$ on $k$. The distinction matters for applications with growing treewidth. Likewise, the planar absolute constant and the fixed-bag constant do not include an efficient implementation merely from the metric existence statement.

🏷️ Key steps and proof outlines

A cut construction has separate upper and lower obligations

Let $\nu$ be a nonnegative measure on cuts and define $D(x,y)=\int |1_S(x)-1_S(y)|d\nu (S)$. To prove the upper bound, it suffices to check edges. If $x=x_0,\dots ,x_m=y$ is a shortest path, the triangle inequality for each indicator gives

$$D(x,y)\le \sum _{i=1}^{m}D(x_{i-1},x_i)\le C\sum _{i=1}^m\ell (x_{i-1},x_i)=C{d}_G(x,y).$$

No corresponding path argument proves the lower bound: different edge separations can cancel when a cut is evaluated only at the two endpoints. The source constructions therefore protect pair separation explicitly. Expected cuts are useful because upper edge charges and lower separation probabilities are both linear in the cut measure.

Planar switching preserves a monotone invariant

In the planar manuscript, a column is ordered by a height derived from a root-distance function. Each cut occupies an upper interval of the column. Switching a threshold while retaining this upper-interval form prevents rapid repeated crossings along the column. Local coordinate charts describe neighboring columns, and paired perturbations with opposite signs match their interfaces.

The main update either gives a pair a definite separation probability or confines it to a more structured unresolved configuration. In the latter case, secondary seeds lie near two short paths. A packing lemma applies specifically to those seeds. Planarity is used through their circular order and the geometry of the paths; the argument does not infer a global doubling property of planar graph metrics. Ordered fields on two arcs then supply a transverse distinction between pairs that the first update failed to separate. (OpenAI, 2026b)

Coarse and fine scales must preserve a successful separation

Suppose a pair has distance comparable to scale $r$. A local cut update at that scale is only useful if subsequent updates do not erase its separation. The source uses scales separated by a fixed large factor $L$. Coarser updates have small probabilities of interfering with the relevant local chart, while finer updates have small total displacement of its thresholds.

The abstract accounting is geometric: if interference at $L^{j}r$ is bounded by $C{L}^{-j\alpha }$, or displacement at $L^{-j}r$ by $Cr{L}^{-j\beta }$, summing over $j\ge 1$ gives finite totals. Choosing $L$ large makes those totals smaller than the separation margin obtained at scale $r$. The manuscript proves the appropriate estimates for its charts and switches. This is how local successful experiments coexist inside one cut law, rather than merely furnishing a different embedding for each pair.

Tree decompositions glue local laws but need long-range transport

For bounded treewidth, adjacent bags overlap in a separator. Compatible laws on bag cuts can be glued by conditional sampling along the decomposition tree. The connected-subtree condition for each vertex ensures that its cut value is consistent wherever it appears. Every graph edge lies in a bag, so local edge bounds survive this gluing.

Long-range separation requires more. The manuscript interprets the coupling of cut states along the bag path as transport. There are at most $2^k$ cut states per bag, but the path can contain arbitrarily many bags. A product of fixed local losses would therefore be unacceptable. The particle construction instead retains reservations and uses paired perturbations whose average on a bag is zero. Existing marginals remain unchanged while selected unresolved particle pairs gain separation. (OpenAI, 2026a)

Reservations and anchors prevent losses from accumulating with depth

Reservations preserve a common ordering of selected particles. The number of order types is bounded in terms of $k!$, independently of decomposition depth. A quadratic budget controls large changes between particles, so repeated perturbations along a long path consume a finite total amount rather than one fresh allowance per bag.

The anchor construction adds independent launch noise from two sources and handles pairs that are not exposed inside a common bag. The final contradiction normalizes a hypothetical failure of the lower comparison and studies the limiting transport across a decomposition path. Either a common-bag perturbation or a crossing anchor separates the pair. The sum of the corresponding two cut pseudometrics therefore satisfies

$${\lambda }_k{d}_G(x,y)\le D_{\mathrm{bag}}(x,y)+D_{\mathrm{anc}}(x,y)\le C_k^{\prime }{d}_G(x,y).$$

Rescaling gives a distortion bound depending only on $k$. The construction proves existence of a finite cut metric; it does not by itself provide a sharp formula for the best distortion or an efficient algorithm for its weights.

See Also

Edit distance in L1 uses the same cut representation to prove lower bounds instead of constructing embeddings. Doubling subsets of Hilbert space explains a different obstruction, where the target is finite-dimensional Euclidean space.

🏷️ Manuscripts and verification scope

• Planar Graph Metrics Embed into $L_1$ with Constant Distortion — pinned manuscript and companion source.
• $L_1$ Embeddings of Graphs of Bounded Treewidth — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The scope describes the two headline embedding assertions. Their graph classes and the dependence of the constants remain distinct. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. L₁ Embeddings of Graphs of Bounded Treewidth.

🐻  OpenAI 2026b. Planar Graph Metrics Embed into L₁ with Constant Distortion.