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
15h
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
183
648
7,457
2,469,986
Dmitry Rybin@DmitryRybin1
15h
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.
12
10
1,509
104,955
Dmitry Rybin@DmitryRybin1
15h
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
859
92,457
Sort replies:<br>Relevant<br>Recent<br>Liked
Ben Stephens
@btwphones
7h
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?
47
33,753
Dmitry Rybin@DmitryRybin1
7h
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
228
30,440
Archos-Capital
@Archos_Capital
12m
Replying to @DmitryRybin1
Fun corollary: this same graph also kills the Morell–Skutella convex-combination conjecture.
Each sink's zero-cost path is pinned by its terminal arc, so the "free ride" probabilities would sum to 1/3 + 2/5 + 1/3 = 16/15 — but the shared corridor allows at most one free rider. Can't have 107%.
Verified by both my good friends Fable 5 and 5.6 Sol!
315
板核酸(はんかくさん)@hankakuspace7
23m
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.
344
Francisco Costa 🇵🇹
@phelgo
11h
Replying to @DmitryRybin1
The future of Science, ladies and gentlemen.
60
1,275
51,293
Steve Martin
@RighttoTryGuy
8h
Replying to @DmitryRybin1
267
14,583
Ettore
@EttoreMariotti
11h
Replying to @DmitryRybin1
wake up babe, a new decades old problem have been solved by AI
65
6,844
Lovel Sinagara@LSinagara
2h
Replying to @DmitryRybin1
After Jacobian Conjecture being proven wrong, now this Dinitz-Garg-Goemans conjecture. Anyone care what this is all about?
1,309
will
@wblazer_
12h
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!"
27
1,221
45,799
筋トレパンダ@a_newbie_trader
6h
Replying to @DmitryRybin1
日本からこんにちは😊<br>私は数学徒ではないので正直なところ、Dinitz-Garg-Goemans予想が何なのか理解できないといった感じですが😅、きっと日本でも話題になると思います👀<br>ニュースになるかも📺️
1,852
peeyush
@peeyuzz
10h
Replying to @DmitryRybin1
too much basedness for a next token predictor
12
1,031
27,676
Bryant
@BA_Wolf
8h
Replying to @DmitryRybin1
lol
lmao even
72
5,451
UncharitableTake@Unchariterrible
51m
Replying to @DmitryRybin1
Hmm. But is the conjecture without merit? Is a restatement of the conjecture with narrower bounds called for?
299
George Ramonov
@georgeramonov
12h
Replying to @DmitryRybin1 @srush_nlp
do gaslight until breakthrough
35
9,936
phyrooo@phyrooo
14h
Replying to @DmitryRybin1
Please continue research and find a new conjecture to disprove.
121
11,750
Moritz Groß
@Moritz__Gross
7h
Replying to @DmitryRybin1
average thesis advisor
164
5,361
Tim Sweeney
@TimSweeneyEpic
4h
Replying to @DmitryRybin1
Thank you for sharing the source chat!
55
2,214
Dean McKee
@deanmckee757
12h
Replying to @DmitryRybin1 @srush_nlp
Get wrecked, Dinitz, Garg, and Goemans
119
11,939
Felp@felps_bra
9h
Replying to @DmitryRybin1
lol
96
7,285
jokesonly@recurrentneural
12h
Replying to @DmitryRybin1
I am just lolling at the prompts. Hats off!
18
5,968
Abraham Marín-Pérez@AbrahamMarin
8h
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,159
pranav
@pranav_so
10h
Replying to @DmitryRybin1
what was the file uploaded? was it non-trivially helpful in finding the solution?
31
4,096
whocareslol@whocareslo4730
13h
Replying to @DmitryRybin1
that...