Dmitry Rybin (@DmitryRybin1): "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
Dmitry Rybin@DmitryRybin1
23h
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 chatgpt.com/share/6a60b2eb-0…
Jul 22, 2026 · 12:18 PM UTC
227
819
8,765
3,455,965
Dmitry Rybin@DmitryRybin1
23h
I know counterexamples to old conjectures are becoming a meme at this point. But I really cared about this problem and spent many weeks thinking about it a while ago (in both directions, proof and disproof).
I think almost all graph flows experts thought about this problem.
14
12
1,742
133,296
Dmitry Rybin@DmitryRybin1
23h
The conjecture was based on absolutely stunning result of Dinitz, Garg, and Goemans: any fractional flow can be routed to unsplittable flow by violating graph capacities by at most max(demand).
The chat with gpt pro here is an absolute meme
1,001
115,823
Sort replies:<br>Relevant<br>Recent<br>Liked
Ben Stephens
@btwphones
16h
Replying to @DmitryRybin1
in hindsight, could this have been found by bruteforce? and if so, how many years ago, given feasible compute of that era?
81
51,985
Dmitry Rybin@DmitryRybin1
16h
Not really.
I tried brute force search myself and with old LLMs too (o1/o3). The problem is there are many degrees of freedom: costs, flows, demands to nodes. so even tiny graphs have enormous number of combinations of these params
335
46,849
wxKobold
@wxKobold
30m
Replying to @DmitryRybin1
Tried your strategy of just asking ChatGPT to find something, and it did. But I don't actually know enough about graphs to vet the answer. You feel like checking it out for me?
73
AIコンサルお姉さん｜がんばらない時代@AI_Xanadu_Pro
4h
Replying to @DmitryRybin1
反例がひとつの具体的なグラフとして提示されている点が、証明とは違って扱いやすいところかと思います。
モデルの推論を信じ込まなくても対象そのものを直接検算できるので、再現性は GPT-5.6 Pro の中身よりも外側の独立検証で決まりそうですね。
751
❦@3Ddoritos
8h
Replying to @DmitryRybin1
I continued your conversation and was able to also get a direct disproof of Morell–Skutella Conjecture 2
1,346
Francisco Costa 🇵🇹
@phelgo
20h
Replying to @DmitryRybin1
The future of Science, ladies and gentlemen.
70
1,521
66,341
Devesh@ibedevesh
6h
Replying to @DmitryRybin1
My model simply says this is impossible
695
Joscha Bach
@Plinz
15m
Replying to @DmitryRybin1
People are using immature AI to recklessly destroy lots of math. We should wait until the models are good enough to *prove* conjectures instead of just disproving them. It's so much easier to destroy than to build! We need a moratorium on using AI against math.
103
Bryant
@BA_Wolf
16h
Replying to @DmitryRybin1
lol
lmao even
98
7,300
Steve Martin
@RighttoTryGuy
17h
Replying to @DmitryRybin1
10
342
20,040
Lovel Sinagara@LSinagara
10h
Replying to @DmitryRybin1
After Jacobian Conjecture being proven wrong, now this Dinitz-Garg-Goemans conjecture. Anyone care what this is all about?
2,455
will
@wblazer_
21h
Replying to @DmitryRybin1
Hahahaha literally just:<br>> Do a breakthrough<br>"I did not find a breakthrough"<br>> Try again<br>"No breakthrough still"<br>> Try harder<br>"No luck, this is an open problem!"<br>> What if you solved it though<br>"Here's your breakthrough sir!"
36
1,431
54,867
Dean McKee
@deanmckee757
21h
Replying to @DmitryRybin1 @srush_nlp
Get wrecked, Dinitz, Garg, and Goemans
128
13,017
peeyush
@peeyuzz
19h
Replying to @DmitryRybin1
too much basedness for a next token predictor
16
1,274
36,388
Ettore
@EttoreMariotti
19h
Replying to @DmitryRybin1
wake up babe, a new decades old problem have been solved by AI
76
7,810
Moritz Groß
@Moritz__Gross
16h
Replying to @DmitryRybin1
average thesis advisor
267
8,888
Tim Sweeney
@TimSweeneyEpic
13h
Replying to @DmitryRybin1
Thank you for sharing the source chat!
94
3,986
pranav
@pranav_so
18h
Replying to @DmitryRybin1
what was the file uploaded? was it non-trivially helpful in finding the solution?
36
4,686
phyrooo@phyrooo
22h
Replying to @DmitryRybin1
Please continue research and find a new conjecture to disprove.
124
12,524
Felp@felps_bra
18h
Replying to @DmitryRybin1
lol
118
9,416
Abraham Marín-Pérez@AbrahamMarin
17h
Replying to @DmitryRybin1
Since this is a shared chat, anyone can continue it. Just ask "verify your work, are you sure that you have truly disproved the conjecture?" and then have fun.
4,313
板核酸(はんかくさん)@hankakuspace7
9h
Replying to @DmitryRybin1
I, too, have (likely) discovered a counterexample to a recent conjecture on line-graph inertia by using GPT 5.6! What makes this interesting is that the AI selected both the topic and the solution method; I do not even fully grasp the meaning of the problem itself.
1,389
Geospatial FM@geospatialfm
14h
Replying to @DmitryRybin1
Is this a theorem by AGI...