Cut to size?

0:00Cuts and distances

Take a graph whose edges have positive lengths, and measure the distance between two vertices by the shortest path. Can these distances be reproduced, up to a fixed factor, by points in the space L₁? L₁ distances are exactly sums of weighted cuts: split the vertices into two sides, and count the weight once for every pair the split separates. So the question is whether one can choose weighted cuts that separate every pair in proportion to its distance, while charging every edge at most a constant times its length. The best constant is the distortion. In our exact computation by linear programming, with every edge of length one, a cycle of 8 and a 3 × 3 grid embed with no distortion at all, while the complete bipartite graph K₂,₃ needs exactly 4/3. The question matters for algorithms. Linial, London and Rabinovich, and independently Aumann and Rabani, connected such embeddings to the gap between multicommodity flows and sparsest cuts, and Gupta, Newman, Rabinovich and Sinclair showed that on a fixed graph, the worst flow-cut gap equals the worst L₁ distortion over all edge lengths. In a paper first presented in 1999, they conjectured that every family of graphs closed under taking minors, other than the family of all graphs, has bounded distortion. Planar graphs are the central test. For planar graphs, Rao proved a bound growing like the square root of the logarithm of the number of vertices, through Euclidean space, and Newman and Rabinovich showed that route cannot do better. Constant bounds were known for special classes: series-parallel graphs, where the best constant is exactly two, planar graphs that peel away in a fixed number of outer layers, and, beyond planarity, graphs of bounded pathwidth. The lower bound two, due to Lee and Raghavendra, comes from diamond-like graphs built by repeatedly replacing each edge with many parallel paths of two edges. Even the thinnest version, with just two paths per edge, needs 1.25 after two rounds in our computation. Among 120 random planar graphs on 10 vertices, with straight-line edge lengths, the largest distortion we found was about 1.21.

2:15The claims

Result 089 is two OpenAI preprints, both dated September 23. The first, 45 pages, proves the planar case: there is one universal constant C such that every finite connected planar graph, with any positive edge lengths, embeds into L₁ with distortion at most C. The second, 30 pages, proves the bounded-treewidth case: for graphs with a tree decomposition whose bags have at most k vertices, the distortion is bounded by a constant depending only on k. Neither paper computes its constant. Through the flow-cut connection, both give uniformly bounded gaps between multicommodity flow and sparsest cut on these graphs. With a reduction of Lee and Sidiropoulos, they also cover graphs that are almost embeddable in a fixed surface, with a bounded number of extra vertices and of attached strips of bounded width. The full conjecture, for every minor-closed family, still needs gluing along larger cliques and is not claimed. OpenAI also published Lean formalizations of both main theorems, about 34,000 lines for the planar case and 15,000 for bounded treewidth, matched against separate statements. We have not run the checks.

3:32How the proofs go

The planar proof first redraws the graph as vertical columns. Take a shortest-path tree from a root, and use distance from the root as height. Each edge outside the tree becomes two rising branches that meet at a tip, and planarity puts the columns in a circular order where the switches between them never cross. For any label, the active points on each column form an upper interval, switches keep membership, and the labels that change along a vertical stretch have total measure equal to its length, so every path’s length bounds the cut distance between its endpoints. That gives the upper bound for free, however many updates follow. The lower bound comes from random local updates at each scale. Thresholds take the form height plus a random sign times a field, and the fields are pieced together from distance functions within thin bands. Because links never cross, the entrances to each region come through at most two portals, so neighboring pieces choose exactly the same formula at their interfaces. A first system tries to raise the field near one endpoint of each pair; when that fails it finds short descending paths, and it can also certify separation through a low inactive tip. The pairs that survive leave seeds, and a packing bound limits how many can interfere. A second system uses fields ordered along the two arcs of the circle to separate the survivors. Sparse schedules of scales, with large gaps between them, keep coarser scales from breaking up the local regions a pair needs, and keep finer scales from erasing what it gained: each point moves by at most a constant times the scale, each eligible pair gains separation with at least a fixed probability, and a small ball is split between new regions with probability at most proportional to its radius over the scale. The treewidth proof works on the tree decomposition instead: consistent cut laws on bags glue into a global law, and particles, real functions whose threshold sweeps give cuts, are perturbed in pairs, plus and minus a function vanishing on the current bag, so that bag’s law is unchanged, while frozen pairs carry uncertainty along the decomposition that turns into separation between distant bags.

5:46Where it stands

Neither preprint is peer reviewed, and neither has been revised. OpenAI’s Lean formalizations cover both main theorems; we have not run them. The papers prove that the constants exist but give no value, and the series-parallel graphs show any planar constant must be at least two. The treewidth paper uses the padded decompositions of Filtser and coauthors and Markov gluing from Chlamtáč, Krauthgamer and Raghavendra. Neither paper is among those OSVerify reviewed, and we have seen no expert review. If they hold, planar graph metrics, and those of bounded treewidth, sit in L₁ with bounded distortion, and the corresponding flow-cut gaps are bounded too. The Gupta, Newman, Rabinovich and Sinclair conjecture for all minor-closed families remains open.