Dmitry Rybin posts a GPT-5.6 Pro counterexample to the ~30-year-old Dinitz–Garg–Goemans (Goemans cost) conjecture on unsplittable flows
Awaiting review
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Expert-checked
- Importance
- 3 of 5
- Last verified
- 19 October 2026
Your AI and this story
- GPT-6 Astra83 days after its cutoff
- Claude Opus 5.522 days after its cutoff
- Gemini 4 Argon113 days after its cutoff
- Grok 4.752 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 22 days before it.
Key facts
- Rybin on X (22 July 2026, ~4.88M views by Oct 19, fxtwitter): ‘Dinitz-Garg-Goemans conjecture is false. This graph theory problem was open for ~30 years. The graph below has fractional flow cost 58. Any unsplittable flow (with capacity violation <=15) has cost at least 60.’ The post links the ChatGPT conversation with GPT-5.6 Pro
- What is refuted (DataCamp): the cost version, Goemans’ conjecture that a cheap splittable flow can be turned into an unsplittable one keeping both congestion and cost bounded; the Dinitz–Garg–Goemans congestion theorem itself is not in question
- Construction (as reported by 36Kr and DataCamp): one source, three terminals with demands 15, 10 and 15; fractional cost 58 vs ≥ 60 for any unsplittable routing within the congestion budget. DataCamp could not reproduce the exact graph from a primary source
- Checks: DataCamp says several people checked the arithmetic and found it consistent and one researcher placed the instance in an infinite three-parameter family; QbitAI/36Kr says the deliverables included proof certificates, an exhaustive enumeration program and LaTeX source. No named expert statement found
- Seen by us only on 19 Oct 2026, through Fireship’s video ‘Summer math fell to the machines’ (Aug 19); Chinese tech press (36Kr, 24 July) covered it the same week together with Shouqiao Wang’s six Erdős problems
What happened
Rybin asked GPT-5.6 Pro for a complete counterexample to the conjecture and posted the resulting graph and the conversation. The claim spread widely on X (one of the most viewed AI-maths posts of the summer) and in Chinese tech media. We read the X post (via fxtwitter), DataCamp and 36Kr; the open-since year is DataCamp’s “roughly 1999”, which fits Rybin’s “~30 years”. The construction details are secondary; verify against the chat before relying on them.
Why it matters
It is one of several AI-found counterexamples posted in July 2026 (see the Jacobian, Hessian and Rota-flats entries of the same week) and was missed by this dataset for three months because it lived only on X and in a chat log, with no arXiv paper.
What is disputed or not yet verified
| Verification | Unverified claim (X post with chat log); arithmetic reportedly checked by others; no paper or peer review found |
|---|
Sources
4 sources from 4 sites. Numbers match the chips in the text.
4 sources: 2 press, 2 reactions
Press
- DataCamp: GPT-5.6 and the Dinitz-Garg-Goemans conjecturedatacamp.com, press
- 36Kr: GPT-5.6 disproves 30-year graph theory conjecture; Peking University alumnus solves six Erdős problems in five days (24 July)eu.36kr.com, press
Reactions
- Dmitry Rybin on X: Dinitz-Garg-Goemans conjecture is false (22 July 2026)x.com, discussion
- ChatGPT conversation with GPT-5.6 Pro (shared by Rybin)chatgpt.com, discussion
Changes
- Filed. Late from the 2026-10-19 lead (Fireship video); X post read via fxtwitter