Short··0:21·Combinatorics
Erdős–Gallai Conjecture: Every Graph Splits Into Few Loops
Watch on YouTubeAbout the problem →
About this video
The Erdős–Gallai cycle-decomposition conjecture asks whether the links of every graph on n dots can be split into at most C·n pieces, each a simple cycle or a single link, for one fixed constant C, even when the graph is dense and has about n² links. OpenAI claims a proof that such a constant exists for every finite simple graph; this is OpenAI's preprint, not yet peer reviewed. The animation peels a real random graph with 20 dots and 88 links into 9 cycles and 10 single links.
Paper (OpenAI, catalogue result 181):
- A linear cycle-and-edge decomposition of every graph: github.com/openai/math/blob/main/preprints/A-linear-cycle-and…
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/181
About the problem
Combinatorics·OpenAI Math·Result 181
The Erdős–Gallai cycle-decomposition conjecture
Proves that the edges of every finite simple undirected graph on n vertices can be partitioned into at most Cn simple cycles and single edges, for an absolute constant C. This resolves the Erdős–Gallai cycle-decomposition conjecture, bounding the number of pieces linearly even for dense graphs. (Lean)
Topics
Erdős–Gallai conjectureErdos Gallai conjecturecycle decompositioncycle decomposition conjectureErdős–Gallai cycle decompositionedge decompositiongraph decompositioncycles and edgesgraph theoryextremal graph theorycombinatoricsPaul ErdősTibor Gallaidense graphsOpenAIOpenAI mathAI mathematicsAI proofmathsmathematicsmath shorts3D animationErdos-Gallai conjectureErdos-Gallai cycle decompositionPaul Erdos
