Short··0:20·Convex and metric geometry
GNRS Conjecture for Planar Graphs: OpenAI Claims L1 Embeddings
Watch on YouTubeAbout the problem →
About this video
The Gupta–Newman–Rabinovich–Sinclair (GNRS) conjecture asks whether the distances in planar graphs, and in any family closed under minors, can be drawn in L1 with only bounded stretch; an L1 map is exactly a weighted stack of cuts. OpenAI claims proofs that every planar graph, with any positive edge lengths, embeds into L1 with one universal distortion bound, and that graphs of bounded treewidth do too, so the matching multicommodity flow–cut gaps are bounded. The animation computes the best L1 map of one small planar graph by linear programming: 39 weighted cuts, stretch 1.25. These are OpenAI's preprints, not yet peer reviewed.
Papers (OpenAI, catalogue result 089):
- Planar Graph Metrics Embed into L1 with Constant Distortion: github.com/openai/math/blob/main/preprints/Planar-Graph-Metri…
- L1 Embeddings of Graphs of Bounded Treewidth: github.com/openai/math/blob/main/preprints/L1-Embeddings-of-G…
The animation illustrates the result; it is not a proof.
Gradient Damage: mathematics you can see, equations you can hear.
youtube.com/@gradientdamage
Every result explained: gradientdamage.com/p/089
About the problem
Convex and metric geometry·OpenAI Math·Result 089
Bounded-distortion L1 embeddings of planar and bounded-treewidth graphs
Resolves the planar and bounded-treewidth cases of the Gupta–Newman–Rabinovich–Sinclair conjecture. Shortest-path metrics of finite connected graphs with arbitrary positive edge lengths embed into real L1 with universal distortion for planar graphs, and distortion depending only on treewidth for bounded-treewidth graphs. The corresponding multicommodity flow–cut gaps are uniformly bounded. (Lean)
Topics
GNRS conjectureplanar embedding conjectureL1 embeddingmetric embeddingplanar graphstreewidthdistortioncut metricssparsest cutmulticommodity flowflow cut gapmetric geometrytheoretical computer sciencegraph theoryOpenAIOpenAI mathAI mathematicsAI proofmathsmathematicsmath shorts3D animation
