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
Jul 22
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
256
890
9,542
4,268,122
Dmitry Rybin@DmitryRybin1
Jul 22
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.
15
15
1,900
156,270
Dmitry Rybin@DmitryRybin1
Jul 22
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,092
134,301
Sort replies:<br>Relevant<br>Recent<br>Liked
pranav
@pranav_so
Jul 22
Replying to @DmitryRybin1
what was the file uploaded? was it non-trivially helpful in finding the solution?
50
10,619
Dmitry Rybin@DmitryRybin1
4h
The file was this paper from arxiv
24
4,645
Ben Stephens
@btwphones
Jul 22
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?
96
63,674
Dmitry Rybin@DmitryRybin1
Jul 22
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
411
57,437
Yacine Mahdid
@yacinelearning
8h
Replying to @DmitryRybin1
ah man this is so cool would love to interview you on what the overall workflow look like
nice work!
12
5,911
Dmitry Rybin@DmitryRybin1
5h
Thank you Yacine 🫡<br>Will try to find time these days
5,011
more replies
phyrooo@phyrooo
Jul 22
Replying to @DmitryRybin1
Please continue research and find a new conjecture to disprove.
125
12,920
Bryant
@BA_Wolf
Jul 22
Replying to @DmitryRybin1
lol
lmao even
112
8,249
Ettore
@EttoreMariotti
Jul 22
Replying to @DmitryRybin1
wake up babe, a new decades old problem have been solved by AI
79
8,193
Dean McKee
@deanmckee757
Jul 22
Replying to @DmitryRybin1 @srush_nlp
Get wrecked, Dinitz, Garg, and Goemans
138
13,624
Moritz Groß
@Moritz__Gross
Jul 22
Replying to @DmitryRybin1
average thesis advisor
312
11,392
Francisco Costa 🇵🇹
@phelgo
Jul 22
Replying to @DmitryRybin1
The future of Science, ladies and gentlemen.
80
1,644
74,405
avious
@0xAvious
20h
Replying to @DmitryRybin1
the prompting is great but this 90 minute chain of thought is incredible
26
1,770
Jonathan Shobrook
@jshobrook
21h
Replying to @DmitryRybin1
“Well since you asked politely…”
31
4,844
Felp@felps_bra
Jul 22
Replying to @DmitryRybin1
lol
133
10,575
Kislay Parashar
@KislayParashar1
Jul 22
Replying to @DmitryRybin1
Thirty years of people trying to prove this and it breaks on a graph small enough to fit on a whiteboard, that's rougher than gpt finding it first honestly.
70
7,107
Andrew 🎛️🎹🔊
@android_stern
23h
Replying to @DmitryRybin1
It was really that simple
135
5,249
Brayan Ortiz
@brayaON20
Jul 22
Replying to @DmitryRybin1
The new scientific journal will be the LLMs sessions that showcase the conversation leading the proof of a result.
22
6,744
ss@ss04072012
Jul 22
Replying to @DmitryRybin1
Woah that conversation is awesome .
38
8,397
George Ramonov
@georgeramonov
Jul 22
Replying to @DmitryRybin1 @srush_nlp
do gaslight until breakthrough
39
11,281
Tim Sweeney
@TimSweeneyEpic
23h
Replying to @DmitryRybin1
Thank you for sharing the source chat!
115
4,915
Bitter Pills to Swallow
@thebitterlesson
Jul 22
Replying to @DmitryRybin1
This approach remains undefeated
18
981
34,159
will
@wblazer_
Jul 22
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!"
41
1,527
60,380
peeyush
@peeyuzz
Jul 22
Replying to @DmitryRybin1
too much basedness for a next token predictor
20
1,387
41,275
jokesonly@recurrentneural
Jul 22
Replying to @DmitryRybin1
I am just lolling at the prompts. Hats off!
18
6,584
Ankit Jxa
@kingofknowwhere
Jul 22
Replying to @DmitryRybin1
This paper has 250 citations. How did you find it
22
7,333
TheShadowbanned
@ShadowbanSlam
Jul 22
Replying to @DmitryRybin1
The chat is just... sad. "Find a countexample." "Continue research." "Continue...