Breakthrough Tracker record
A finite counterexample claim for the Dinitz–Garg–Goemans cost conjecture
The claim gives a seven-vertex acyclic network with three demands. Its fractional flow has cost 58, while exhaustive enumeration of all eight unsplittable routings leaves every load-feasible routing with cost at least 60.
← Back to the filtered Breakthrough Tracker
- Stable ID
math-dinitz-garg-goemans-counterexample-2026- Revision
math-dinitz-garg-goemans-counterexample-2026.v1- Field
- Mathematics · Combinatorial optimization and graph flows
- Evidence
- Tier 3 · Peer reviewed: No
- Record state
- Provisional · Exact counterexample claim; specialist review pending
- Last checked
AI role
The complete instance and certificate were generated in a public GPT-5.6 Pro conversation after repeated prompts to find an unconditional counterexample. Rybin shared the result and had previously worked on the problem.
Record details
- Problem or result
- Goemans’ conjecture that a fractional single-source flow can always be rounded to an unsplittable flow of no greater cost while increasing every arc load by at most the maximum demand
- Authors
- GPT-5.6 Pro output shared by Dmitry Rybin
- Institutions
- Public ChatGPT shared conversation
- Result date
- Public claim shared July 22, 2026
Why it matters
If confirmed, the example disproves a nearly three-decade-old conjecture in single-source unsplittable flow using a small certificate that can be checked entirely with integer arithmetic.
Limits
No paper, arXiv record, DOI, versioned author repository or independent specialist assessment was located. The public shared conversation exposes the full numerical certificate, but its linked sandbox attachments are not independently downloadable from the public page. Kingy independently reconstructed the graph, enumerated all six source–terminal paths and all eight routings, and reproduced the 58-versus-60 separation; the tracker therefore records a provisional exact counterexample claim, not field acceptance.
Sources
- Primary: Public ChatGPT conversation containing the complete finite certificate
- Primary: Dmitry Rybin’s public announcement thread
- Independent: Dinitz, Garg and Goemans, original 1999 problem paper
- Independent: Swamy, Traub, Vargas Koch and Zenklusen, 2025 statement of the still-open conjecture
Correction and revision history
- 2026-07-23 — Added provisionally after the complete public numerical certificate was extracted and independently reproduced with exact integer arithmetic; stable scholarly publication and specialist assessment remain outstanding.
Machine-readable: JSON v1 · CSV v1 · Schema v1
This individual record remains noindex until a story-specific featured image passes Kingy’s rendered-pixel visual review. The source-linked tracker hub remains the public index.