Paper explains ChatGPT-found counterexample to Goemans's unsplittable-flow conjecture
Goemans conjectured that any fractional single-source flow could be converted into an unsplittable flow without increasing total cost and while increasing any arc load by at most the largest demand. The conjecture was long-standing. Recently, Dmitry Rybin announced a seven-vertex counterexample found through an interaction with ChatGPT, which disproved it.
The paper's authors say that interaction left several things open. It did not reveal why this particular topology and its demand, fractional-flow and cost choices work together, whether the example belongs to a broader family, or which structural features determine where counterexamples can occur. It also left unclear why the AI-assisted search succeeded where earlier human efforts had not.
To answer these questions the paper develops a forward counterexample construction pipeline. It starts from an arborescence on which failure is impossible and adds terminal-entering shortcut arcs. The resulting load constraints define a finite set of admissible route choices. Their convex hull, which the paper calls the conflict polytope, yields exact conditions for demands, fractional flows and costs.
Starting from a simple arborescence, the pipeline selects Rybin's topology and characterizes all counterexamples that topology supports.
The experiments test whether the pipeline transfers. When ChatGPT was instructed to follow it while varying the initial arborescence and the shortcut placement, it produced counterexamples on topologies genuinely different from Rybin's. It found valid constructions starting from 93 other rooted arborescence shapes.
The theory also explains why the original example was difficult to discover through blind enumeration. The authors suggest that Rybin's interaction lies between blind enumeration and a complete theory-guided construction.
Key facts
- Goemans's conjecture said any fractional single-source flow can become an unsplittable flow without raising total cost and with any arc load rising by at most the largest demand.
- Dmitry Rybin announced a seven-vertex counterexample found through an interaction with ChatGPT, which disproved the conjecture.
- The paper's pipeline starts from an arborescence on which failure is impossible, adds terminal-entering shortcut arcs, and uses a conflict polytope to give exact conditions for demands, fractional flows and costs.
- The pipeline selects Rybin's topology and characterizes all counterexamples it supports.
- Told to follow the pipeline, ChatGPT produced counterexamples on topologies different from Rybin's and found valid constructions from 93 other rooted arborescence shapes.
Why it matters
An AI-assisted interaction disproved a long-standing conjecture, but it left the reasons unexplained: why that topology works, whether it belongs to a broader family, and why the search succeeded where earlier human efforts had not. The paper tries to turn a one-off result into understanding. It gives a construction that recovers Rybin's example and characterizes every counterexample that topology supports. The authors also place Rybin's interaction between blind enumeration and a complete theory-guided construction.
Who it affects
Researchers working on single-source flows and unsplittable flow, the area Goemans's conjecture belongs to, now have a systematic description of where counterexamples can occur. Anyone watching how language models are used in mathematical discovery gets a worked example of moving from an opaque AI-assisted find to a structured theory that the model can then follow.
How to use it
The recipe in the abstract is concrete. Start from an arborescence on which failure is impossible. Add terminal-entering shortcut arcs. Read the load constraints as a finite set of admissible route choices, and take their convex hull, the conflict polytope, to get exact conditions on demands, fractional flows and costs. In the experiments, ChatGPT was instructed to follow this pipeline while varying the initial arborescence and the shortcut placement.
How solid is it
This is an arXiv preprint, and the account here rests on its abstract. The paper's claims are its own: that the pipeline selects Rybin's topology, characterizes all counterexamples it supports, and that ChatGPT produced counterexamples on genuinely different topologies, with valid constructions from 93 other rooted arborescence shapes. The abstract names no authors or institutions. It does not say which ChatGPT model or version was used, or how many prompts or attempts were needed. It does not say how many of the tried arborescence shapes failed, only that 93 other shapes gave valid constructions. It does not say whether the paper has been peer reviewed.
Risks and caveats
The abstract gives no date for Rybin's announcement and no first name or reference for Goemans's conjecture beyond calling it long-standing. It reports no runtime, compute cost or search-space size for the blind enumeration, so the claim that the original example was hard to find by blind enumeration cannot be sized from the abstract alone. The authors describe Rybin's interaction as lying between blind enumeration and a complete theory-guided construction, which is a suggestion rather than a precise finding.
“The theory also explains why the original example was difficult to discover through blind enumeration and suggests that Rybin's interaction lies between blind enumeration and a complete theory-guided construction.”
— Abstract of arXiv 2611.23244